Sept puissance 256 compte 217 chiffres et on n'en écrit aucun
Publié le 27/10/2026 · 3 min de lecture · Calculateurs du quotidien
Daniel Okonkwo — Développeur front-end et rédacteur Tech chez OneKitly
Performance web · Formats de fichiers
Vérifié à partir de 2 sources
Sept élevé à la puissance 256 est un nombre de 217 chiffres, et trouver son reste dans la division par treize n'en exige aucun. L'astuce est que le reste se prend à chaque étape : élève sept au carré pour obtenir 49, réduis à 10, élève au carré pour obtenir 100, réduis à 9, et continue — huit élévations au total, car 256 vaut deux puissance huit, et la réponse est 9. La même méthode traite 2¹⁰⁰⁰ modulo 1 000 000 007 et rend 688 423 210 alors que la valeur honnête compte 302 chiffres. Aucun nombre intermédiaire ne dépasse jamais le carré du module, et c'est ce qui rend le calcul possible sur une machine à entiers de taille fixe.
7²⁵⁶ mod 13 vaut 9, et 2¹⁰⁰⁰ mod 1 000 000 007 vaut 688 423 210. Les deux sortent de huit ou dix élévations au carré, sans qu'aucun nombre du calcul ne dépasse le carré du module.
Huit multiplications au lieu de deux cent cinquante-cinq
Calculer une puissance par multiplications répétées coûte une étape par unité d'exposant. Élever au carré double l'exposant à chaque fois : atteindre 256 prend huit étapes et non 255, et atteindre un exposant à trois cents chiffres en prend un millier environ. Un exposant qui n'est pas une puissance de deux se traite en l'écrivant en binaire et en élevant au carré à chaque bit, en multipliant par la base là où le bit vaut un — d'où la description courante de la méthode comme une lecture des chiffres binaires de l'exposant d'un bout à l'autre. Le coût est proportionnel au nombre de bits de l'exposant, non à l'exposant lui-même.
Pourquoi ces huit étapes prennent un temps constant
Chaque valeur intermédiaire est réduite aussitôt : elle reste sous le module et son carré tient dans le double de la largeur du module. Cette borne explique que le travail par étape ne croisse pas avec l'exposant, et qu'une implémentation puisse dimensionner son arithmétique une fois pour toutes. Elle explique aussi l'échec cuisant de l'alternative naïve : calculer d'abord le nombre à 217 chiffres puis réduire à la fin est mathématiquement correct et réclame une arithmétique à précision arbitraire, plusieurs centaines d'octets par valeur, et bien plus de temps que tout le calcul modulaire.
| Expression | Chiffres si écrit en entier | Résultat |
|---|---|---|
| 7²⁵⁶ mod 13 | 217 | 9 |
| 2¹⁰⁰⁰ mod 1 000 000 007 | 302 | 688 423 210 |
Questions fréquentes
- Pourquoi 1 000 000 007 revient-il si souvent comme module ?
- Parce qu'il est premier, juste sous le milliard, et que son carré tient dans un entier de soixante-quatre bits. Être premier signifie que toute valeur non nulle possède un inverse multiplicatif : la division fonctionne et rien ne dégénère. Être juste sous le milliard garde les résultats lisibles et rend rares les collisions dans un usage de type hachage. Que son carré tienne dans un mot machine permet de multiplier deux valeurs réduites sans débordement et sans arithmétique à précision arbitraire. Ces trois propriétés réunies expliquent à elles seules la fréquence de ce nombre dans les énoncés de programmation compétitive.
- Le temps de calcul laisse-t-il fuir quelque chose ?
- Oui, et c'est une vraie classe d'attaques, non une inquiétude théorique. La version naïve ne multiplie que là où un bit de l'exposant vaut un : le temps d'exécution dépend donc du nombre de bits à un — et quand l'exposant est une clé privée, c'est de l'information qui quitte la machine par l'horloge. Les implémentations sérieuses effectuent donc la multiplication sans condition et jettent le résultat quand le bit est nul, payant un coût constant pour rendre le temps indépendant du secret. La même discipline réapparaît partout où un branchement dépend de données privées.
Articles qui pourraient t'intéresser
Tous les guides →Outils similaires
Sources
Tu as repéré une erreur dans cet article ?