Exponentiation modulaire

Sous le terme (barbare ?-) d'exponentiation modulaire, se cache en réalité une opération toute simple qui consiste à calculer les puissances successives d'un nombre donné (une base), et d'en calculer ensuite le reste dans sa division par un autre nombre (le premier p).

 

Exemple : Les puissances de 2 modulo 19

Calculons les puissances successives de 2 (en multipliant par 2 à chaque étape), on obtient :

1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, etc.

Le calcul des restes des puissances de 2 dans la division par le premier 19 nous donne une suite répétitive de 18 nombres ( à considérer comme des bases).

1, 2, 4, 8, 16, 13, 7, 14, 9, 18, 17, 15, 11, 3, 6, 12, 5, 10, 1, 2, 4, 8, 16, 13, etc.

Dont seules les bases en liens fournissent des périodes uniques.

1, 2, 4, 8, 16 restent tels quels, 13 est bien le reste de la division de 32 par 19.

l.e double de 13, 26 admet bien 7 pour reste (toujours dans la division par 19) mais pas de période unique,

14 est bien le double de 7, et est égal au reste de la division par 19 de 2 élevé à la puissance 7 ( 2^7 = 128 = 14 + 6*19) etc.

La 18ème base de cette liste, 10 multiplié par 2 donne bien 20 qui admet 1 pour reste dans la division par 19 et le processus recommence.

La plus petite base émettant une période unique est appelée Graine du Premier

La base 2 est la graine de 19.

10 produisant le même graphe en est la base corréllée.

Les bases générant ces périodes invariantes se regroupent par paires, dont le produit admet 1 pour reste dans la division par le premier. Pour 19, ce sont les suivantes :

(2, 10) , (14, 15) , (3, 13)

 

Le calcul suivant étend la propriété de la graine

à générer des périodes uniques

