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

[Torbjörn Granlund]

"Marco Bodrato" <bodrato at mail.dm.unipi.it> 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
powm.

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.


-- 
Torbjörn
Please encrypt, key id 0xC8601622