137!+1 C159 finished by GNFS
 

The complete factorization of 137!+1 is:

7321 (p4, Paul Leyland) *
213749061182918881280504944217119 (p33, David Miller, ECM, 1999-11-14) *
28662735231819784615664987397230579783137 (p41, Sean A. Irvine, ECM 2005-07-19) *
224369312643440739439186586733601848833986009164493892003691007743395367816053 (p78) *
498118135871015829455868415732484005093448444912305410621425821767779074935530459 (p81)

By far the most difficult part of this factorization was splitting the
C159 (526 bits) comprised of the two largest factors. The computation
was performed using the Bahr/Franke/Kleinjung implementation of GNFS
with the computation resources of Reel Two. The entire computation
took 5 months calendar time, although this would have less if two
power failures had not occurred. To the best of my knowledge this
ranks as the 7th hardest general factorization and the p78 is largest
known penultimate factor of n!+/-1.

Polynomial selection was performed using the method of Kleinjung:

X5 441480
X4 -13790614826344
X3 4416198744416538077
X2 155387218898977908242215
X1 -2179338375403953462829904271901
X0 579111459871494028246728783033774745
Y1 122026256907621821
Y0 -3024663496420147724790465262058

Lattice sieving was applied to nearly all special-q in the range 16e6
to 120e6 with factor base bounds 10e6 and 16e6. The bounds for the
large primes were 2^32. Sieving yielded 185e6 relations, of which 31e6
surived the uniqueness test. Sieving took 80 days on a variety of
machines with combined CPU power of just over 20 GHz (although this
was sustained throughout the entire period of sieving).

The resulting matrix had 6.4e6 rows and columns and took 32 days to
solve with block Lanczos on a single 3 GHz Pentium 4 with 3.5 GB of
RAM; the matrix itself occupied about 2.4 GB of RAM. (Note this
machine was used for various other tasks during the reduction). Three
earlier attempts to reduce the matrix failed due to two separate power
failures. In particular, a Java port of the Franke's Lanczos code was
running at about 60% of the speed of the C version on a dual 1.8 GHz
Opteron. It would seem adding some checkpointing code like the CWI
suite would be a good idea.

The factor was found on the 2nd and 3rd linear dependencies examined.

Thanks to Richard Littin and Jonathan Purvis for donating CPU time on
their desktops for sieving; and to Stuart Inglis for helping keep the
machines up and for providing disk space. For futher details on efforts
to factor n!+/-1 see Andrew Walker's page:

[url]http://www.uow.edu.au/%7Eajw01/ecm/curves.html[/url]

Sean A. Irvine

Congratulations!

Sean,
I'm a noob and in the process of learning how to set up GGNFS to help me factor a C155. I'm wondering if you or someone else could recommend parameters for the sieving process. GGNFS only comes with defaults up to C126 and even those are dubios. I plan on using the Bahr/Franke/Kleinjung lattice siever.

Here are the defaults that come with ggnfs for C126:

type,digits,deg,maxs1,maxskew,goodScore,efrac,j0,j1,eStepSize,maxTime,rlim,alim,lpbr,lpba,mfbr,mfba,rlambda,alambda,qintsize,A,B
gnfs,126,5,67,2000,5.0e-6,0.28,250,20,50000,3600,5400000,5400000,27,27,51,51,2.5,2.5,60000,4000000,300

[QUOTE=UpooPoo]Sean,
I'm a noob and in the process of learning how to set up GGNFS to help me factor a C155. I'm wondering if you or someone else could recommend parameters for the sieving process. GGNFS only comes with defaults up to C126 and even those are dubios. I plan on using the Bahr/Franke/Kleinjung lattice siever.
[/QUOTE]
GGNFS cannot handle the postprocessing for a factorization that big.

jasonp

[QUOTE=UpooPoo]Sean,
I'm a noob and in the process of learning how to set up GGNFS to help me factor a C155. I'm wondering if you or someone else could recommend parameters for the sieving process. GGNFS only comes with defaults up to C126 and even those are dubios. I plan on using the Bahr/Franke/Kleinjung lattice siever.

Here are the defaults that come with ggnfs for C126:

type,digits,deg,maxs1,maxskew,goodScore,efrac,j0,j1,eStepSize,maxTime,rlim,alim,lpbr,lpba,mfbr,mfba,rlambda,alambda,qintsize,A,B
gnfs,126,5,67,2000,5.0e-6,0.28,250,20,50000,3600,5400000,5400000,27,27,51,51,2.5,2.5,60000,4000000,300[/QUOTE]

