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

paul zimmermann Paul.Zimmermann at inria.fr
Wed May 1 06:22:44 UTC 2019


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

Paul


More information about the gmp-discuss mailing list