Approfondissements de lycée/Arithmétique modulaire approfondie

Approfondissements de lycée

Introduction

Les mathématiques sont la reine des sciences et la théorie des nombres est la reine des mathématiques. -- Carl Friedrich Gauss 1777 - 1855

Dans la section Nombres premiers et arithmétique modulaire, nous avons vu les propriétés élémentaires d'un nombre premier et sa relation avec l'arithmétique modulaire. Pour la plus grande partie, notre attention a été restreinte à l'arithmétique mod p, où p est un nombre premier.

Dans ce chapitre, nous démarrons en discutant certains résultats plus élémentaires dans l'arithmétique modulo un nombre premier p, puis en se déplaçant sur la discussion de ces résultats modulo m où m est un nombre composé. En particulier, nous examinerons de plus près le Théorème des restes chinois (TRC), et comment il nous permet de casser l'arithmétique modulo m en composants. À partir de ce point de vue, le TRC est un outils extrêmement puissant qui peut nous aider à débloquer beaucoup de secrets de l'arithmétique modulaire (avec une relative facilité).

Enfin, nous introduirons l'idée d'un groupe abélien à travers la multiplication dans l'arithmétique modulaire et nous discuterons sur le problème du logarithme discret qui sous-tend un des plus importants systèmes cryptographiques connus actuellement.

Connaissance supposée Dans ce chapitre, nous supposons que le lecteur peut trouver les inverses et est capable de résoudre un système de congruences (Théorème des Restes Chinois) (voir : Nombres premiers et arithmétique modulaire).

Théorème de Wilson

Le théorème de Wilson est un simple résultat qui conduit à un nombre d'observations intéressantes dans la théorie élémentaire des nombres. Il établit le résultat suivant : Si p est un nombre premier, alors

$1\cdot 2\cdot 3\cdots (p-1)\equiv p-1{\pmod {p}}$

Nous savons que l'inverse de p - 1 est p - 1, donc tout autre nombre peut être apparié avec son inverse et être éliminé. Par exemple, soit p = 7, nous considérons

1 × 2 × .. × 6 ≡ (2 × 4) × (3 × 5) × 1 × 6 = 6

Ce que nous avons fait, c'est apparier les nombres qui sont inverses les uns des autres, il nous reste alors les nombres qui sont inverse avec eux-même. Dans ce cas, ce sont les nombres 1 et 6.

Mais, il existe une difficulté technique. Pour un nombre premier général, p, comment savons-nous que 1 et p - 1 sont les seuls nombre mod p qui élevés au carrés donnent 1 ? Pour m non premier, il existe plus de 2 solutions à x² ≡ 1 (mod m), par exemple, soit m = 15, alors x = 1, 14, 4, 11 sont les solutions de x² ≡ 1 (mod m).

Néanmoins, nous pouvons montrer qu'il ne peut y avoir que (au plus) deux solutions à x² ≡ 1 (mod p) lorsque p est premier. Nous le faisons par une simple démonstration par l'absurde. Vous pouvez passer la preuve suivante et admettre que le théorème de Wilson est vrai.

Soit p un nombre premier, et x² ≡ 1 (mod p). Nous voulons prouver qu'il ne peut exister seulement que 2 solutions, c'est à dire x = 1, -1

$x^{2}-1\!$	$\equiv 0\!$
$(x-1)(x+1)\!$	$\equiv 0\!$

il est évident, à partir de ci-dessus que x = 1, -1 (≡ p - 1) sont solutions. Supposons qu'il existe une autre solution, x = d, et d n'est pas égal à 1 ou -1. Puisque p est un nombre premier, nous savons que d - 1 doit avoir un inverse. Nous substituons x avec d et multiplions les deux côtés par l'inverse, c.a.d.

$(d-1)(d+1)\!$	$=0\!$
$d+1\!$	$=0\!$
$d\!$	$=-1\!$

mais notre supposition initiale était que d ≠ -1. C'est une contradiction. Par conséquent, il ne peut exister que 2 solutions à x² ≡ 1 (mod p).

Le petit théorème de Fermat

Il existe un remarquable petit théorème nommé en l'honneur de Fermat, le prince des mathématiciens amateurs. Il établit que si p est premier et pour a ≠ 0 donné alors

$a^{p-1}\equiv 1{\pmod {p}}\!$

