Calcul de l'exposant de déchiffrement

• La conaissance de a permet de déchiffrer le texte !!!
  
  
  
•  Mais aussi de factoriser n. 
  
  Donc si a est révélé, Bob devra changer b et a et aussi n !!!!
  
  
•  Algorithme de factorisation utilisant a
1. tire w < n aleatoire
   
   
2.  
3. si x < n alors succès x=p ou x=q
   
   
4.  
5. écris  , r impair
   
   
6.   
   
   
7. si  alors fin échec
   
   
8.  tant que  fais
9.  
10.  
    
    
11. si  alors fin échec
12.  sinon  succès x=p ou x=q
    
    
• Exemple: n=89855713 et b=34986517 et a=82330933. Tirons w=5
  
  
• 
• étape 6: v=885877701
  
  
•  étape 10: v=1
  
  
•  étape 12: pgcd (85877702,n) = 9103
  
  
  
•  Donc p=9103 et  
  
  
• Algorithme Las Vegas. Pourquoi ?
  
  
  
•  Complexité ??
  
  
•  Probabilté de succès