GMP used during 3 and a half years to solve MIT's LCS35
Torbjörn Granlund
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
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
More information about the gmp-discuss
mailing list