Ce théorème repose sur le fait que p est premier. Rappelons que si p est premier alors a ≠ 0 possède un inverse. Donc, pour tout b et c, nous devons avoir

$ab\equiv ac{\pmod {p}}\!$ si et seulement si $b\equiv c{\pmod {p}}\!$

Une simple conséquence de ce qui précède est que les nombres suivants doivent tous être différents mod p

a, 2a , 3a, 4a, ..., (p-1)a

et il existe p - 1 de ces nombres ! Par conséquent, la liste précédente est simplement les nombres 1, 2, ... p - 1 dans un ordre différent. Prenons un exemple, si p = 5, et a = 2 :

1, 2, 3, 4

multiplions chacun des précédents par 2 mod 5, nous obtenons

2, 4, 1, 3

Ce sont les nombres originaux dans un ordre différent.

Ainsi, pour tout p et en utilisant le Théorème de Wilson (rappel : 1 × 2 × ... × (p-1) ≡ -1), nous obtenons

$a\cdot 2a\cdots (p-1)a\!$	$\equiv \!$	$1\cdot 2\cdots (p-1)$
	$\equiv \!$	$-1\!$

et d'un autre côté, nous obtenons aussi

$a\cdot 2a\cdots (p-1)a\!$	$\equiv \!$	$a^{p-1}(1\cdot 2\cdots (p-1))$
	$\equiv \!$	$-a^{p-1}\!$

En égalisant les deux résultats, nous obtenons

$-a^{p-1}\!$

$\equiv \!$

$-1\!$

ce qui est essentiellement le petit théorème de Fermat.

L'arithmétique modulaire avec un m général

*Le Théorème des Restes Chinois revisité*

Cette section est plutôt théorique, et est destinée à justifier l'arithmétique que couvrira la section suivante. Par conséquent, il n'est pas nécessaire de comprendre entièrement ce qui est exposé ici, le lecteur peut choisir en toute quiétude de passer l'exposé ci-dessous.

Rappelons le Théorème des Restes Chinois (TRC) que nous avons exposé dans la section Arithmétique modulaire. Les congruences suivantes

$x\equiv b{\pmod {n_{1}}}\!$

$x\equiv c{\pmod {n_{2}}}\!$

ont une solution si et seulement si pgcd(n₁,n₂) divise (b - c).

Ce simple théorème décevant contient la clef de l'arithmétique modulo m (composé) ! Nous considérerons le cas où m a seulement deux facteurs premiers, c'est à dire un nombre semi-premier, puis le cas général.

Supposons m = pⁱq^j, où p et q sont des nombres premiers distincts, alors chaque nombre naturel sous m (0, 1, 2, ..., m - 1) correspond uniquement à un système de congruences mod pⁱ et mod q^j. Ceci est dû au fait que pgcd(pⁱ,q^j) = 1, donc il divise tous les nombres.

Considérons un nombre n, il correspond à

$n\equiv x_{n}{\pmod {p^{i}}}\!$

$n\equiv y_{n}{\pmod {q^{j}}}\!$

pour deux nombres x_n et y_n. Si r ≠ n alors r correspond à

$r\equiv x_{r}{\pmod {p^{i}}}\!$

$r\equiv y_{r}{\pmod {q^{j}}}\!$

Maintenant, puisque r et n sont différents, nous devons avoir, soit x_r ≠ x_n et/ou y_r ≠ y_n

Par exemple, prenons $m=12=2^{2}\times 3$, alors nous pouvons construire la table suivante montrant les $x_{n}$, $y_{n}$ pour chaque n (0, 1, 2 ... 11)

n	n (mod 22)	n (mod 3)
0	0	0
1	1	1
2	2	2
3	3	0
4	0	1
5	1	2
6	2	0
7	3	1
8	0	2
9	1	0
10	2	1
11	3	2

Note : comme prévu, chaque nombre correspond uniquement à deux systèmes de congruences mod 2² et mod 3.

Exercices

1. Considérons m = 45 = 3² × 5. Complétez la table ci-dessous et vérifiez que deux nombres quelconques doivent différer d'au moins une place dans la deuxième et la troisième colonne

n	n (mod 32)	n (mod 5)
0	0	0
1	1	1
2	2	2
...
44	?	?

2. Supposons m = pⁱq^j, n correspond à

$n\equiv x_{n}{\pmod {p^{i}}}\!$

$n\equiv y_{n}{\pmod {q^{j}}}\!$

