Algorithme de Rabin-Miller

1. écris  où m est impair
   
   
2.  tire un entier aléatoire  
   
   
3.  
   
   
4. si  alors

réponds n est premier et fin.
 
5.  pour i=0 jusqu'à k-1 fais
   
   
6.  si  alors

réponds n est premier et fin.

sinon 
 

7. réponds n est décomposable

 

 

• Complexité  
  
  
• Nombre pas premier pas d'erreur, mais parfois il dit non premier pour un premier
  
  
•  Probabilité d'erreur < 1/4
  
  
•  En pratique, on utilise cet algorithme. Pourquoi?