Pour le RSA, il n'y a rien de mieux qu'un premier aléatoire, sur lequel on n'a a priori aucune information. L'idée est alors de prendre un entier de 500 chiffres au hasard, et de tester s'il est premier : si c'est le cas, on le garde, sinon on choisit un autre nombre au hasard, jusqu'à finir par tomber sur un premier. Cela pose deux problèmes. D'abord, il faut que l'on puisse trouver un premier au bout d'un nombre raisonnable de tirages. Un théorème conjecturé par Gauss, et démontré par de la Vallée Poussin, affirme que si P(n) désigne le nombre de nombres premiers plus petits que n, alors :

Ainsi, si l'on choisit un nombre de 500 chiffres au hasard, on a environ une chance sur ln(10⁵⁰⁰) de tomber sur un premier, c'est-à-dire environ une chance sur 1150. Tout cela reste très raisonnable!

D'autre part, il faut que, étant donné un entier n, on puisse rapidement déterminer s'il est premier ou non. Il faut donc des tests de primalité efficaces. Le plus rudimentaire est de prendre tour à tour tous les nombres entre 2 et racine de de n, et vérifier s'ils divisent ou non n. Mais cet algorithme est bien trop naïf, car il nécessite 10²⁵⁰ calculs environ pour un nombre de 500 chiffres. Impossible! On a donc recours à d'autres tests, les tests de Solovay-Strassen et Miller-Rabin. Leur particularité est d'être des algorithmes probabilistes : ils répondent "n est probablement premier", avec une probabilité très grande (et que l'on peut ajuster). En général, en cryptographie, on se contente de nombres dont on sait qu'ils sont premiers avec une probabilité supérieure à 1-1/2¹⁰⁰ .

Algorithme d’Euclide :

Soit (a, b) Î ℕ´ℕ*. Si a = b q + r, alors : D(a)∩ D(b)= D(r)∩ D(b) et par conséquent a Ù b= b Ù r

Démonstration :

Si dÎ D(a)∩ D(b), alors dï (b q) et dï a, donc dï (a - b q) = r par suite dÎ D(r)∩ D(b)
Par symétrie, puisque r = a - b q, on a aussi D(r)∩ D(b) Î  D(a)∩ D(b)
D’où l’égalité :  D(a)∩ D(b)= D(r)∩ D(b)
et dons les plus grands éléments de D(a)∩ D(b) et D(r)∩ D(b) sont égaux, ce qui donne le résultat.

Coefficients de Bézout :

Il existe des entiers relatifs u et v tels que :
a u + b v = a Ù b
Un tel couple (u, v) est appelé un couple de coefficients de Bézout de a et b.

Démonstration :

Quitte à remplacer a par ïaïet b par ïbï, il suffit de traiter le cas où a et b sont des entiers naturels.
Démontrons par récurrence sur b Î ℕ la propriété H_b : « Pour tout entier naturel a, il existe (u, v) Î ℤ² tel que  a u + b v = a Ù b ».
       
        H₀ est vraie car  a ´ 1 + 0 ´ 0 = a = a Ù 0.
       
        Supposons la propriété vraie jusqu’au rang b-1, avec b Î ℕ^*. Soit a Î ℕ ;  notons d le PGCD de a et b. on effectue la division euclidienne de a par b :
               a = b q + r     avec  0 < r £ b.
        Nous avons donc d = b Ù r (Algorithme d’Euclide) et la propriété H_r montre qu’il existe (u', v') Î ℤ² tel que :
         b u' + r v' = d
        On a donc :
     b u' + ( a – b q ) v' = d
        ce qui donne :
        a u + b v = d
        avec  u = v' et v = u' – q v'. D’où H_b.

Identité de Bézout :

Les entiers a et b sont premiers entre eux si, et seulement si, il existe (u, v) Î ℤ² tel que
a u + b v = 1

Démonstration :

Si a et b sont premiers entre eux, alors a Ù b = 1 et d’après la proposition « coefficients de Bézout », il existe  (u, v) Î ℤ² tel que  a u + b v = a Ù b  = 1.

S’il existe deux entiers relatifs u et v tel que  a u + b v = 1, alors tout diviseur commun à a et b divise a u + b v donc est égal à 1 ou à –1. On en déduit que a et b sont premiers entre eux.

Théorème de Gauss :

Etant donnés trois entiers relatifs a, b et  c on a :
(a Ù b =1  et  aï b c ) →  aï c

Démonstration :

Supposons a Ù b = 1 et aï b c. D’après l’identité de Bézout, il existe deux entiers relatifs u et v tels que  a u + b v = 1, ce qui implique a c u + b c v = c.
Comme aï b c, on a  aï b c v et donc :

aï b c v + a c u = c

Petit théorème de Fermat :

Soit p un nombre premier et a un entier naturel premier avec p alors :
a^{p – 1} – 1 est divisible par p

Démonstration :

p ne divise aucun nombre de la suite a, 2a, 3a, …, (p – 1)a. En effet, d’après le théorème de Gauss, si p divisait un de ces produits k a, p diviserait k puisque a et
p sont premiers entre eux. Ceci est impossible puisque 1<k<p.
De plus les restes des divisions de a, 2a, 3a, …, (p – 1)a par p sont tous différents. Si on trouvait des restes identiques pour k a et k’ a ( k>k’) alors le reste de (k-k’)a par p serait nul, ce qui est impossible d’après ce qui précède.
Donc à l’ordre près des facteurs les restes de a, 2a, 3a, …, (p – 1)a par p sont 1, 2, 3, …, (p-1).
Par conséquent la division du produit  a ´ 2a ´ 3a ´…´ (p – 1)a a pour reste le produit 2´3´…´(p – 1)
donc a^{p - 1}´2´3´…´(p – 1) est congru à 2´3´…´(p – 1) modulo p                  (    a^{p – 1}(p-1) !≡ (p-1) ![p])    ).
Comme p est premier, a^{p – 1} congru à 1 modulo p

      Théorème des restes chinois :

Prenons m₁, ..., m_n des entiers supérieurs à 2 deux à deux premiers entre eux, et a₁,...,a_n des entiers.

Le système d'équations :
x=a₁ mod m₁
...
x=a_nmod m_n
admet une unique solution modulo M=m₁×...×m_n donnée par la formule :
x=a₁M₁y₁+...+a_nM_ny_n mod M
où M_i=M/m_i, et y_i=M_i-1 mod m_i pour i compris entre 1 et n.

Exemple : Une bande de 17 pirates s'est emparée d'un butin composé de pièces d'or d'égale valeur. Ils décident de se les partager également, et de donner le reste au cuisinier chinois. Celui-ci recevrait alors 3 pièces. Mais les pirates se querellent, et six d'entre eux sont tués. Le cuisinier recevrait alors 4 pièces. Dans un naufrage ultérieur, seuls le butin, six pirates et le cuisinier sont sauvés, et le partage donnerait alors 5 pièces d'or à ce dernier. Quelle est la fortune minimale que peut espérer le cuisinier quand il décide d'empoisonner le reste des pirates?

Si x est ce nombre, x est le plus petit entier positif tel que :
x=3 mod 17.
x=4 mod 11.
x=5 mod 6.
On applique le théorème chinois : on a M=17×11×6=1122, M1=66, M2=102, M3=187. L'inversion de chaque Mi (par l'algorithme d'Euclide) donne y1=8, y2=4, y3=1.

On obtient donc :
x=3×66×8+4×102×4+5×187×1 mod 1122 = 785 mod 1122.

785 pièces d'or, voila qui reste particulièrement motivant!

Le théorème d'Euler

           Accueil