Calculateur d'exponentiation modulaire

L'exponentiation modulaire calcule le reste obtenu lorsqu'une base entière est élevée à un exposant entier positif ou nul, puis divisée par un module positif. L'expression a^b mod m désigne l'unique reste entre 0 et m - 1 congru à a^b. Un calcul direct devient vite impraticable, car les puissances atteignent des tailles immenses, même si le reste final est petit. Ce calculateur évite de construire cet énorme entier intermédiaire. La méthode efficace est appelée exponentiation binaire, carrés successifs ou méthode par carrés et multiplications. On écrit l'exposant en binaire et on traite ses bits. La base est d'abord réduite modulo m. À chaque étape, le facteur courant est élevé au carré modulo m. Si le bit correspondant de l'exposant vaut un, ce facteur est multiplié au résultat, immédiatement réduit à nouveau modulo m. Chaque valeur intermédiaire étant réduite, les valeurs restent inférieures au carré du module. Cet algorithme nécessite un nombre d'étapes proportionnel au logarithme de l'exposant. Calculer une puissance d'exposant un milliard ne demande donc qu'environ trente étapes de mise au carré, plutôt qu'un milliard de multiplications répétées. Le décompte affiché distingue les carrés des multiplications sélectionnées correspondant aux bits de valeur un de l'exposant. Un exposant nul renvoie bien 1 mod m. L'arithmétique modulaire considère comme équivalents les nombres ayant le même reste. Par exemple, 17 et 5 sont congrus modulo 12, car ils donnent tous deux un reste de 5. Une base négative est également acceptée : elle est d'abord normalisée en un résidu non négatif. L'exposant doit être positif ou nul dans ce calculateur. Les exposants modulaires négatifs nécessitent un inverse multiplicatif modulaire, qui n'existe que si la base et le module sont premiers entre eux. Les puissances modulaires sont essentielles en théorie des nombres et en cryptographie moderne. Le chiffrement et les signatures RSA élèvent des messages à de grandes puissances modulo un nombre composé. L'échange de clés Diffie-Hellman et de nombreux systèmes à logarithme discret utilisent des puissances modulo un nombre premier. Cette opération intervient aussi dans les tests de primalité, les générateurs pseudo-aléatoires, les sommes de contrôle, les motifs cycliques et les concours de programmation. Les trois champs sont traités comme des entiers exacts de taille arbitraire, et non comme des nombres à virgule flottante. Les valeurs dépassant la limite habituelle des entiers sûrs de JavaScript conservent donc tous leurs chiffres. Le module doit être supérieur à un, sans virgule ni point décimal dans les saisies. Pour une vérification manuelle, réduisez d'abord la base, puis vérifiez de petits exposants par multiplications successives en prenant le reste à chaque étape.