Calcul d'une congruence
dans Arithmétique
Bonjour,
Je suis en licence 2 d'informatique et je suis ici car je bloque dans un exercice d'arithmétique.
J'essaye de déchiffrer un message chiffré RSA or pour cela je dois pouvoir calculer 70^73 mod 159.
J'y ai passé des heures dessus, et je n'y arrive malheureusement pas.
J'ai essayé de trouver 70^73mod3 (=1) mais je bloque au niveau de 70^73mod53 (159=3*53).
Merci de me répondre (j'ai un examen dans 2h )
Je suis en licence 2 d'informatique et je suis ici car je bloque dans un exercice d'arithmétique.
J'essaye de déchiffrer un message chiffré RSA or pour cela je dois pouvoir calculer 70^73 mod 159.
J'y ai passé des heures dessus, et je n'y arrive malheureusement pas.
J'ai essayé de trouver 70^73mod3 (=1) mais je bloque au niveau de 70^73mod53 (159=3*53).
Merci de me répondre (j'ai un examen dans 2h )
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
On remarque que 73 = 64 + 8 + 1, et donc il suffit de calculer les puissances 1, 2, 4, 8, 16, 32 et 64èmes de 70 modulo 159 et de faire encore 2 multiplications (soit 8 au total).
Le tout peut se faire avec une calculatrice collège, en retenant quelques secondes dans sa tête la valeur de la puissance 8ème.
Sinon, puisque tu es en licence d'informatique, j'imagine que tu as accès à des ordinateurs et peut-être même à des logiciels de calcul.
En c++, en python, ou avec xcas, la commande est la même : powmod(70, 73, 159)
Avec WolframAlpha, tu peux même te contenter de taper : 70^73 mod 159
et pouf, tu as la réponse.
Mots-clefs: Algorithme d'exponentiation rapide. Voir les liens dans le message suivant:
http://www.les-mathematiques.net/phorum/read.php?5,1811278,1811384#msg-1811384
(ce sujet a fait l'objet de trois fils de discussion en moins d'une semaine)
Tant pis, voici quand même ma façon de résoudre ce genre de problème, très à la mode ces jours-ci :
Nelly05 cherche $x$, entier, tel que $70^{73}\equiv x\pmod{159}$.
$70$ et $159$ étant premiers entre eux, le petit théorème de Fermat généralisé par Euler donne :
$70^{\phi{(159)}}\equiv 1 \pmod{159}$.
Or, $\phi{(159)}=\phi{(3\times 53)}=(3^1-3^0)(53^1-53^0)=2\times 52=104$.
Donc, $70^{104}\equiv 1\pmod{159}$.
Il s'ensuit que, s'il existe un entier $n$ strictement positif et inférieur à $104$ tel que $70^n\equiv 1 \pmod{159}$, alors $n$ est un diviseur de $104$.
Puisque $104=2^\color{red}3\color{black}\times 13^\color{red}1$, $104$ possède $(\color{red}3\color{black}+1)(\color{red}1\color{black}+1)=8$ diviseurs, qui sont $1, 2, 4, 8, 13, 26, 52, 104$, ce qui permet, avec une simple calculette, la création du tout petit tableau suivant, où les puissances de $70$ sont calculées modulo $159$ (qu'on me pardonne ce raccourci de langage) :
\begin{array}{|c|c|c|c|c|c|c|c}
\hline
puissance & 1 & 2 & 4 & 8 & 13 & 26 & \\
\hline
70 & 70 & 130 & 46 & 49 & 52 & 1 & \\
\hline
\end{array}
(A noter que $70^{13}=70^8\times 70^4 \times 70^1$.)
Donc :
$x\equiv 70^{73}\equiv (70^{26})^{2}\times 70^{21}\equiv (1)^2\times 70^{21}\equiv 70^{21}\equiv 70^8\times 70^{13}=49\times 52\equiv 4\pmod{159}$.
Donc $x=4+159k$ $(k\in \mathbb{Z})$.
-- Schnoebelen, Philippe