Exponentiation modulaire

Ce calculateur réalise l'exponentiation d'un grand nombre entier selon un module. Un algorithme rapide est utilisé, décrit juste en-dessous du calculateur.

Exponentiation modulaire

Base

Exposant

Module

Calculer

Résultat

 

 Lien  sauvegarder  Widget

Algorithmes rapides d'exponentiation

La mise en œuvre la plus simple de l'exponentiation nécessite N-1 multiplications, où N est un exposant de base.
Malgré toute la puissance des ordinateurs modernes, cette méthode ne nous convient pas puisque nous utiliserons des nombres pour l'exposant plus grand que des entiers standards de 64 octets. Ex. le nombre premier de Mersenne : 618970019642690137449562111 utilisé comme valeur d'exposant par défaut à 89 octets (voir Longueur binaire).
Pour gérer de tels exposants en toute sécurité, nous devons utiliser des algorithmes rapides d'exponentiation.

Dans le calculateur Expansion de la puissance polynomiale, nous avons déjà utilisé l'algorithme d'exponentiation basé sur un arbre de puissance. Il permet de minimiser grandement le nombre de multiplications. Néanmoins, nous ne pouvons pas l'utiliser avec des exposants énormes puisque l'arbre d'exponentiation consomme trop de mémoire.
Ce calculateur utilise la mise en œuvre libraire bigInt de l'algorithme rapide d'exponentiation modulaire basé sur la méthode binaire. Le même article décrit une version de cet algorithme qui traite les chiffres binaires du moins important au plus important (de gauche à droite). C'est un inconvénient dans notre cas, puisque nous utilisons des entiers avec des longueurs d'octets variables et nous ne connaissons pas la position de l'octet le plus important à l'avance.

Algorithme d'exponentiation binaire (droite à gauche).

Ainsi, l'algorithme que nous utilisons pour gérer les octets des exposants du moins important au plus important (de droite à gauche).
Le pseudocode de l'algorithme :

a //base
e //exposant
m //module
 //exponentiation modulaire
r ⟵ 1      
while (e!=0) {
            if (e mod 2 = 1) r ⟵ r * a mod m;
            e ⟵ e / 2;
            a = a*a mod m;
        }
output ⟵ r