Bonjour,
Je voudrais savoir si quelqu'un peut m'aider à résoudre deux petites equations modulaires. Je me rappel plus comment on fait. J'en ai besoin pour faire du cryptage RSA. Ma première équation, je dois trouver un d tel que:
7*d.mod(55)=1
Quel est la démarche pour trouver d?
ma deuxième équation est de la forme:
10^7.mod(55)=?
J'ai essayé avec le petit théorème de Fermat, mais ça marche pas.
Salut et bienvenue,
pour la première question, utilise l'algorithme d'Euclide étendu (à 7 et 55). Fais une recherche sur google pour te rafraîchir la mémoire au besoin.
Pour la seconde, 10^2=-10 mod 55 donc 10^7=(-10)^3.10=-10^4=-10^2=10 mod 55.
Cordialement.
Merci beaucoup pour ton aide. Pour la première équation, je crois qu'il faut reconnaitre une identité de Bezout: 7d = 1 + 40*k
Je me rappellais plus qu'il fallait utiliser l'algo d'Euclide pour d. Maintenant c'est bon.
Par contre pour la seconde équation, il y a un théorème ou bien c'est intuitif?
En tout cas merci pour ton aide.
Pour la seconde, il fallait trouver une puissance de 10 sympathique modulo 55. Il se trouvait que 103 avait bonne mine. Sinon, il aurait fallu continuer, ou être "plus astucieux".
Cordialement.
