🚀 go-pugleaf

Dan Bernstein and I are pleased to announce the record factorization
of the 158 digit number 2^523-1. Its prime factors are p_69 and p_90,
where

p_69 = 160188778313202118610543685368878688932828701136501444932217468039063

and

p_90 = 171417691861249198128317096534322116476165056718630345094896620367860\
       006486977101859504089

The factorization was found using our massively parallel implementation
of the lattice sieve (a variant of the number field sieve). The bulk of
the computation (the sieving) was carried out on two 16384 processor
massively parallel computers, one at Bellcore and one at AT&T Bell Labs,
in a total of approximately 3 weeks CPU time. The matrix elimination
was done on a workstation (two days to reduce a 280000x240000 sparse
matrix to a 94000x94000 dense one) and on the Bellcore massively
parallel machine (5 hours for the dense matrix). The entire factorization
took less than a month real time.

This should be compared with the previous record factorization of a
difficult number, namely 2^512 + 1, which took four months real time on
approximately 700 workstations around the world, together with a
massively parallel computer for the matrix elimination.

We gratefully acknowledge Andrew Odlyzko's generous help in running
our program on the AT&T Bell Labs machine.

Arjen Lenstra