Computing A mod d (for small odd d without division and multiplication)

[marco.bodrato at tutanota.com]

Ciao,

8 mar 2026, 19:59 da tg at gmplib.org:

> This algorithm is useful mainly for quite small d, or more precisely
> when the number of limbs in A >> d.  This is because the rems[] vector
> will else potentially be large and expensive to compute.
>
d is odd, right? So it's a product of odd primes.
For every odd prime p, the order of Z/pZ* is even, and the size of rems[] is the size of the order of 2^GMP_NUMB_BITS modulo d.
If GMP_NUMB_BITS is even (as usual), 2^GMP_NUMB_BITS is a square, and it can not be a generator.

I mean,
mp_limbs_t rems [d-GMP_NUMB_BITS%2 >> 1-GMP_NUMB_BITS%2];
should be large enough.


> There are numbers d for which B^k = 1 for any k for our common B of 2^32
> and 2^64.  Examples are 3, 5, 15, 17, 51, 85, 255, and 257.  These will
> just use rems[0], and many other d values will have a "cycle length" of
> just 3.
>
The divisors of 2^(GMP_NUMB_BITS)-1, right?
? #divisors(2^(64*3)-1)
49152

Ĝis,
m