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

[Marco Bodrato]

Ciao Paul,

Il Mer, 1 Maggio 2019 8:22 am, paul zimmermann ha scritto:
>        Dear Marco,
>
>> On the other side
>>        mpz_powm (a, a, 2^2048, n);
>> should be faster than 2048 times
>>        mpz_mul(b,a,a);
>>        mpz_mod(a,b,n);
>
> not sure, since the base-2^k exponentiation will not help in that case

I agree, but "REDC form" should help.

> (either sliding window or not), since it saves multiplications,
> and in this case we have squarings only.

> Moreover, the base-2^k exponentiation will precompute a^i for i < 2^k,
> which will give some small overhead.

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."

[ https://gmplib.org/list-archives/gmp-discuss/2019-April/006310.html ]

If we'd use popcount(n) to choose the "k" for "base-2^k", the
squaring-only cases like this one would not pre-compute any "a^i".

Ĝis,
m

-- 
http://bodrato.it/papers/