et r correspond à

$r\equiv x_{r}{\pmod {p^{i}}}\!$

$r\equiv y_{r}{\pmod {q^{j}}}\!$

Il est vrai que

$n+r\equiv x_{n}+x_{r}{\pmod {p^{i}}}\!$

$n+r\equiv y_{n}+y_{r}{\pmod {q^{j}}}\!$

et que

$nr\equiv x_{n}x_{r}{\pmod {p^{i}}}\!$

$nr\equiv y_{n}y_{r}{\pmod {q^{j}}}\!$

Arithmétique avec le TRC

L'exercice 2 ci-dessus a donné la plus grosse indication pour savoir comment le TRC peut nous aider avec l'arithmétique modulo m. Il n'est pas essentiel pour le lecteur de tout comprendre ci-dessus, à ce niveau. Nous décrirons comment le TRC peut nous aider avec l'arithmétique modulo m. Dans des termes simples, le TRC aide à casser un calcul modulo-m en de plus petits calculs modulo des facteurs premiers de m.

Comme toujours, considérons un exemple simple d'abord. Soit $m=63=3^{2}\ \times \ 7$, nous voyons que m a deux nombres premiers distincts. Nous devons montrer la multiplication de 51 et 13 modulo 63 de deux manières. Premièrement, la manière standard

$51\times 13\!$	$=\!$	$663\!$
	$=\!$	$10\times 63+33\!$
	$\equiv \!$	$33{\pmod {63}}\!$

Alternativement, nous notons que

$51\equiv 6{\pmod {9}}\!$

et

$51\equiv 2{\pmod {7}}\!$

Nous pouvons représenter les deux expressions ci-dessus comme un couple (6,2). Nous faisons un petit abus de notation en écrivant 51 = (6,2). De manière similaire, nous écrivons 13 = (4,6). Lorsque nous multiplions avec les couples, nous multiplions les composants, i.e. (a,b) × (c,d) = (ac,bd),

$51\times 13\!$	$=\!$	$(6,2)\times (4,6)\!$
	$=\!$	$(24,12)\!$
	$=\!$	$(2\times 9+6,7+5)\!$
	$\equiv \!$	$(6,5)\!$

Maintenant, résolvons

$x\equiv 6{\pmod {9}}\!$

et

$x\equiv 5{\pmod {7}}\!$

nous écrivons x = 6 + 9a, qui est la première congruence, puis

$6+9a\!$	$\equiv \!$	$5{\pmod {7}}\!$
$2a\!$	$\equiv \!$	$6\!$
$a\!$	$\equiv \!$	$3\!$

par conséquent, nous avons a = 3 + 7b, en substituant plus haut, nous obtenons

$x=6+9(3+7b)=33+63b\equiv 33{\pmod {63}}\!$

qui est la même réponse que nous avons obtenue à partir de la multiplication de 51 et 13 (mod 63) par la méthode standard !

Résumons ce que nous avons fait. En représentant les deux nombres (51 et 13) sous forme de deux couples et en multipliant les composants, nous finissons avec un autre couple. Et ce couple correspond au produit des deux nombres (mod m) via le Théorème des Restes Chinois.

Nous prendrons deux exemples supplémentaires. Soit $m=88=2^{3}\times 11$, et multiplions 66 et 40 de deux manières. D'abord, la manière standard

$66\times 40\!$	$=\!$	$2640\!$
	$=\!$	$30\times 88\!$
	$\equiv \!$	$0{\pmod {88}}\!$

et maintenant, la deuxième manière, 40 = (0,7) et 66 = (4,0) et

$66\times 40\!$	$=\!$	$(0,7)\times (4,0)\!$
	$=\!$	$(0,0)\!$
	$\equiv \!$	$0{\pmod {88}}\!$

Pour le deuxième exemple, nous notons qu'il n'est pas nécessaire de s'arrêter à simplement deux facteurs premiers distincts. Prenons $m=975=3\times 5^{2}\times 13$, et multiplions 900 et 647 (mod 975),

$900\times 647\!$	$=\!$	$582300\!$
	$\equiv \!$	$225{\pmod {975}}\!$

Pour l'autre manière, nous notons que 900 ≡ 0 (mod 3) ≡ 0 (mod 25) ≡ 3 (mod 13), et pour 647 ≡ 2 (mod 3) ≡ 22 (mod 25) ≡ 10 (mod 13),

