Exponentiation par carrés
Un article de Wikipédia, l'encyclopédie libre.
 |
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).
|
La méthode de l'exponentiation par carrés consiste en cela : on désire calculer abmod n
La méthode de base consiste à calculer ab de manière directe. Ceci demande une puissance de calcul trop importante.
La méthode consiste à décomposer b sur la base 2.
Ainsi on calcule les a2k puis on retrouve ab en sommant les a2k résultant de la décomposition de b sur la base 2. Cette méthode permet une diminution de la complexité de b vers Log(b).
