The factors of M757

[xilman]

Less than an hour ago, this appeared in a window on my workstation:

Original number had 213 digits:
13752482059206622184516110319504078523243712131392474512308817064826925562339964
32157638160851187604400926673771338223960482503058695991668529363734439720161301
88795692624533425489999025582244971978683298161118487
Probable prime factor 1 has 79 digits:
5722137022002067824248227975095857749151312827809388406962346253182128916964593
Probable prime factor 2 has 134 digits:
24033821640983508088736273403005965446689002356344332130565066643193813901119771
090424269412054543072714914742665677774247325292327559


Back on 31st August, the NFSNET clients changed over to working on the 2_757M project. 124 days later, we have the factors above. A full announcement will be made later this week, but here's an overview of what we did.

The number 2,757- was chosen because it's both a Cunningham number and a prime-index Mersenne number. The composite cofactor had 213 digits but because we used SNFS and couldn't exploit the known factorization, we had to factor the full 228 digits of 2^757-1.

The sieving phase began on 31st August and finished on 13th October, using 13745WU of sieving effort. The filtering and merging of the 76.7M relations began the same day and finished on 28th October with the production of a matrix with slightly over 7.522 million rows and columns.

Linear algebra on that matrix took 32 days 16 hours total elapsed time, with 26d 11h recorded in the many log files along the way. The 6d 5h discrepancy is accounted for by time lost to crashes and to scheduled downtime on the cluster at Microsoft Research in Cambridge. The actual cpu time was about 7600 hours (i.e. 30 cpus at about 40% loading).

We were fortunate in that the factors were found on the first dependency, which took 157 minutes on a 2.53GHz P4 machine.

This was the hardest factorization yet completed by NFSNET, just pipping 10,227- which completed three months ago. The current project, 2,811-, is even harder but is still running along smoothly.

As always, thanks are due to all the people who contributed their machine cycles and their enthusiasm. Further, we acknowledge the contribution made by CWI in providing us with their NFS code for us to use and to redistribute in a modified form.


Paul

[ewmayer]

Congratulations on the new latest factorization!

It's obvious that neither the p-1 nor p+1 method could have found the p79, since:

p79 - 1 = 2^4.13.757.1229897.54286614780461303.1380765008073205793.394201037959710813849206239443089

p79 + 1 =
2.3^2.19.47.7432993.2324637841.185510276424547.111057345764905462413172936544652769659794471

[ewmayer]

p.s.: To those who may not closely follow such factorizations, note that the above inout number in Paul's message is not 2^757 - 1, it's that number with the two easily found small factors (9815263 and 561595591) divided out.

But - doesn't SNFS usually work on the undivided number, even if leaving the small factors in makes for a larger (but algebraically suitable for SNFS) form? Paul?

[Wacky]

Originally posted by ewmayer
But - doesn't SNFS usually work on the undivided number, even if leaving the small factors in makes for a larger (but algebraically suitable for SNFS) form? Paul?

The polynomials are chosen on the basis of the simple form of the undivided number. However, all of the modular arithmetic is done on the basis of the smaller composite factor.

[ewmayer]

Originally posted by Wacky
The polynomials are chosen on the basis of the simple form of the undivided number. However, all of the modular arithmetic is done on the basis of the smaller composite factor.

For numbers of special form like the Mersennes and Fermats, wouldn't it be faster to do modular arithmetic using the Crandall/Fagin DWTand the full number?

[xilman]

Originally posted by ewmayer
For numbers of special form like the Mersennes and Fermats, wouldn't it be faster to do modular arithmetic using the Crandall/Fagin DWTand the full number?

Yes but.

The but is that only a trivial amount of arithmetic is done modulo N. Virtually all the computation takes place in the siever where the limits are largely set by memory access speeds and, as a secondary consideration, single and double precision integer arithmetic.

To answer the original question: we were unable to exploit the factors of M757 and had to factor the full 2^757-1, apart from the entirely negligible speedup already noted.

Sometimes it's possible to exploit known factors. If more than a third or so of the number has been factored (from c200 to c130, for instance) it will usually be quicker to factor the small cofactor with GNFS than the entire number with SNFS. Sometimes algebraic factorizations can be exploited. For example, we would not factor 2^802+1 itself but factor (2^401 + 2^201 + 1) and (2^401 - 2^201 + 1) individually, since each of those quantities can be represented as a simple polynomial with a known root.


Paul

[ewmayer]

Thanks for the clarification, Paul - that was how I understood the SNFS algorithm to work.

And of course with the prime-exponent Mersennes, algebraic factors aren't an issue.