$900\times 647\!$	$=\!$	$(0,0,3)\times (2,22,10)\!$
	$\equiv \!$	$(0,0,30)\!$
	$\equiv \!$	$(0,0,4)\!$

maintenant, si nous résolvons les congruences suivantes

$x\equiv 0{\pmod {3}}\!$

$x\equiv 0{\pmod {25}}\!$

$x\equiv 4{\pmod {13}}\!$

alors nous obtiendrons x ≡ 225 !

Pourquoi ? Casser l'arithmétique modulaire m en composants plus petits semble être un peu de travail. Prenons l'exemple des multiplications, d'abord, nous avons besoin d'exprimer chaque nombre comme un n-uplet (n est le nombre de facteurs premiers distincts de m), multiplier les composants, puis résoudre les n congruences résultantes. Assurément, ce travail est plus complexe que de multiplier simplement les deux nombres, puis de réduire le résultat modulo m. Alors, pourquoi se donner la peine d'étudier cela ?

En cassant un nombre m en facteurs premiers, nous avons un aperçu de la manière dont l'arithmétique fonctionne réellement. De manière plus importante, beaucoup de problèmes en arithmétique modulaire m peuvent être difficiles à résoudre, mais lorsque qu'ils sont cassés en composants, ils deviennent subitement plus faciles, par exemple le théorème de Wilson pour un m général (discuté ci-dessous).

Exercices

1. Montrer que l'addition peut aussi être effectuée par composants.

2. Multiplier par composants 32 et 84 (mod 134).

...

L'indicatrice d'Euler

Pour discuter de la forme la plus générale du théorème de Wilson et du petit théorème de Fermat mod m (non premier), il est intéressant de connaître un résultat simple du mathématicien célèbre Euler. Plus précisément, nous voulons discuter d'une fonction, appelée la fonction indicatrice d'Euler, notée φ.

Les fonctions φ ne sont pas des choses très simples. Pour un nombre naturel quelconque m, φ(m) donne le nombre de n < m, tel que pgcd(n,m) = 1. En d'autres termes, elle calcule combien de nombre mod m ont un inverse. Nous discuterons de la valeur de φ(m) pour les cas simples d'abord, puis nous déduirons la formule pour un m général à partir des résultats basiques.

Par exemple, soit m = 5, alors φ(m) = 4. Comme 5 est un nombre premier, tous les nombres naturels différents de zéro inférieurs à 5 (1,2,3 and 4) sont premiers avec lui. Donc, il existe 4 nombres mod 5 qui ont des inverses. En fait, si m est premier, alors φ(m) = m - 1.

Nous pouvons généraliser ce qui précède à m = p^r où p est premier. Dans ce cas, nous essayons d'employer un argument de comptage pour calculer φ(m). Notez qu'il existe p^r nombres naturels inférieurs à m (0, 1, 2 ... p^r - 1), et donc φ(m) = p^r - (nombre de n < m tels que pgcd(n,m) ≠ 1). Nous avons effectué ceci parce qu'il est plus facile de compter le nombre de n sans inverse mod m.

Un élément, n mod m n'a pas d'inverse si et seulement si il partage un facteur commun avec m. Mais, tous les facteurs de m (non égaux à 1) sont un multiple de p. Donc, combien de multiples de p existent mod m ? Nous pouvons les lister, ce sont

$0,p,2p,\cdots ,p^{r}-p\!$

où le dernier élément peut être écrit comme (p^r-1 - 1)p, et donc, il existe $p^{r-1}\!$ multiples de p. Par conséquent, nous pouvons conclure

$\varphi (p^{r})=p^{r}-p^{r-1}\!$

Nous avons maintenant toute la machinerie nécessaire pour déduire la formule de φ(m) pour un m quelconque.

Par le Théorème Fondamental de l'Arithmétique, tout nombre naturel m peut être exprimé de manière unique comme le produit de nombres premiers, c'est à dire

$m=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}\!$

où p_i pour i = 1, 2 ... r sont des nombres premiers distincts et k_i sont des entiers positifs. Par exemple 1225275 = 3×5²×17×31². À partir d'ici, le lecteur peut essayer de déduire le résultat suivant (le TRC peut aider).

La fonction indicatrice d'Euler φ

Supposons m exprimé de manière unique comme ci-dessous
  $m=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}\!$
