Exponentiation modulaire

• Supposons que n a k bits (donc  ).

 
•  Méthodes trivielles:


• addition: O(k)

 
•  multiplication: 
• réduction mod n : O(k)

 
•  donc multiplication modulaire (multiplication + réduction): 
• exponentiation modulaire:  (c fois multiplication). Combien ???

 
•   . Pourquoi ?

 
• Donc: Square-and-multiply.


Soit  , avec  . Alors :

1.   
2.   pour i=l-1 jusqu'à 0 fais
3.   
4.   si  alors 
• le dernier 

 
• complexité