Factorisation

Plusieurs méthodes sur crible quadratique, crible algébrique, courbes elliptiques. Algorithme  , méthode p-1 de Pollard, méthode p+1 de Williams, fractions continues, crible d'Erastostène, etc, etc.

La méthode p-1

• Soient: n le nombre à factoriser,
• B une borne (limite la complexité)
• et un nombre quelconque g compris entre 2 et n-1.
  
  
1. 
2. pour j=2 jusqu'à B fais  
   
   
3.  
   
   
4. si 1 < d < n alors d est un facteur de n succès
   
   
5.  sinon aucun facteur trouvé échec

 

 

• Complexité  
  
  
• Donc si B est  l'algorithme est polynomial mais la probabilité de succès est très faible
•  Si on augmente B jusqu`a  l'algorithme réussira mais il devient exponential
  
  
•  En pratique: réseaux d'ordinateurs. (ex. 116 chiffres - 4000 mips-an - millions d'instructions per second pendant un an)
  
•  RSA Data Security: RSA Factoring Challenge - une liste des nombres difficiles
  
  
  
1. RSA-100, RSA-120, RSA-129 on été factorisés - crible quadratique
   
   
2.  et on 12 aout 1999 - RSA 155 a été (512 bits) factorisé !!!!!!
   
   
3.  avec:
   160       175-400 MHz SGI and Sun workstations
   8           250 MHz SGI Origin 2000 processors
   120      300-450 MHz Pentium II PCs
   4           500 MHz Digital/Compaq boxes
   
   
4.  8000mips pendant 3,7 mois. En fait plus 7 mois de preparation !!!!!