Calcul de li'nverse modulaire

[adel87]

bonsoir à tous le monde je voudrais savoir comment je peut calculer l'inverse modulaire je suis vraiment perdu car je suis un étudiant en informatique j'ai besoin de ca dans la module de crypto
merci

[Mathusalem]

bonsoir à tous le monde je voudrais savoir comment je peut calculer l'inverse modulaire je suis vraiment perdu car je suis un étudiant en informatique j'ai besoin de ca dans la module de crypto
merci

Salut, tu cherches y tel que x*y congru 1 mod (p) n'est-ce pas ?

En particulier, tu cherches x*y - k*p = 1

Tu cherches donc y et k. Ceci peut se résoude par l'algorithme d'euclide étendu (l'algorithme est sur le net).

Sinon, tu peux faire une boucle (C++)

while ((x*y)%p != 1)
{ y = y + 1 }
en initialisant y a 1 ou 0... le problème de ça c'est la complexité est supérieure a l'algorithme d'euclide etendu, ça dépend du "p" choisi.