I'm probably not the best person to answer, since I tend to be rather lazy about selecting parameters. The "best" parameters depend on lots of things like your number, your polynomials, the skewness etc., and your computational resources.
Ideally, you should try a number of variations with trial sieving to see what will work best.

Have you done many other GNFS factorizations? If not, start with something much smaller that GGNFS is known to handle. Also, are you certain your number is not amenable to SNFS and have you expended an appropriate amount of ECM effort. It might help if you can post more detail about your number of interest.

[QUOTE=UpooPoo]factor a C155.[/QUOTE]

A C155 always sounds suspiciously like "512 bit RSA key"...

[QUOTE=jasonp]GGNFS cannot handle the postprocessing for a factorization that big.

jasonp[/QUOTE]

That's fine, we are actually using our own code for postprocessing atm :-).

[QUOTE=Mystwalker]
A C155 always sounds suspiciously like "512 bit RSA key"...
[/QUOTE]

Actually this C155 is an RSA-512 key. I and a few other college students are working on parallelizing the post-processing phase. We started with matrices from some smaller numbers and have had positive performance increases. Recently we have gained access to a much larger cluster and we want to see how the performance scales over larger matrices. However, we haven't been very picky about parameters ourselves. Processing time is an issue with scheduling this cluster so I wanted to make sure we are a bit more careful in our selection.

[QUOTE=UpooPoo]That's fine, we are actually using our own code for postprocessing atm :-).
[/QUOTE]
Great! The more software out there that can do NFS postprocessing, the better.

jasonp

[QUOTE=jasonp]Great! The more software out there that can do NFS postprocessing, the better.

jasonp[/QUOTE]

I almost agree, but I'd make it "the better software out there ..., the better". It seems that a lot of people are writing NFS software these days, and mostly are solving the same tasks over and over again. Personally, I'd rather see a lot of people get behind *one* free project (ggnfs?) and improve that to the point where it is ready for large-scale factorisations.

Just my 2 cents...
Alex

[QUOTE=akruppa]I almost agree, but I'd make it "the better software out there ..., the better". It seems that a lot of people are writing NFS software these days, and mostly are solving the same tasks over and over again. Personally, I'd rather see a lot of people get behind *one* free project (ggnfs?) and improve that to the point where it is ready for large-scale factorisations.
[/QUOTE]

I completely agree, it would be great if everyone could pool their efforts into a single free implementation, and GGNFS is the most logical choice. However, over time I've become dissatisfied with GGNFS.

<rant>
The code has become very messy, there's a big infrastructure needed for portability that needs extensive tweaking (and that takes up most of the developers' time), and much of the core (poly generation, factor base stuff, lattice sieving) is mostly lifted from Franke/Kleinjung/Bahr, and is badly written to the point of being unworkable except to fix bugs.
</rant>

For a while after I started adding NFS code to msieve, I felt pretty guilty that I was putting effort into reinventing the wheel. Over the last few months I realized several things: first, all of this is hobby stuff, and if working on this hobby stuff is continually frustrating then you need another hobby. Second, figuring out how all the pieces work is much easier when you're responsible for all those pieces. Finally, an implementation from scratch gives opportunities that just do not exist when working on an existing codebase.

For example, the factor base generator in msieve started from Chris' original code in GGNFS, but I've modified and optimized it to the point where the current version bears essentially no resemblance, and is twice as fast as the Bahr factor base code that GGNFS currently uses. GGNFS' line siever was the first line siever I ever wrote, and it sucks compared to the one in msieve. If I had only tweaked that first line siever, the result today would still suck.

I still think there's room to eventually go back and fold my work into GGNFS, but just do not want to deal with the hassle of doing so. Basically I want better code out there, and if that means eveyone will have to wait longer to factor a C155, then so be it.

jasonp

[QUOTE=jasonp]first, all of this is hobby stuff[/QUOTE]
that's the main point for me. I started my NFS implementation long before
GGNFS appeared, so I didn't feel I was wasting time reinventing stuff - there was very little available unless you got hold of CWI's software. Today it could be argued that my implementation is redundant, but it's still worth it to me to try and improve it, and if anyone else finds it useful then that's just a bonus.
And I agree with Bob Silverman that it's much more satisfying to write your own software than to just run someone else's, even if I never manage to break any factorisation records.

Chris