GMP used during 3 and a half years to solve MIT's LCS35

Bernard Fabrot bfabrot at
Fri May 10 17:48:24 UTC 2019

These are amazing datapoints!

It's very interesting because the numbers from GMP 2.0.2 on hardware from
1999 are, if I'm not making big mistakes, within 10% of the original
problem parameters, which someone from RSA (not Rivest) estimated (3300
sq/s @ 500 Mhz, Rivest picked 3000 sq/s and your numbers "clock-speed
adjusted to 500 Mhz" give 3600 sq/s).

So the original estimate in 1999 seemed quite good. But the performance
increase got underestimated: they tabled on 35 years before finding a
solution while a modern CPU with GMP can do it in I'd say 2 years (I did it
in 3.3 years with not even the most efficient calls, on a Skylake at 4.0
Ghz: this is not the fastest).

My take is that: as explained in this thread the 32 -> 64 bits thread
brought a huge speed increase, the algorithms/implementation got better,
the cpu cycles needed for some instructions went down so even if the 10 Ghz
expected in the problem weren't reached, it's still basically 10x compared
to the original problem prediction.

Thanks a huge lot to everyone, not only for GMP but also for all the help


More information about the gmp-discuss mailing list