Tests de primalité probabiliste

• En practique, on fabrique des nombres aléatoires et l'on teste leur primalité jusqu'a l'obtention d'un premier.
  
  
•  Théorème de raréfaction des nombres premiers:
  
  

Le nombre des premiers inférieures à n est environ  


• Donc pour p modulus 512 bits, on tire en moyenne  (environ 177) nombres avant d'obtenir un premier.
•  Il faut tester la primalité !!!!
  
  
•  Pas d'algorithmes deterministes mais d'algorithmes probabilistes
  
  
•  Algorithmes probabilistes:
1. Bits aleatoires (face ou pile)
   
   
2.  probabilite d'erreur < 1/2
   
   
3.  Temps polynomial
   
   
4.  MonteCarlo, Las Vegas etc ...
   
   
5.  RP, BPP , etc