Calcul modulo
dans Arithmétique
Bonjour
Existe-t-il une méthode pour calculer $a^b \pmod n$ à la main ? Par exemple : calculer $23^7 \pmod{661}$.
Merci d'avance.
Existe-t-il une méthode pour calculer $a^b \pmod n$ à la main ? Par exemple : calculer $23^7 \pmod{661}$.
Merci d'avance.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
$23^{50} \equiv ? \pmod{68}$
$\equiv 23^{(32+16+2)} \equiv 23^{32} 23^{16} 23^2 \pmod{68}$
$23^2 \equiv 53 \pmod{68}$
$23^4 \equiv (23^2)^2 \equiv 53^2 \equiv 21 \pmod{68}$
$23^8 \equiv (23^4)^2 \equiv 21^2 \equiv 33 \pmod{68}$
$23^{16} \equiv (23^8)^2 \equiv 33^2 ... \pmod{68}$
...
...
Pour calculer des puissances, la méthode indiquée par soland est efficace. Variante récursive (pas top à la main peut-être ?) : $a^b=a^{b/2}$ si $b$ est pair et $a^b=a\cdot a^{(b-1)/2}$, ce qui conduit à faire entre $\log_2(b)$ et $2\log_2(b)$ multiplications.
Ensuite, il y a la question du calcul modulo $n$ : il semble clair qu'il faut prendre le temps de réduire modulo $n$ le résultat de chaque multiplication (c'est-à-dire de remplacer le résultat par son reste dans la division euclidienne par $n$).
Si on a à faire à la main un calcul où $b$ est très grand, il semble utile de trouver l'ordre multiplicatif de $a$, c'est-à-dire le plus petit $o$ tel que $a^o=1\pmod{n}$ (si $a$ est bien premier avec $n$). On divise $b$ par $o$, disons $b=qo+r$ avec $0\le r<o$, et $a^b=a^o\pmod{n}$. Dans le cas de $23^7$, ça ne s'applique pas (l'ordre de $23$ modulo $661$ se trouve être $660$, le plus grand possible).