alors
  $\varphi (m)=(p_{1}^{k_{1}}-p_{1}^{k_{1}-1})(p_{2}^{k_{2}}-p_{2}^{k_{2}-1})\cdots (p_{r}^{k_{r}}-p_{r}^{k_{r}-1})\!$

Le théorème de Wilson

Le théorème de Wilson pour un m général établit que le produit de tous les éléments inversibles mod m

égal -1 si m a seulement un facteur premier, ou m = 2p^k pour un certain nombre premier p

égal à 1 pour tous les autres cas

Un élément inversible mod m est un nombre naturel n < m tel que pgcd(n, m) = 1. Un élément auto-inversible est un élément dont l'inverse est lui-même.

Dans la démonstration du théorème de Wilson pour un nombre premier p, les nombres de 1 à p - 1 ont tous des inverses. Ceci n'est pas vrai pour un m général. En fait, il est certain que (m - 1)! ≡ 0 (mod m), pour cette raison, nous considérons à la place le produit de tous les éléments inversibles mod m.

Pour le cas où m = p est un nombre premier, nous avons aussi fait appel au fait que 1 et p - 1 sont les seuls éléments qui, élevés au carré, donnent 1. En fait, pour m = p^k, 1 et m - 1 (≡ -1) sont les seuls éléments auto-inversibles (voir les exercices). Mais, pour un m général, ceci n'est pas vrai. Prenons par exemple m = 21. En arithmétique modulo 21 chacun des nombres suivants est lui-même un inverse

1, 20, 8, 13

donc, comment pouvons-nous dire que le produit de tous les éléments inversibles est égal à 1 ?

Nous utilisons le TRC décrit précédement. Considérons le cas où m = 2p^k. Par le TRC, chaque élément mod m peut être représenté comme un couple (a,b) où a peut prendre la valeur 0 ou 1 tandis que b peut prendre la valeur 0, 1, ..., ou p^k - 1. Chaque couple correspond uniquement à une paire de congruences et la multiplication peut être exécutée par composants.

En utilisant l'information précédente, nous pouvons facilement lister tous les éléments auto-inversibles, parce que (a,b)² ≡ 1 signifie (a²,b²) = (1,1), donc a est un élément inversible mod 2 et b est un élément inversible mod p^k, donc a ≡ 1 ou -1, b ≡ 1 ou -1. Mais mod 2 1 ≡ -1, donc a = 1. Par conséquent, il existe deux éléments qui sont auto-inversibles mod m = 2p^k, ce sont (1,1) = 1, et (1, -1) = m - 1 . Donc, dans ce cas, le résultat est le même, comme m possède seulement un facteur premier unique.

Pour le cas où m possède plus d'un facteur premier et m≠ 2p^k. Disons m a n facteurs premiers alors m peut être représenté comme un n-uplet. Disons que m possède 3 facteurs premiers distincts, alors tous les éléments auto-inversibles de m sont

1. (1,1,1)
2. (1,1,-1)
3. (1,-1,1)
4. (1,-1,-1)
5. (-1,1,1)
6. (-1,1,-1)
7. (-1,-1,1)
8. (-1,-1,-1)

leur produit est (1,1,1) qui correspond à 1 mod m.

Exercice

1. Soit p un nombre premier. Montrer que dans l'arithmétique modulo p^k, 1 et p^k - 1 sont les seuls éléments auto-inversibles.

...plus à venir

...

Le petit théorème de Fermat

Comme indiqué dans la section précédente, tous les éléments ne sont pas inversibles (c.a.d. possède un inverse) mod m. Une version généralisée du dernier théorème de Fermat utilise la fonction indicatrice d'Euler, il énonce

$a^{\phi (m)}\equiv 1{\pmod {m}}\!$

pour tous les a ≠ 0 satisfaisant pgcd(a,m) = 1. Ceci est facile à voir à partir de la version généralisée du théorème de Wilson. Nous utilisons une technique similaire à partir de la démonstration du petit théorème de Fermat. Nous avons

$(ab_{1})(ab_{2})\cdots (ab_{\phi (m)})\equiv b_{1}b_{2}\cdots b_{\phi (m)}{\pmod {m}}$

où les b_i's sont tous les éléments inversibles mod m. Par le théorème de Wilson, le produit de tous les éléments inversibles égaux à d (= 1 ou -1). Donc, nous obtenons

