Algorithme d'Euclide

• FAIT:

 

 


 

• On dit que b est premier avec n

 
•  Algorithme d'Euclide pour calculer le plus grand diviseur commun de deux entiers  et  :


• 
• 
• 
• 
•  
• avec 

 
• 

 
• Alors, on fait  et  et on vérifie si pgcd(n,b)=1
  
  
•  Deux possibilites: b est inversible alors comment calculer l'inverse  ???
  
  

 
•  Ou b n'est pas inversible et il faut choisir un autre b et recommencer.
  
  

 
•  FAIT: Le nombre des entiers premiers avec n est  . Donc , pour RSA ????