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

Torbjörn Granlund tg at
Mon Dec 16 15:30:32 UTC 2019

paul zimmermann <Paul.Zimmermann at> writes:

  thank you for the benchmark, which shows a clear gain with the popcount
  method when the exponent is sparse, and no regression when it is not.

I believe that the amount of analysis of the exponent we can afford is a
function of the expected computation time.

A popcount adds linear time in the exponent size.  If the base and
modular argument are small enough, that will add noticeable overhead.

We might want to do a more sophisticated analysis of the exponent when
the base and modular are are large enough.

Please encrypt, key id 0xC8601622

More information about the gmp-devel mailing list