Justification du cryptage RSA
Deuxième partie : Théorèmes préliminaires

Les théorèmes suivants vont servir dans la suite de la démonstration.

 

Soient a, b de N^*

Alors, il existe (k, k’) de Z² tels que a L b = ka + k’b

 

Démonstration

Soient a, b de N*

On note aZ + bZ = { ka + k’b / (k, k') appartient Z²}

On note a L b le plus petit élément de C=(aZ + bZ) Ç N^*

a L b existe car C contient a et b donc est non vide. a L b est appelé pgcd de a et b.

                                                  

Montrons que si n appartient à  aZ  + bZ, alors a L b divise n :

Soit n de aZ + bZ. La division euclidienne de n donne :

n = (a L b) q + r avec 0 £ r < a L b

n appartient à aZ + bZ

(a L b)q appartient à aZ + bZ donc r appartient à aZ + bZ et r = 0 car 0 £ r < a L b et que a L b est le plus petit élément de C.

Donc a L b divise n.

                                                                                                     

On a alors a L b divise a car a appartient à aZ + bZ et a L b divise b car b appartient à aZ + bZ.

 

Le théorème de Bézout est donc démontré car a L b appartient à aZ + bZ.

                                                     

                                                     

Soit d de Z*

Si d divise a et d divise b,

Alors d divise a L b.

 

Démonstration :

d divise a donc a s’écrit a = ad

d divise b donc b s’écrit b = bd, avec (a, b) de Z²

 

Donc d’après le théorème de Bézout,

a L b = kad +  k’bd

a L b = d(ka + k’b)

 

 

a et b sont premiers entre eux si et seulement si a L b = 1

 

 

Soit (a, b) de N*²

Soit c de N,

Si a divise bc et que a L b = 1, alors a divise c

 

Démonstration :

a L b = 1 donc (Bézout)  au + bv = 1

acu + bcv = c

Or a divise ac, a divise bc,

Donc a divise c.

 

 

Soit (a, b) de N*2

Soit c de Z

Si a divise c, si b divise c, avec a L b = 1, alors ab divise c.

 

Démonstration :

a divise c. Donc c = aa

b divise c. Donc c = bb

 

D’où aa = bb.

Donc a divise bb.

Or a L b = 1, donc d’après le théorème de Gauss, a divise b,

Donc b peut s’écrire b = ak

On a alors c = abk

 

ab divise donc bien c.

 

 

Soit (a, b) de N*2

Si a L b = 1 et si a L c = 1

Alors, a L bc = 1

 

Démonstration :

a L b = 1. Donc au + bv = 1

a L c = 1. Donc au’ + cv’ = 1

au + bv(au’ + cv’) = 1

au + abvu’ + bcvv’ = 1

a(u + bu’v) + bc(vv’) = 1

a L bc = 1

 

 

Si a º b [n] , alors ap º bp [n]

 

Démonstration :

a º b [n]. Donc n divise a – b

Or pour tout entier naturel p ³ 1,

a^p – b^p est un multiple de a – b

Donc n divise a^p – b^p.

Donc a^p º b^p [n]

 

 

Soit a de N

Soit p premier avec a (p L a = 1)

Alors, ap º a [p]

 

Démonstration :

Montrons tout d’abord que, p étant premier,

i appartenant à [1, p-1],

alors p divise les .  

Démonstration :

p ! = i !(p-i) !

p est premier avec tous les nombres compris entre 1 et p-1 puisque p est premier :

p L1, p L2, p L 3…, p L p-1                         

D’après le théorème f, p L i ! = 1

De même, p L (p-i) ! = 1

Donc, toujours d’après le théorème f,

p L (p-i) !(i) ! = 1

et comme p divise p ! et que p !=  (i !)(p-i) !

D’après le théorème de Gauss, p divise alors

 

On peut maintenant démontrer le petit théorème de Fermat par récurrence :

 

- 0^p º 0 [p]  

- Si a^p º a [p],

alors (a + 1)^p = º a^p + 1 [p] , car p divise lorsque 0 < i < p

donc (a + 1)^p º a + 1 [p]

                                  

Le théorème de Fermat est donc démontré.

 

 

Soit a de N

Soit p L a = 1

Alors ap-1 º 1 [p]

 

Démonstration :

a^p º a [p] signifie que p divise a^p – a

Or a^p – a = a(a^p-1 – 1)

Donc p divise a(a^p-1 – 1)

D’après le théorème de Gauss, p étant premier avec a,

p divise a^p-1 – 1, soit a^p-1 º 1 [p]

 

 

Soit p de N, avec p premier

Soit a de N

 

Alors, ak(p-1)+1 º a [p]

 

Démonstration :

- Si a L p = 1, alors d’après le théorème de Fermat,       

a^p-1 º 1 [p]

a^k(p-1) º 1 [p] (d’après le théorème g)

a^k(p-1)+1 º a [p]

- Si p divise a, alors a^k(p-1)+1 est divisible par p,

et a^k(p-1)+1 º 0 º a [p]