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

[Marco Bodrato]

Ciao Paul,

Il 2020-03-21 07:06 paul zimmermann ha scritto:
> Dear Will,
> 
>> > 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$

> Then for computing 2^n mod m, if e is the number of bits of n, you need
> basically e-1 squarings mod m, plus on average e/2 multiplications by 
> 2,
> but those will be inexpensive: just multiply by 2 and subtract m if 
> needed.

Some initial squarings can be saved, because a common initial power 2^n' 
<= 2^63 can be shared for every m.

It is possible to do very slightly better. But the possible improvement 
is so small that it is not really worth it.

If m fits in a register, then squaring or multiplying mod m have the 
same cost.
This means that in some very special circumstances a slightly better 
"Addition–chain" may exist.
E.e. To compute 2^1071 it is very slightly better to compute 
(2^63)^(2^4)*(2^63),
than ((((2^33)^4*2)^2*2)^2*2)^2*2.

But one can only find a sequence that saves  some of the inexpensive 
multiplications by 2.

> Now for the squarings, the best is to use redc: since m < 2^64, 
> precompute

There is a portion of code in the current development library for the 
very special case base=2 and size of m limited to one limb:

https://gmplib.org/repo/gmp/file/a1bfb342ebe9/mpn/generic/powm.c#l268

If you have further suggestions, I'll be happy to know !-)

Ĝis,
m

-- 
http://bodrato.it/