Everybody knows that in order to calculate a+b (mod m) or a*b
(mod m), we can calculate a (mod m) and b (mod m) and then do the operation.
But if we have 2a (mod m) with a>m, we cant reduce a (mod m) and
then calculate 2a (mod m) (mod m).
So, the idea is to introduce such modulos in base b, for wich we have always:
|
ba = ba (mod m) (mod m) for all values of a (If a (mod m)=0, we'll take m as exponent, not zero) |
These numbers aren't so rare. Here is a table of the first twenty magicmodulos in the first bases :
|
n°
|
Base 2
|
Base 3
|
Base 4
|
Base 5
|
Base 6
|
Base 7
|
Base 8
|
| 1 |
1
|
1
|
1
|
1
|
1
|
1
|
1
|
| 2 |
2
|
2
|
2
|
2
|
2
|
2
|
2
|
| 3 |
6
|
3
|
3
|
4
|
3
|
3
|
4
|
| 4 |
18
|
4
|
4
|
5
|
5
|
4
|
6
|
| 5 |
42
|
6
|
6
|
6
|
6
|
6
|
7
|
| 6 |
54
|
8
|
9
|
8
|
10
|
7
|
8
|
| 7 |
126
|
12
|
10
|
10
|
14
|
8
|
12
|
| 8 |
162
|
16
|
12
|
12
|
15
|
9
|
14
|
| 9 |
294
|
20
|
18
|
16
|
25
|
12
|
18
|
| 10 |
342
|
24
|
20
|
18
|
30
|
14
|
20
|
| 11 |
378
|
32
|
21
|
20
|
42
|
16
|
24
|
| 12 |
486
|
39
|
27
|
24
|
50
|
18
|
28
|
| 13 |
882
|
40
|
30
|
30
|
70
|
20
|
36
|
| 14 |
1026
|
42
|
36
|
32
|
75
|
21
|
40
|
| 15 |
1134
|
48
|
42
|
36
|
98
|
24
|
42
|
| 16 |
1314
|
60
|
50
|
40
|
110
|
27
|
49
|
| 17 |
1458
|
64
|
54
|
42
|
125
|
28
|
52
|
| 18 |
1806
|
78
|
60
|
48
|
129
|
32
|
54
|
| 19 |
2058
|
80
|
63
|
52
|
150
|
36
|
56
|
| 20 |
2394
|
84
|
68
|
54
|
186
|
40
|
60
|
Remark : the number of magicmodulos asymptotically grows with the size of the base.
But, how can we find such numbers ? It's quite easy ; here is their characteristic property :
|
bm+1 (mod m) = b (mod m)
|
Be careful : don't divide each side by b because b and m aren't necessarily relatively prime.
If the precedent property is true, it can be easily shown by recurrence that :
|
ba = ba (mod m) (mod m) for
all values of a (a (mod m) <> 0)
|
Example : Because 1458 is a magicmodulo in base 2, we can easily calculate 24400 (mod 1458) : 4400 = 26 (mod 1458) so 24400 (mod 1458) = 226 (mod 1458) = 40 (mod 1458) and that's all !
Most of the magicmodulos can be predicted. These numbers are magicmodulo in base b :
- every divisor of b (even 1 and b) (proved)
- b*(b+1)n for all values of n (proved)
- b*(b-1)n for all values of n (not proved)
- (b-1)n for all values of n (not proved)
- (b-1)*m if m is magicmodulo in base b (not proved)
- (b+1)*m if m>1 is magicmodulo in base b (not proved)
- bm+1-b if m is magicmodulo in base b (proved)
- u*(b-1) with u= 1,2,6,42 or 1806 (not proved)
These numbers u aren't random : I call them universal magicmodulo because they are magicmodulo in all the bases (proved). I think it exists another bigger universal magicmodulo but it must be >20000000 (tested on my computer). So if you find one of them, please email-me !
The magicmodulos can be used in order to speed up the calculation of binary exponentiations (modpow / powmod) modulo N. Perhaps this would accelerate pseudo-primality tests...
|
Prime numbers + pseudoprimes
|
Magicmodulos
|
|
| Characteristic property |
an = a (mod n)
|
an+1 = a (mod n)
|
| "Fabrication" of a bigger |
n --> (bn-1)/(b-1) (pseudoprime in base
b)
|
n --> bn+1-b (in base b)
|
To be continued...