228
7 La cryptographie ` a cl´ e publique
On choisit a 1 , . . . , a k au hasard dans E et on fait passer le test. Calculons la probabilit´ e
que n soit premier sachant que a 1 , . . . , a k ont r´ eussi le test. Donnons des noms aux
´ ev´ enements : A i est l’´ ev´ enement « a i a r´ eussi le test ». Soit P (n) l’´ ev´ enement « n est
premier » et Q(n) son compl´ ementaire, c’est-` a-dire « n n’est pas premier ». Notons
A = A 1 ∩ · · · ∩ A k . A est donc l’´ ev´ enement « tous les ´ ee l´ ements a 1 , . . . , a k ont r´ eussi le
test ». La formule de Bayes donne
Prob(P (n) | A) =
Prob(A | P (n))Prob(P (n))
Prob(A | P (n))Prob(P (n)) + Prob(A | Q(n))Prob(Q(n))
.
Comme
Prob(A | P (n)) = 1,
Prob(A | Q(n)) ≤
1
2 k ,
et qu’on peut calculer approximativement Prob(P (n)) et Prob(Q(n)) par le th´ eor` eme
des nombres premiers, on peut calculer approximativement la probabilit´ e que n soit premier (ou plutˆ ot, donner une borne inf´ erieure ` a cette probabilit´ e) sachant que a 1 , . . . , a k
ont pass´ e le test.
En effet, le d´ enominateur satisfait ` a
Prob(A | P (n))Prob(P (n)) + Prob(A | Q(n))Prob(Q(n))
≤ Prob(P (n)) +
1
2 k Prob(Q(n)).
Le num´ erateur vaut simplement Prob(P (n)). Prenons maintenant le cas o` u n est un
nombre impair de 100 chiffres non divisible par 5 (c’est-` a-dire un ´ el´ ement de B). Alors,
on a vu que
Prob(P (n)) ≈
1
92
et Prob(Q(n)) ≈
91
92 . Ceci donne
Prob(P (n) | A) ≥
1
1 + 91
1
2 k
= p k .
Faisons maintenant des tests num´ eriques avec diff´ erentes valeurs de k.
p 10 = 0,9184 = 1 − 0,816 × 10
−1 ,
p 20 = 0,999913 = 1 − 0,868 × 10
−4 ,
p 30 = 0,9999999152 = 1 − 0,848 × 10
−7 ,
p 40 = 0,9999999999172 = 1 − 0,828 × 10
−10 .
On voit que le nombre k n’a pas besoin d’ˆ etre grand pour qu’il y ait une tr` es grande
probabilit´ e que n soit premier.
Il nous reste maintenant ` a d´ efinir le symbole de Jacobi et `
a montrer que, si n n’est
pas premier, moins de la moiti´ e des nombres a ∈ E r´ eussissent le test, c’est-` a-dire
7 La cryptographie ` a cl´ e publique
On choisit a 1 , . . . , a k au hasard dans E et on fait passer le test. Calculons la probabilit´ e
que n soit premier sachant que a 1 , . . . , a k ont r´ eussi le test. Donnons des noms aux
´ ev´ enements : A i est l’´ ev´ enement « a i a r´ eussi le test ». Soit P (n) l’´ ev´ enement « n est
premier » et Q(n) son compl´ ementaire, c’est-` a-dire « n n’est pas premier ». Notons
A = A 1 ∩ · · · ∩ A k . A est donc l’´ ev´ enement « tous les ´ ee l´ ements a 1 , . . . , a k ont r´ eussi le
test ». La formule de Bayes donne
Prob(P (n) | A) =
Prob(A | P (n))Prob(P (n))
Prob(A | P (n))Prob(P (n)) + Prob(A | Q(n))Prob(Q(n))
.
Comme
Prob(A | P (n)) = 1,
Prob(A | Q(n)) ≤
1
2 k ,
et qu’on peut calculer approximativement Prob(P (n)) et Prob(Q(n)) par le th´ eor` eme
des nombres premiers, on peut calculer approximativement la probabilit´ e que n soit premier (ou plutˆ ot, donner une borne inf´ erieure ` a cette probabilit´ e) sachant que a 1 , . . . , a k
ont pass´ e le test.
En effet, le d´ enominateur satisfait ` a
Prob(A | P (n))Prob(P (n)) + Prob(A | Q(n))Prob(Q(n))
≤ Prob(P (n)) +
1
2 k Prob(Q(n)).
Le num´ erateur vaut simplement Prob(P (n)). Prenons maintenant le cas o` u n est un
nombre impair de 100 chiffres non divisible par 5 (c’est-` a-dire un ´ el´ ement de B). Alors,
on a vu que
Prob(P (n)) ≈
1
92
et Prob(Q(n)) ≈
91
92 . Ceci donne
Prob(P (n) | A) ≥
1
1 + 91
1
2 k
= p k .
Faisons maintenant des tests num´ eriques avec diff´ erentes valeurs de k.
p 10 = 0,9184 = 1 − 0,816 × 10
−1 ,
p 20 = 0,999913 = 1 − 0,868 × 10
−4 ,
p 30 = 0,9999999152 = 1 − 0,848 × 10
−7 ,
p 40 = 0,9999999999172 = 1 − 0,828 × 10
−10 .
On voit que le nombre k n’a pas besoin d’ˆ etre grand pour qu’il y ait une tr` es grande
probabilit´ e que n soit premier.
Il nous reste maintenant ` a d´ efinir le symbole de Jacobi et `
a montrer que, si n n’est
pas premier, moins de la moiti´ e des nombres a ∈ E r´ eussissent le test, c’est-` a-dire