Factorization of 2,761-. c189 = p69 * p 121

[xilman]

I posted this to the nfsnet-announce list a few moments ago.

Originally Posted by paul@nfsnet.org

Some of you will already have seen the initial announcement of the
factorization of 2^761-1 into its two prime factors of 69 and 121
decimal digits. Here is a rather more complete report.

The NFSNET admin team decided last year to complete the base-2
Cunningham tables to an index of at least 768, which is a round number
in binary. The penultimate integer was 2,761-1, also known as
2,761-.c189, aka M761. Some factors were already known; we were
completing the 189-digit co-factor.

We used the special number field sieve, with polynomials x^6-2 and
x-2^127, which share a root 2^127 mod M761. We sieved with factor base
primes up to 50M on each side and allowed up to 2 large primes smaller
than 1G. We began sieving on 2005 September 19 and thought we had
finished by November 12. Indeed, at that point we had enough relations
(about 80M) collected to let us complete the factorization but the
matrix would have been very large, perhaps intractably so. A small
number of machines continued sieving after the bulk of the NFSNET
clients had moved on to 2^764+1. Their relatively small but very
important additional work allowed us to build a reasonable matrix.

Richard Wackerbarth called a halt to the sieving when we had
87357332 unique relations. He removed the singletons, reducing the set
to 55294250, but ran into problems when trying to filter any further.
Essentially, he ran out of (virtual) memory on his 2GB (physical) memory
Mac. I copied them over to Cambridge on December 23rd and managed to
make progress on a 2GB Sun. The filtering process just fit into that
machine (indicating that the two operating systems have somewhat
different virtual memory subsystems --- not too surprising) and
eventually boiled down the relations to the point where we could build a
matrix with 6157472 rows, 6160740 columns and a total weight of
378398239 set bits.

That matrix was processed on my Athlon-64 3500+, which has a clock speed
of 2.2GHz and 2.5GB RAM. The linear algebra took 444.6 hours and used
1866MB of active virtual memory. Once completed, the square root phase
took under 3 hours to find the factors. The first dependency produced
only the trivial factorization but the second revealed:

Probable prime factor 1 has 121 digits:
2107048624990017888277673772279371580792509894029946695224069650783071896637390038709062589566791754603427516344308169913
Probable prime factor 2 has 69 digits:
280230266918608239805810556544655376723809198780890337110755962385407


Our thanks to everyone who contributed to this achievement. We could
not have done it without the work of many many people.


Paul Leyland, for the NFSNET admin team.

paul

[R.D. Silverman]

Originally Posted by xilman

I posted this to the nfsnet-announce list a few moments ago.

<snip>

paul

Very Nice. Now there are only 3 numbers of the form 2^n -1 with n < 815
left unfactored and Kleinjung is doing 2,793-.

Any volunteers for 2,787- and 2,799-?

I will do 2,815- when I finish 2,820+ (needs ~1 more week of sieving)

[hlaiho]

2^797+1, c205 is now c150, when Bruce Dodson has found today 55-digit factor
3716911716373158932595690775277458436562439413950537497. GNFS target?

I think it's time to post here Sam's current reserved numbers list, when M739 and M761
are now completely factored.

Heikki

[xilman]

Originally Posted by hlaiho

2^797+1, c205 is now c150, when Bruce Dodson has found today 55-digit factor
3716911716373158932595690775277458436562439413950537497. GNFS target?

Now that's not a bad idea! Thanks.

I haven't seen Bruce's announcement of that one yet, either directly or via a third party. This is strange. I generally get to hear about them quite quickly.

Paul