216
7 La cryptographie ` a cl´ e publique
Preuve Montrons d’abord que r n | a et r n | b. Puisque r n+1 = 0, la derni` ere ´ equation
s’´ ecrit r n−1 = q n+1 r n . Donc, r n | r n−1 . L’avant-derni` ere ´ equation est : r n−2 = q n r n−1 +
r n . Comme r n | r n−1 , alors r n | q n r n−1 + r n . Donc, r n | r n−2 . On it` ere en remontant les
´ equations une `
a une. On obtient finalement que r n | r i pour tout i. Donc, r n | r 1 q 2 +r 2 =
b. Finalement, puisque r n | b et r n | r 1 , alors r n | bq 1 + r 1 = a. Donc, r n | a et r n | b, ce
qui entraˆ ıne que r n | (a, b).
Soit maintenant d un diviseur de a et de b. On doit montrer que d divise r n . Dans
ce cas-ci, on proc` ede en sens inverse. Puisque d | a et d | b, alors d | r 1 = a − bq 1 . Dans
la deuxi` eme ´ equation, on a d | b et d | r 1 , donc d | r 2 = b − r 1 q 2 . On it` ere et on obtient
d | r i pour tout i. En particulier, d | r n .
On peut donc conclure que r n = (a, b).
Corollaire 7.4 Soient a et b deux entiers et c = (a, b). Il existe x, y ∈ Z tels que
c = ax + by.
Preuve La preuve utilise la preuve de la proposition 7.3. On sait que c = r n . On
remonte les ´ equations une ` a une. Comme r n−2 = q n r n−1 + r n , alors
r n = r n−2 − q n r n−1 .
(7.1)
Dans cette ´ equation, on substitue r n−1 = r n−3 − q n−1 r n−2 . L’´ equation (7.1) devient
r n = r n−2 (1 + q n−1 q n ) − q n r n−3 .
(7.2)
Dans cette ´ equation, on substitue r n−2 = r n−4 − q n−2 r n−3 . On it` ere. . . On obtient
finalement r n = r 1 x 1 + r 2 y 1 pour x 1 , y 1 ∈ Z. On substitue r 2 = b − r 1 q 2 , ce qui donne
r n = r 1 (x 1 − q 2 y 1 ) + by 1 .
On substitue r 1 = a − bq 1 pour finalement obtenir
r n = a(x 1 − q 2 y 1 ) + b(−q 1 x 1 + q 1 q 2 y 1 + y 1 ) = ax + by,
o` u x = x 1 − q 2 y 1 et y = −q 1 x 1 + q 1 q 2 y 1 + y 1 .
Remarque La preuve du corollaire 7.4 est tr` es importante. Elle donne la m´ ethode
pour trouver les entiers x et y tels que (a, b) = ax + by. Cette m´ ethode peut sembler
fastidieuse lorsqu’on l’applique ` a la main, mais elle se programme et s’ex´ ecute facilement
sur un ordinateur, mˆ eme si a et b sont grands. De mˆ eme, il est facile pour un ordinateur
de trouver le plus grand commun diviseur de deux nombres ` a l’aide de l’algorithme
d’Euclide pr´ esent´ e ` a la proposition 7.3.
Proposition 7.5 1. Soit c = (a, b). Alors, c est caract´ eris´ e par la propri´ et´ e suivante :
c = min{ax + by | x, y ∈ Z, ax + by > 0}.
7 La cryptographie ` a cl´ e publique
Preuve Montrons d’abord que r n | a et r n | b. Puisque r n+1 = 0, la derni` ere ´ equation
s’´ ecrit r n−1 = q n+1 r n . Donc, r n | r n−1 . L’avant-derni` ere ´ equation est : r n−2 = q n r n−1 +
r n . Comme r n | r n−1 , alors r n | q n r n−1 + r n . Donc, r n | r n−2 . On it` ere en remontant les
´ equations une `
a une. On obtient finalement que r n | r i pour tout i. Donc, r n | r 1 q 2 +r 2 =
b. Finalement, puisque r n | b et r n | r 1 , alors r n | bq 1 + r 1 = a. Donc, r n | a et r n | b, ce
qui entraˆ ıne que r n | (a, b).
Soit maintenant d un diviseur de a et de b. On doit montrer que d divise r n . Dans
ce cas-ci, on proc` ede en sens inverse. Puisque d | a et d | b, alors d | r 1 = a − bq 1 . Dans
la deuxi` eme ´ equation, on a d | b et d | r 1 , donc d | r 2 = b − r 1 q 2 . On it` ere et on obtient
d | r i pour tout i. En particulier, d | r n .
On peut donc conclure que r n = (a, b).
Corollaire 7.4 Soient a et b deux entiers et c = (a, b). Il existe x, y ∈ Z tels que
c = ax + by.
Preuve La preuve utilise la preuve de la proposition 7.3. On sait que c = r n . On
remonte les ´ equations une ` a une. Comme r n−2 = q n r n−1 + r n , alors
r n = r n−2 − q n r n−1 .
(7.1)
Dans cette ´ equation, on substitue r n−1 = r n−3 − q n−1 r n−2 . L’´ equation (7.1) devient
r n = r n−2 (1 + q n−1 q n ) − q n r n−3 .
(7.2)
Dans cette ´ equation, on substitue r n−2 = r n−4 − q n−2 r n−3 . On it` ere. . . On obtient
finalement r n = r 1 x 1 + r 2 y 1 pour x 1 , y 1 ∈ Z. On substitue r 2 = b − r 1 q 2 , ce qui donne
r n = r 1 (x 1 − q 2 y 1 ) + by 1 .
On substitue r 1 = a − bq 1 pour finalement obtenir
r n = a(x 1 − q 2 y 1 ) + b(−q 1 x 1 + q 1 q 2 y 1 + y 1 ) = ax + by,
o` u x = x 1 − q 2 y 1 et y = −q 1 x 1 + q 1 q 2 y 1 + y 1 .
Remarque La preuve du corollaire 7.4 est tr` es importante. Elle donne la m´ ethode
pour trouver les entiers x et y tels que (a, b) = ax + by. Cette m´ ethode peut sembler
fastidieuse lorsqu’on l’applique ` a la main, mais elle se programme et s’ex´ ecute facilement
sur un ordinateur, mˆ eme si a et b sont grands. De mˆ eme, il est facile pour un ordinateur
de trouver le plus grand commun diviseur de deux nombres ` a l’aide de l’algorithme
d’Euclide pr´ esent´ e ` a la proposition 7.3.
Proposition 7.5 1. Soit c = (a, b). Alors, c est caract´ eris´ e par la propri´ et´ e suivante :
c = min{ax + by | x, y ∈ Z, ax + by > 0}.