$a^{\phi (m)}d\equiv d{\pmod {m}}\!$

qui est essentiellement l'énoncé du petit théorème de Fermat.

Bien que le petit théorème de Fermat est très net, il est imprécis dans un certain sens. Par exemple, prenons m = 15 = 3 × 5, nous savons que si a possède un inverse mod 15 alors a^φ(15) = a⁸ ≡ 1 (mod 15). Mais 8 est trop grand, tout ce que nous avons besoin est 4, a⁴ ≡ 1 (mod 15) pour tous les a avec un inverse (le lecteur peut vérifier).

La fonction de Carmichael λ(m) est le plus petit nombre tel que a^λ(m) ≡ 1 (mod m) pour un a inversible. Une question dans Ensemble de problèmes traite de cette fonction.

Exercices

...plus à venir

La factorisation double-torsion

Il est clair que factoriser un grand nombre peut être extrêmement difficile. Par exemple, étant donné 76 372 591 715 434 667, qui est le produit de deux nombres premiers, le lecteur peut-il le factoriser ? Sans l'aide d'un bon logiciel d'algèbre, la tâche risque d'être impossible. À ce jour, il n'existe pas d'algorithme connu efficient pour factoriser un nombre en facteurs premiers.

Néanmoins, sous certaines circonstances spéciales, factoriser peut être facile. Nous considérerons la méthode de factorisation double-torsion. Un élément double-torsion dans l'arithmétique modulaire m est un nombre a tel que a² ≡ 1 (mod m).

Considérons un exemple en arithmétique modulo 21. Notez qu'en utilisant le TRC, nous pouvons représenter tout nombre mod 21 comme un couple. Les éléments double-torsion sont 1 = (1,1), 13 = (1,-1), 8 = (-1,1) et 20 = (-1,-1). Les nombres 13 et 8 sont intéressants, parce que 1 et 20 (≡ - 1) sont évidemment double-torsion, nous appelons ces nombres double-torsion triviaux.

Maintenant, 13 + 1 = (1,-1) + (1,1) = (2,0). Par conséquent 13 + 1 = 14 est un élément partageant un facteur commun avec 21, comme le deuxième composant dans la représentation en couple de 14 est zéro. Par conséquent PGCD(14,21) = 7 est un facteur de 21.

L'exemple ci-dessus est très stupide parce que tout le monde peut factoriser 21. Mais qu'en est-il de 24 131 ? Factoriser n'est pas si facile. Mais, étant donné que 12 271 est un élément double-torsion non-trivial (c.a.d. ≠ 1 ou -1), alors nous pouvons conclure que pgcd(12271 + 1,24131) et pgcd(12271 - 1,24131) sont des facteurs de 24 131. En effet, pgcd(12272,24131) = 59 et pgcd(12270,24131) = 409 sont tous les deux des facteurs de 24 131.

Plus généralement, soit m un nombre composé, et t un élément double-torsion non-trivial mod m c.a.d. t ≠ 1, -1. Alors

pgcd(t + 1,m) divise m, et

pgdc(t - 1,m) divise m

ceci peut être expliqué en utilisant le TRC.

Nous expliquerons le cas où m = pq, p et q sont des nombres premiers. Étant donné t est un élément double-torsion non-trivial, alors t a pour représentation (1,-1) ou (-1,1). Supposons t = (-1,1) alors t + 1 = (-1,1) + (1,1) = (0,2), par conséquent t + 1 doit avoir un multiple de p par conséquent pgcd(t,m) = p. L'autre cas t - 1 = (-1,1) - (1,1) = (-2,0) et donc pgcd(t - 1,m) = q.

Donc, si nous avons un élément double-torsion non-trivial alors nous avons effectivement trouvé un (et sans doute plus) facteur premier, qui donne la factorisation du nombre. Dans les applications cryptographiques publiques les plus modernes, pour casser le système nous avons besoin seulement de factoriser un nombre avec deux facteurs premiers. De ce point de vue, la méthode de factorisation double-torsion est effroyablement efficiente.

Bien sur, trouver un élément double-torsion non-trivial n'est pas une tâche facile non plus. Donc, la banque par internet est encore sûre pour le moment. De cette manière, 76372591715434667 = 224364191 × 340395637.

Exercices

1. Étant donné que 18815 est un élément double-torsion mod 26176. Factoriser 26176.

...plus à venir'