GMP used during 3 and a half years to solve MIT's LCS35
nemmart at hotmail.com
Wed May 1 06:43:11 UTC 2019
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
> On the other side
> mpz_powm (a, a, 2^2048, n);
> should be faster than 2048 times
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.
gmp-discuss mailing list
gmp-discuss at gmplib.org
More information about the gmp-discuss