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

[William Galway]

Thanks Marco.  My installation of GMP is quite outdated so I'll make sure
to bring it up to date -- although I may need to ask for guidance on how to
install the patch.

Once I've done some benchmarks I'll try to report my results to the mailing
list.

-- Regards, Will


On Fri, Mar 20, 2020 at 5:33 PM Marco Bodrato <bodrato at mail.dm.unipi.it>
wrote:

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