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

[Niels Möller]

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.

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

? forstep(n = 1, 101, 2, print(n, "\t", znorder(Mod(2^64, n)), "\t", factor(eulerphi(n))))
1	1	matrix(0,2)
3	1	Mat([2, 1])
5	1	Mat([2, 2])
7	3	[2, 1; 3, 1]
9	3	[2, 1; 3, 1]
11	5	[2, 1; 5, 1]
13	3	[2, 2; 3, 1]
15	1	Mat([2, 3])
17	1	Mat([2, 4])
19	9	[2, 1; 3, 2]
21	3	[2, 2; 3, 1]
23	11	[2, 1; 11, 1]
25	5	[2, 2; 5, 1]
27	9	[2, 1; 3, 2]
29	7	[2, 2; 7, 1]
31	5	[2, 1; 3, 1; 5, 1]
33	5	[2, 2; 5, 1]
35	3	[2, 3; 3, 1]
37	9	[2, 2; 3, 2]
39	3	[2, 3; 3, 1]
41	5	[2, 3; 5, 1]
43	7	[2, 1; 3, 1; 7, 1]
45	3	[2, 3; 3, 1]
47	23	[2, 1; 23, 1]
49	21	[2, 1; 3, 1; 7, 1]
51	1	Mat([2, 5])
53	13	[2, 2; 13, 1]
55	5	[2, 3; 5, 1]
57	9	[2, 2; 3, 2]
59	29	[2, 1; 29, 1]
61	15	[2, 2; 3, 1; 5, 1]
63	3	[2, 2; 3, 2]
65	3	[2, 4; 3, 1]
67	33	[2, 1; 3, 1; 11, 1]
69	11	[2, 2; 11, 1]
71	35	[2, 1; 5, 1; 7, 1]
73	9	[2, 3; 3, 2]
75	5	[2, 3; 5, 1]
77	15	[2, 2; 3, 1; 5, 1]
79	39	[2, 1; 3, 1; 13, 1]
81	27	[2, 1; 3, 3]
83	41	[2, 1; 41, 1]
85	1	Mat([2, 6])
87	7	[2, 3; 7, 1]
89	11	[2, 3; 11, 1]
91	3	[2, 3; 3, 2]
93	5	[2, 2; 3, 1; 5, 1]
95	9	[2, 3; 3, 2]
97	3	[2, 5; 3, 1]
99	15	[2, 2; 3, 1; 5, 1]
101	25	[2, 2; 5, 2]

Worst case is (d - 1)/2, possible for prime d, as I think Marco said
(but for some reason, my email client doesn't like Marco's recent
messages).

Regards,
/Niels

-- 
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.