GMP used during 3 and a half years to solve MIT's LCS35
tg at gmplib.org
Wed May 1 20:31:24 UTC 2019
"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
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