7.4 Construire de grands nombres premiers
227
Prob(X = k) = (1 − p)
k−1 p.
En effet, on a une probabilit´ e 1 − p de tirer un entier non premier `
a chacun des k − 1
premiers tirages et une probabilit´ e p de tirer un nombre premier au k-i` eme tirage.
L’esp´ erance de la variable al´ eatoire X est le nombre moyen d’exp´ eriences qu’on s’attend
` a faire pour obtenir un premier succ` es, c’est-` a-dire g´ en´ erer un nombre premier. Pour
une variable g´ eom´ etrique de param` etre p, on a
E(X) =
∞
k=1
kProb(X = k) =
∞
k=1
k(1 − p)
k−1 p =
1
p
.
(Montrer que
∞
k=1 k(1 − p)
k−1 p =
1
p demande un peu d’astuce. Ce calcul se trouve
dans tout livre de probabilit´ e.)
Dans notre cas, si le dernier chiffre appartient ` a {1, 3, 7, 9} et donc que p ≈
1
92 , alors
E(X) = 92 ; il faudra donc faire en moyenne 92 exp´ eriences avant de g´ en´ erer un nombre
premier.
Ce que nous avons fait jusqu’` a pr´ esent suppose qu’il existe un moyen de tester
si un nombre entier n est premier, qui soit plus simple que de factoriser n. Un tel
test s’appelle test de primalit´ e. Il en existe plusieurs dans la litt´ erature. Tous font
appel `
a un certain raffinement math´ ematique. Le test que nous pr´ esentons ici est le
test apparaissant dans l’article original du code RSA, [7]. Il est technique et utilise
le symbole de Jacobi, introduit ci-dessous et peu intuitif. Le principe sous-jacent est
que n laisse ses « empreintes » partout si bien que, si n n’est pas premier, au moins
la moiti´ e des nombres de l’ensemble {1, . . . , n} « savent » que n n’est pas premier. Si
k nombres m 1 , . . . m k ∈ {1, . . . , n} r´ eussissent le test, alors n a une grande probabilit´ e
d’ˆ etre premier : c’est un exercice avec la formule de Bayes.
Un test probabiliste de primalit´ e Nous introduisons, pour des entiers m et n
relativement premiers, le symbole de Jacobi J(m, n) ∈ {−1, 1}. La d´ efinition technique
de J(m, n) sera donn´ ee plus bas. Soit
E = {1, . . . , n − 1}.
Si n est un nombre premier et si a ∈ E, alors
(a, n) = 1,
J(a, n) ≡ a
n−1
2
(mod n).
(7.4)
Si n n’est pas premier, alors au moins la moiti´ e des nombres de E ne satisfont pas `
a
(7.4). On dira qu’ils « ´ echouent au test ». D` es qu’un nombre a ∈ E ´ echoue au test, on
sait que n n’est pas premier. Si on choisit a ∈ E au hasard, on a donc
Prob(a r´ eussit le test | n est non premier) ≤
1
2
.
227
Prob(X = k) = (1 − p)
k−1 p.
En effet, on a une probabilit´ e 1 − p de tirer un entier non premier `
a chacun des k − 1
premiers tirages et une probabilit´ e p de tirer un nombre premier au k-i` eme tirage.
L’esp´ erance de la variable al´ eatoire X est le nombre moyen d’exp´ eriences qu’on s’attend
` a faire pour obtenir un premier succ` es, c’est-` a-dire g´ en´ erer un nombre premier. Pour
une variable g´ eom´ etrique de param` etre p, on a
E(X) =
∞
k=1
kProb(X = k) =
∞
k=1
k(1 − p)
k−1 p =
1
p
.
(Montrer que
∞
k=1 k(1 − p)
k−1 p =
1
p demande un peu d’astuce. Ce calcul se trouve
dans tout livre de probabilit´ e.)
Dans notre cas, si le dernier chiffre appartient ` a {1, 3, 7, 9} et donc que p ≈
1
92 , alors
E(X) = 92 ; il faudra donc faire en moyenne 92 exp´ eriences avant de g´ en´ erer un nombre
premier.
Ce que nous avons fait jusqu’` a pr´ esent suppose qu’il existe un moyen de tester
si un nombre entier n est premier, qui soit plus simple que de factoriser n. Un tel
test s’appelle test de primalit´ e. Il en existe plusieurs dans la litt´ erature. Tous font
appel `
a un certain raffinement math´ ematique. Le test que nous pr´ esentons ici est le
test apparaissant dans l’article original du code RSA, [7]. Il est technique et utilise
le symbole de Jacobi, introduit ci-dessous et peu intuitif. Le principe sous-jacent est
que n laisse ses « empreintes » partout si bien que, si n n’est pas premier, au moins
la moiti´ e des nombres de l’ensemble {1, . . . , n} « savent » que n n’est pas premier. Si
k nombres m 1 , . . . m k ∈ {1, . . . , n} r´ eussissent le test, alors n a une grande probabilit´ e
d’ˆ etre premier : c’est un exercice avec la formule de Bayes.
Un test probabiliste de primalit´ e Nous introduisons, pour des entiers m et n
relativement premiers, le symbole de Jacobi J(m, n) ∈ {−1, 1}. La d´ efinition technique
de J(m, n) sera donn´ ee plus bas. Soit
E = {1, . . . , n − 1}.
Si n est un nombre premier et si a ∈ E, alors
(a, n) = 1,
J(a, n) ≡ a
n−1
2
(mod n).
(7.4)
Si n n’est pas premier, alors au moins la moiti´ e des nombres de E ne satisfont pas `
a
(7.4). On dira qu’ils « ´ echouent au test ». D` es qu’un nombre a ∈ E ´ echoue au test, on
sait que n n’est pas premier. Si on choisit a ∈ E au hasard, on a donc
Prob(a r´ eussit le test | n est non premier) ≤
1
2
.