Le nombre 2^100 est 1267650600228229401496703205376, trente et un chiffres, et l'écran l'affiche comme 1.2676506002282⋅10+30. Demandez 2^100 mod 7 dans la même fenêtre et la réponse est 0. Demandez 2^4 mod 7 et c'est 2, ce qui est la bonne : 2^3 = 8 ≡ 1 (mod 7), donc 2^99 ≡ 1 et 2^100 ≡ 2, ou de façon équivalente 2^6 ≡ 1 et 100 mod 6 = 4 réduisent toute la question à 2^4 mod 7.
La puissance n'a rien de faux ; le reste, si. Un double garde cinquante-trois bits, donc la valeur représentable la plus proche de 2^100/7 s'écarte d'environ 10^13, et un reste calculé comme a − 7·floor(a/7) hérite d'une erreur bien plus grande que le module. La bonne méthode ne laisse jamais le nombre grossir : réduire d'abord et élever ensuite, ce qui est exactement ce que fait l'exponentiation modulaire dans toute bibliothèque cryptographique, et la raison pour laquelle le RSA peut travailler avec des nombres de mille bits sur du matériel qui en garde cinquante-trois. C'est le même plafond qui fait de 2^53 le dernier compteur entier exact.
Réponse
0
Comment la lire
2^100 mod 7 sur l'espace de travail : la réponse de la machine, pas celle de l'arithmétique. Le deuxième lien est 2^6 mod 7 = 1, la période ; le troisième est la question réduite 2^4 mod 7 = 2, qui est la vraie valeur.
Source
2^100 = 1267650600228229401496703205376 is exact in binary floating point, being a power of two, but the quotient by 7 has thirty significant digits and IEEE-754 binary64 carries only about sixteen, so a mod implemented as a − b·floor(a/b) returns a remainder taken from the rounded quotient
Résolvez-le dans la calculatrice
Ces liens ouvrent la calculatrice appropriée avec les nombres de ce problème déjà saisis. La ligne ci-dessus correspond à ce que l'écran devrait afficher : vérifiez par vous-même.