Any advice on computing 2^n modulo m for MANY values of m, m is 64-bit, n is <10000 say

[Marco Bodrato]

Ciao,

Il 2020-03-18 19:53 William Galway ha scritto:
> I'd like to calculate $2^n$ modulo $m$ with $n$ fixed and no more than
> 32-bits and with $m$ running over many 64-bit values.  The values of 
> $m$

> The obvious candidate might be mpz_powm_ui(rslt, 2, n, m), with the
> arguments cast to the proper types, but surely one could do better with 
> the

If the exponent is large, the current implementation of mpz_powm_ui is 
only a wrapper for the more sophisticated mpz_powm. The latter was 
recently improved with a special implementation for the case base=2, 
exactly the case you need.
https://gmplib.org/repo/gmp/rev/63e53ddfd210

> arguments restricted to the values I'll use.  I'd be willing to 
> hand-code
> the function in assembly language,

> I'd also be willing to let a computer spend a day or so 
> generating/preprocessing

> I've run a few benchmarks using various methods (like mpz_powm_ui),
> but I feel that I could do much better.

If you want, you may try with the new patched library. But of course GMP 
is a generic library, and specialising a code for the given exponent 
can, for sure, gain even more speed.

Ĝis,
m