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

Torbjörn Granlund tg at
Wed May 1 20:31:24 UTC 2019

"Marco Bodrato" <bodrato at> writes:

  That's why a few weeks ago on this same list I suggested:
  "What about even sparser exponents? Should we use 2*popcount(n) instead of
  size_in_bits(n) to estimate the best window size? They should be almost
  equivalent on average."

There are several possible optimisations still to be considered for

We could start by counting the exponent low bits and then square the
base that many times.

I.e, if the exponent e = 2^a*e' we could compute r = b^e mod m as b' =
b^(2^a) mod m, then r = b'^e' mod m.

The table size could now be determined from log2(e').

We could even postpone the table generations for the current sliding
window algorithm until we'd reach the 2nd most significant bit.  That'd
make the table size even more accurately tuned.

Please encrypt, key id 0xC8601622

More information about the gmp-discuss mailing list