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

[Marco Bodrato]

Pardon, a note on notation.

Il 2019-05-01 08:57 Marco Bodrato ha scritto:
> 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.

In the message above, "n" was the modulus.
In the following observations, "n" is the exponent.

Sorry for mixing the two notations from two different messages without 
clarifying that.

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

By the way I tested my claim (not using 2^2048 as an exponent, but 
2^4194304) with the following small program, on two quite different 
machines and simply measured execution with "time"... powm resulted from 
5% to 30% faster than the direct mul+mod loop. The results may be 
different with different version of GMP, different CPUs/architectures, 
different operand sizes...

--------8<-------
#include <stdio.h>
#include <gmp.h>

int
main (int argc, char **argv)
{
   mpz_t a, b, n;
   int i = 1L << 22;

   mpz_inits (a, b, n, NULL);

   mpz_set_str (n, "123456789123456789", 10);
   mpz_set_str (a, "987654321987654321", 10);
   mpz_setbit (n, 2047); mpz_setbit (n, 2030);
   mpz_setbit (a, 2040);

   if (argc > 1) {
     printf ("do {mul mod} while\n");
     do {
       mpz_mul (b, a, a);
       mpz_mod (a, b, n);
     } while (--i);
   } else {
     mpz_setbit (b, i);
     printf ("powm\n");
     mpz_powm (a, a, b, n);
   }
   printf ("%lu\n", mpz_get_ui (a));
   mpz_clears (a, b, n, NULL);
}
--------8<-------


Ĝis,
m