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

[William Galway]

For the size of n that I'm most interested in, say in the 1000 to 10000
range, it is significantly faster to pre-calculate 2^n once and then find
the remainder for many values of m -- perhaps 5 times faster on my
particular architecture ....  (I'm using mpz_fdiv_ui() rather than
mpz_mod().)  It's clear that it's FAST to divide by a single-limb into a
dividend with a size of a few tens of limbs.

I'll try to submit some code to demonstrate, but right now my sample code
(which worked earlier) is generating floating-point exceptions.  (Surely
this is a bug in GMP -- rather than an oversight on my part.  Just joking.)

-- Regards, Will


On Sat, Mar 21, 2020 at 1:24 PM Pedro Gimeno <gmpdiscuss at formauri.es> wrote:

> William Galway wrote on 2020-03-18 19:53:
> >   I've been considering this computation off-and-on for many years, so my
> > apologies if I'm repeating a previous post.
> >
> > I'd like to calculate $2^n$ modulo $m$ with $n$ fixed
>
> Out of curiosity, how much faster is mpz_powm vs just mpz_mod on the
> pre-calculated 2^n?
>