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

[marco.bodrato at tutanota.com]

Ciao Niels,

9 mar 2026, 16:47 da nisse at lysator.liu.se:

> Torbjörn Granlund <tg at gmplib.org> writes:
>
>> 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.
>>
>
> I'm a bit rust on group/number theory, but the order of the
> multiplicative group mod d is phi(d), and the possible (and the likely)
> orders of 2 modulo d are determined by the prime factors of phi(d). And
> since B is a power of two, factors of two in the order (or in phi(d))
> don't matter much.
>

Exact.


> And small numbers seem rather common, as you observed. In pari/gp, I get
>

Yes, of course if d is small, the order can not be large, and since, as you said,
the factors 2 are always removed from the Euler-phi of d, it always is smaller,
by at least a factor 2.


> ? forstep(n = 1, 101, 2, print(n, "\t", znorder(Mod(2^64, n)), "\t", factor(eulerphi(n))))
>
> Worst case is (d - 1)/2, possible for prime d, as I think Marco said
>

Right.

But I'd also print the order of 2 modulo d.

? forstep(d = 1, 101, 2, print(d, "\t", znorder(Mod(2^64, d)), "\t", znorder(Mod(2, d))))
1       1       1                                                                                                        
3       1       2
5       1       4
7       3       3
9       3       6
11      5       10
13      3       12
15      1       4
17      1       8
19      9       18
21      3       6
23      11      11
25      5       20
27      9       18
29      7       28
31      5       5
33      5       10
35      3       12
37      9       36
39      3       12
41      5       20
43      7       14
45      3       12
47      23      23
49      21      21
51      1       8
53      13      52
55      5       20
57      9       18
59      29      58
61      15      60
63      3       6
65      3       12
67      33      66
69      11      22
71      35      35
73      9       9
75      5       20
77      15      30
79      39      39
81      27      54
83      41      82
85      1       8
87      7       28
89      11      11
91      3       12
93      5       10
95      9       36
97      3       48
99      15      30
101     25      100

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;
   should we really perform a 23-passes computation with 23 multiplications and modulus,
   or should we better reduce the number modulo 2^46-1 with some bit trickery,
   and perform a single last step mod 47?
   With 46<64 .
 - 83, the order of 2^64 mod 83 is 41, and the order of 2 is 82;
   should we really perform a 41-passes computation with a few multiplications for each pass,
   or should we better reduce the number modulo 2^82-1 with some bit trickery,
   and perform a single last step mod 83?
   With 64<82<128 .
8 mar 2026, 19:59 da tg at gmplib.org:

> (If we use the "nails feature of GMP, B = 2^60 is interesting, as now
> lots of d give short cycles.)
>
It should not be too difficult to implement a function computing at first the modulo mod 2^60-1 or 2^120-1 and then the modulo of the 1 or 2 limbs residue.
> (but for some reason, my email client doesn't like Marco's recent
> messages).
>

Could you read them only partially?
Unfortunately, I do not have many options I can play with on this server.

Ĝis,
mb