Calculons les nombres premiers avec 18 (n'ayant pas de multiples communs avec lui), ceux-ci sont 6:

1, 5, 7, 11, 13, 17

Et sont aussi nombreux que le nombre des périodes uniques de 19.

Elevons maintenant la graine 2 à ces puissances particulière en gardant le reste dans la division par 19.

Retenons les puissances 1, 5, 7, 11, 13, 17 première avec 18.

1 , 2 , 4 , 8 , 16 , 13 , 7 , 14 , 9 , 18 , 17 , 15 , 11 , 3 , 6 , 12 , 5 , 10

Retenons maintenant les bases situées à ces puissances et répétons le processus. Ces bases en liens sont les seules à générer une période unique pour les fractions de n/19.

Elles sont systématiquement aux rangs 1, 5, 7, 11, 13, 17.

Calcul des puissances de 3 modulo 19 :

1 , 3 , 9 , 8 , 5 , 15 , 7 , 2 , 6 , 18 , 16 , 10 , 11 , 14 , 4 , 12 , 17 , 13

Calcul des puissances de 10 modulo 19 :

1 , 10 , 5 , 12 , 6 , 3 , 11 , 15 , 17 , 18 , 9 , 14 , 7 , 13 , 16 , 8 , 4 , 2

Calcul des puissances de 13 modulo 19 :

1 , 13 , 17 , 12 , 4 , 14 , 11 , 10 , 16 , 18 , 6 , 2 , 7 , 15 , 5 , 8 , 9 , 3

Calcul des puissances de 14 modulo 19 :

1 , 14 , 6 , 8 , 17 , 10 , 7 , 3 , 4 , 18 , 5 , 13 , 11 , 2 , 9 , 12 , 16 , 15

Calcul des puissances de 15 modulo 19 :

1 , 15 , 16 , 12 , 9 , 2 , 11 , 13 , 5 , 18 , 4 , 3 , 7 , 10 , 17 , 8 , 6 , 14

Ainsi, les bases générant une période unique et invariante pour toutes les fractions de n / 19 sont aussi nombreuses que le nombre d'entiers n'ayant pas de diviseurs communs avec 18 et se regroupent en "fratrie" lorsqu' on les élève à ces puissances.

Le calcul suivant résume en quelques tableaux synthétiques le calcul des puissances d'un nombre, lorsqu'on en calcule le reste dans la division par un premier p.

Seules alors les bases en liens génèrent des périodes uniques, elles sont toutes situées sur les même colonnes (puissances).

Modulo 7

Une seule paire (3, 5).

1 2 3 4 5 6
2 4 1 2 4 1
3 2 6 4 5 1
4 2 1 4 2 1
5 4 6 2 3 1
6 1 6 1 6 1

 

Modulo 11

Deux paires (2, 6) et (7, 8)

1
2
3
4
5
6
7
8
9
10
2
4
8
5
10
9
7
3
6
1
3
9
5
4
1
3
9
5
4
1
4
5
9
3
1
4
5
9
3
1
5
3
4
9
1
5
3
4
9
1
6
3
7
9
10
5
8
4
2
1
7
5
2
3
10
4
6
9
8
1
8
9
6
4
10
3
2
5
7
1
9
4
3
5
1
9
4
3
5
1
10
1
10
1
10
1
10
1
10
1

 

Modulo 13

Deux paires (2, 7) et (6, 11)

1
2
3
4
5
6
7
8
9
10
11
12
2
4
8
3
6
12
11
9
5
10
7
1
3
9
1
3
9
1
3
9
1
3
9
1
4
3
12
9
10
1
4
3
12
9
10
1
5
12
8
1
5
12
8
1
5
12
8
1
6
10
8
9
2
12
7
3
5
4
11
1
7
10
5
9
11
12
6
3
8
4
2
1
8
12
5
1
8
12
5
1
8
12
5
1
9
3
1
9
3
1
9
3
1
9
3
1
10
9
12
3
4
1
10
9
12
3
4
1
11
4
5
3
7
12
2
9
8
10
6
1
12
1
12
1
12
1
12
1
12
1
12
1

 

Modulo 17

Quatre paires (3, 6), (5, 7), (10, 12), (11, 14).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
4
8
16
15
13
9
1
2
4
8
16
15
13
9
1
3
9
10
13
5
15
11
16
14
8
7
4
12
2
6
1
4
16
13
1
4
16
13
1
4
16
13
1
4
16
13
1
5
8
6
13
14
2
10
16
12
9
11
4
3
15
7
1
6
2
12
4
7
8
14
16
11
15
5
13
10
9
3
1
7
15
3
4
11
9
12
16
10
2
14
13
6
8
5
1
8
13
2
16
9
4
15
1
8
13
2
16
9
4
15
1
9
13
15
16
8
4
2
1
9
13
15
16
8
4
2
1
10
15
14
4
6
9
5
16
7
2
3
13
11
8
12
1
11
2
5
4
10
8
3
16
6
15
12
13
7
9
14
1
12
8
11
13
3
2
7
16
5
9
6
4
14
15
10
1
13
16
4
1
13
16
4
1
13
16
4
1
13
16
4
1
14
9
7
13
12
15
6
16
3
8
10
4
5
2
11
1
15
4
9
16
2
13
8
1
15
4
9
16
2
13
8
1
16
1
16
1
16
1
16
1
16
1
16
1
16
1
16
1

 

Modulo 19

Trois paires (2, 10), (3, 13), (14, 15).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
4
8
16
13
7
14
9
18
17
15
11
3
6
12
5
10
1
3
9
8
5
15
7
2
6
18
16
10
11
14
4
12
17
13
1
4
16
7
9
17
11
6
5
1
4
16
7
9
17
11
6
5
1
5
6
11
17
9
7
16
4
1
5
6
11
17
9
7
16
4
1
6
17
7
4
5
11
9
16
1
6
17
7
4
5
11
9
16
1
7
11
1
7
11
1
7
11
1
7
11
1
7
11
1
7
11
1
8
7
18
11
12
1
8
7
18
11
12
1
8
7
18
11
12
1
9
5
7
6
16
11
4
17
1
9
5
7
6
16
11
4
17
1
10
5
12
6
3
11
15
17
18
9
14
7
13
16
8
4
2
1
11
7
1
11
7
1
11
7
1
11
7
1
11
7
1
11
7
1
12
11
18
7
8
1
12
11
18
7
8
1
12
11
18
7
8
1
13
17
12
4
14
11
10
16
18
6
2
7
15
5
8
9
3
1
14
6
8
17
10
7
3
4
18
5
13
11
2
9
12
16
15
1
15
16
12
9
2
11
13
5
18
4
3
7
10
17
8
6
14
1
16
9
11
5
4
7
17
6
1
16
9
11
5
4
7
17
6
1
17
4
11
16
6
7
5
9
1
17
4
11
16
6
7
5
9
1
18
1
18
1
18
1
18
1
18
1
18
1
18
1
18
1
18
1

 

Modulo 23

Cinq paires (5, 14), (7, 10), (11, 21), (15, 20), (17, 19).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
4
8
16
9
18
13
3
6
12
1
2
4
8
16
9
18
13
3
6
12
1
3
9
4
12
13
16
2
6
18
8
1
3
9
4
12
13
16
2
6
18
8
1
4
16
18
3
12
2
8
9
13
6
1
4
16
18
3
12
2
8
9
13
6
1
5
2
10
4
20
8
17
16
11
9
22
18
21
13
19
3
15
6
7
12
14
1
6
13
9
8
2
12
3
18
16
4
1
6
13
9
8
2
12
3
18
16
4
1
7
3
21
9
17
4
5
12
15
13
22
16
20
2
14
6
19
18
11
8
10
1
8
18
6
2
16
13
12
4
9
3
1
8
18
6
2
16
13
12
4
9
3
1
9
12
16
6
8
3
4
13
2
18
1
9
12
16
6
8
3
4
13
2
18
1
10
8
11
18
19
6
14
2
20
16
22
13
15
12
5
4
17
9
21
3
7
1
11
6
20
13
5
9
7
8
19
2
22
12
17
3
10
18
14
16
15
4
21
1
12
6
3
13
18
9
16
8
4
2
1
12
6
3
13
18
9
16
8
4
2
1
13
8
12
18
4
6
9
2
3
16
1
13
8
12
18
4
6
9
2
3
16
1
14
12
7
6
15
3
19
13
21
18
22
9
11
16
17
8
20
4
10
2
5
1
15
18
17
2
7
13
11
4
14
3
22
8
5
6
21
16
10
12
19
9
20
1
16
3
2
9
6
4
18
12
8
13
1
16
3
2
9
6
4
18
12
8
13
1
17
13
14
8
21
12
20
18
7
4
22
6
10
9
15
2
11
3
5
16
19
1
18
2
13
4
3
8
6
16
12
9
1
18
2
13
4
3
8
6
16
12
9
1
19
16
5
3
11
2
15
9
10
6
22
4
7
18
20
12
21
8
14
13
17
1
20
9
19
12
10
16
21
6
5
8
22
3
14
4
11
13
7
2
17
18
15
1
21
4
15
16
14
18
10
3
17
12
22
2
19
8
7
9
5
13
20
6
11
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1
22
1

Poursuivons,

Comme on peut le constater, la place manque pour conserver la présentation sous forme de tableau.
C'est pourquoi la suite est disponible aux adresses suivantes: 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109.

Plus d'informations sont disponible à la rubrique :

La graine du premier.