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

[Niall Emmart]

Maybe the fastest approach would be to use the low level routines to do repeated squaring in Montgomery space.

________________________________
From: gmp-discuss <gmp-discuss-bounces at gmplib.org> on behalf of paul zimmermann <Paul.Zimmermann at inria.fr>
Sent: Wednesday, May 1, 2019 2:22 AM
To: Marco Bodrato
Cc: gmp-discuss at gmplib.org; bernard at fabrot.com
Subject: Re: GMP used during 3 and a half years to solve MIT's LCS35

       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
_______________________________________________
gmp-discuss mailing list
gmp-discuss at gmplib.org
https://gmplib.org/mailman/listinfo/gmp-discuss