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

[marco.bodrato at tutanota.com]

Ciao Niels,

10 mar 2026, 08:01 da nisse at lysator.liu.se:

> marco.bodrato at tutanota.com writes:
>
>> Let's take some examples:
>>  - 47, the order of 2^64 mod 47 is 23, and also the order of 2 is 23;
>>    this means that 23 divides 2^(23*2)-1;
>>
>
> You mean that _47_ divides 2^(23*2)-1, right? It appears to also divide
> 2^23 - 1.
>
Yes, correct. I think that it's easier to compute the reminder 2^k-1 with k between
the half and the full GMP_NUMB_BITS, instead of smaller k.


> If I try to rephrase what you are saying: Whenever the order of 2 mod d
> is "small" (so that the needed "rem" array is small), then d divides 2^k
> - 1 for a small k, and reducing mod that larger modulo could then be
> done with shifts and adds rather than multiplies.
>
Correct. And that's how we usually use mpn_mod_34lsub1.But we have to remember that the vice-versa is not always true.
The needed "rem" array can be small also if the order of 2 mod d is not so small.
E.g. the order of 2 mod 769 is 384,
this means a "rem" array of 6 limbs of size 64-bit, or 12 limbs of size 32-bit.
The code proposed by Torbjörn basically computes the limbs of the
residue mod 2^384-1, limb by limb, and it updates the corresponding residue
mod d accordingly. Computing the full 6-12 limbs residue could be not as fast.

> Some off-the-top-of-my-head observations:
>
> There should be a similar trick for d dividing 2^k + 1.
>
Yes, but it is more complex, and 2^k + 1 divides 2^{2k} - 1.

Ĝis,
m