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

[paul zimmermann]

       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$

I thought a little about your problem and didn't see a way to do better than
computing 2^n mod m independently for each m. Assume for simplicity you have
two values of m, m1 and m2. You can of course first compute 2^n mod (m1*m2),
and then reduce the result mod m1 and mod m2, but the modular exponentiation
mod (m1*m2) will be at least twice as expensive as mod m1 and mod m2.

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.

Now for the squarings, the best is to use redc: since m < 2^64, precompute
u = -1/m mod 2^64, then for x < m, compute x*x = h*2^64+l using umul_ppmm,
then v = l*u mod 2^64 (v = l*u in C), l*v = hh*2^64+ll using umul_ppmm
(or directly hh = mulx(l,v) if mulx is available), then l+ll should be 0
mod 2^64 and your redc product is (h+hh) mod m, plus the carry from l+ll.

Hope this helps,
Paul