[nyregurx] modular exponentiation by hand

computing 2^N mod 101 by hand is not difficult.  the algorithm of modular exponentiation by squaring requires squaring a two-digit number, doubling a two-digit number, and long division of a 4-digit number by 101.

101 is prime and 2 is conveniently a generator, so the result can take all values 1 through 100.  it cycles with period 100, so if N is larger than 100, just use its last two digits.  it is nice that all these features coincide.

not sure what this is useful for.  maybe starting with a "less random" two-digit number and turning it into a "more random" two-digit number.  however, there are some ranges in which the output is strongly patterned:

0 Mod(1, 101)
1 Mod(2, 101)
2 Mod(4, 101)
3 Mod(8, 101)
4 Mod(16, 101)
5 Mod(32, 101)
6 Mod(64, 101)

24 Mod(5, 101)
25 Mod(10, 101)
26 Mod(20, 101)
27 Mod(40, 101)
28 Mod(80, 101)

48 Mod(25, 101)
49 Mod(50, 101)
50 Mod(100, 101)
51 Mod(99, 101)
52 Mod(97, 101)
53 Mod(93, 101)
54 Mod(85, 101)
55 Mod(69, 101)
56 Mod(37, 101)

69 Mod(3, 101)
70 Mod(6, 101)
71 Mod(12, 101)
72 Mod(24, 101)
73 Mod(48, 101)
74 Mod(96, 101)
75 Mod(91, 101)
76 Mod(81, 101)
77 Mod(61, 101)
78 Mod(21, 101)
79 Mod(42, 101)

below are all the generators of 101 (the multiplicative group modulo 101).  apart from 2, 50 seems attractive for easy arithmetic.  11 might not be too bad.

? for(n=1, 100, a=Mod(n,101); if((a^20!=1)&&(a^50!=1), print(n)))

2 3 7 8 11 12 15 18 26 27 28 29 34 35 38 40 42 46 48 50 51 53 55 59 61 63 66 67 72 73 74 75 83 86 89 90 93 94 98 99

previously: isprimroot