mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2005-04-25, 12:04   #1
JHansen
 
JHansen's Avatar
 
Apr 2004
Copenhagen, Denmark

11101002 Posts
Cool Factorization attempt on 100^99+99^100

Hi everyone!

I'm currently factoring a number from the Cunningham project together with Tom Cage. When that's done I would like to try something new, namely a C150+ GNFS. 100^99+99^100 is ideal for this. The cofactor of 100^99+99^100 is a C151.

Today I did some trial sieving with the various SNFS polynomials this number allows, but they are all terrible. By far, I got the best results using a GNFS polynomial instead.

The usual rule of thumb says that one should do ECM to 1/3 of the number of digits before running GNFS, so this number needs to have ECM done to 50 digits.

Therefore I would like to suggest this number for ECM work. The XYYXF homepage says there's been done 400 curves with B1=100M, so there's still a lot of work left

Anyone interested in helping out? After the ECM has been done there's the 'small' matter of actually doing the GNFS sieving. This is another place where it's easy to help out, since the ggnfs siever can be used (the post-processing will not be done with ggnfs, though).

If anyone is interested in helping out, then their help is most valued

--
Cheers,
Jes

Last fiddled with by JHansen on 2005-04-25 at 12:09
JHansen is offline   Reply With Quote
Old 2005-04-25, 12:19   #2
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

32·112 Posts
Default

Whether done by GNFS or SNFS, the ECM work should be done first. Therefore I encourage this effort.

Jes,
I'm somewhat surprised that you found GNFS significantly better than SNFS.
Would you mind posting some of the details of your trials?
Wacky is offline   Reply With Quote
Old 2005-04-25, 12:47   #3
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

46438 Posts
Default

Using the SNFS polynomial you mentioned before with Franke's lattice siever on an Athlon XP 3000+, I get an estimate for the sieving time of about 3 weeks. I cannot believe that GNFS on a c150 would be faster than this.

Alex
akruppa is offline   Reply With Quote
Old 2005-04-25, 13:53   #4
JHansen
 
JHansen's Avatar
 
Apr 2004
Copenhagen, Denmark

22·29 Posts
Default

Alex, what polynomials did you use?

I tried the following 3:

1) f(X)=X^5+100 and g(X)=99^20*X-100^20

2) f(X)=100^3*X^6+99^4 and g(X)=99^16*X-100^16

3) f(X)=99^2*X^6+100^3 and g(X)=99^17*X-100^17

But these polys give trash results

--
Cheers,
Jes
JHansen is offline   Reply With Quote
Old 2005-04-25, 14:02   #5
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

I used your 1) polynomial. This is my siever input file:

Code:
2537196124785405629298472350522359111855410046873849968728166881265356084210413204319061258004615655191075511741881238499654058298331798022820025835261
X5 1
X0 100
Y1 8179069375972308708891986605443361898001
Y0 -10000000000000000000000000000000000000000
M 1320467787210331522376990713761285618785472848090779503074046958635251860331885809596723875650972264555150295702904709620129364887501601327334053746078
0 10000000 2.7 29 57
0 10000000 2.7 29 57
Alex
akruppa is offline   Reply With Quote
Old 2005-04-25, 14:31   #6
JHansen
 
JHansen's Avatar
 
Apr 2004
Copenhagen, Denmark

1648 Posts
Thumbs up

Quote:
Originally Posted by akruppa
I used your 1) polynomial. This is my siever input file: ...
I just did some sanity checking to see where my error was. I used the ggnfs version of the Franke siever. It turns out that I forgot to set the large primes limit in my input file, and it looks like the siever then assumed that I did not want to use large primes.

That resulted in ~20sec/rel instead of ~ 0.1sec/rel when you use 29 bit large primes.

Thanks for correcting my error!

--
Cheers,
Jes
JHansen is offline   Reply With Quote
Old 2005-04-25, 14:33   #7
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

You're welcome!

Alex
akruppa is offline   Reply With Quote
Old 2005-04-26, 05:36   #8
trilliwig
 
trilliwig's Avatar
 
Oct 2004
tropical Massachusetts

3×23 Posts
Default

So, are you still interested in doing 99^100+100^99? Seeing as it's now a C202 SNFS instead of a C151 GNFS. So according to the 2/9 rule, ECM need only be done up to the 45-digit level. If you are, I would be interested in helping out with the sieving.
trilliwig is offline   Reply With Quote
Old 2005-04-26, 07:38   #9
JHansen
 
JHansen's Avatar
 
Apr 2004
Copenhagen, Denmark

11101002 Posts
Thumbs up

Quote:
Originally Posted by trilliwig
So, are you still interested in doing 99^100+100^99? Seeing as it's now a C202 SNFS instead of a C151 GNFS.
Yes, I am.

Quote:
Originally Posted by trilliwig
So according to the 2/9 rule, ECM need only be done up to the 45-digit level. If you are, I would be interested in helping out with the sieving.
Err... 151*2/9 ~33,6 so, the ECM needs only be done through the 35 digit level, right?

The XYYXF page states that 400 curves with B1=100M has been done, and ecm 6 reports that one needs only 25 curves with B1=100M to complete the 35 digit level. Thus, the ECM works is all done.
Quote:
Originally Posted by trilliwig
If you are, I would be interested in helping out with the sieving.
Excellent! Yes, you are most welcome!

I will send a PM to you later today with the details.

--
Cheers,
Jes
JHansen is offline   Reply With Quote
Old 2005-04-26, 07:43   #10
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

The GNFS 1/3 rule refers to the size of the remaining cofactor, but the SNFS 2/9 rule refers to the SNFS difficulty. The size of the cofactor has pracically no effect on the time required for SNFS. I, too, would recommend ECM to 45 digits.

Alex
akruppa is offline   Reply With Quote
Old 2005-04-26, 07:55   #11
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

2×1,097 Posts
Default

That makes much more sense! At the 55 digit level, one curve with B1=11e7 takes just under 30 minutes on my 1.9GHz Opteron, so it would take nearly a year to finish at that level for my Opteron. I know SNFS or GNFS won't take nearly that long! :-)

Greg
frmky is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
setting up wakeon lan attempt 4 wildrabbitt Hardware 0 2016-05-22 17:22
Factorization attempt for a c110 regards Odd Multi-Perfect Numbers jchein1 Factoring 60 2006-11-25 19:38
Idea about 10,000,000 digit attempt. jasong Programming 4 2005-11-29 22:24
Factorization attempt for a c214 regards Odd Perfect Numbers jchein1 Factoring 14 2005-10-15 20:01
Factorization attempt to a c163 - a new Odd Perfect Number roadblock jchein1 Factoring 30 2005-05-30 14:43

All times are UTC. The time now is 08:12.


Mon Oct 25 08:12:08 UTC 2021 up 94 days, 2:41, 0 users, load averages: 1.30, 1.41, 1.25

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.