Inscription / Connexion Nouveau Sujet
[Spé] Calcul de l'inverse modulo
Bonsoir!
J'éprouve quelques difficultés à trouver l'inverse d'un modulo, chose bien utile pour les exercices de cryptage/décryptage!
Je pense avoir la méthode, mais je coince sur certains cas bien précis...
Par exemple, 17u≡1[26]. Je sais que u=23, mais seulement en faisant des essais (en essayant chaque possibilité).
Je pensais à dire que 17u=26k+1, et du coup résoudre grâce à l'algorithme d'Euclide, mais je trouve un truc assez bizarre...
En fait, comme on est intéressé que par u et pas k finalement, ça coince car je trouve -1 avec l'algorithme d'Euclide (même sur ma calculette) : en effet, 17*-3=51 et 26*2=52, mais donc on trouve 1 avec 26*2>17*-3...
Du coup, je trouve juste que 17*-3≡-1≡25[26], et non pas la réponse que je cherche (càd 17u≡1[26])
Quelqu'un aurait une idée du pourquoi? 
Pour l'algorithme sur ma calculette, c'est pourtant censé me donner le reste de la division (donc 1, et non -1) et les coefficients pour y parvenir... Je coince donc, pour résumer, dès que le reste est -1 et non 1!
Merci d'avance!
Bonsoir, tu t'es emmèlé les pinceaux.
On reprend:
Tu cherches une solution particulière à l'équation 17x=26y+1. Autrement dit, l'équation 17x-26y=1. Ta solution particulière déjà c'est (-3,-2) et pas (-3,2).
Ensuite, tu as 17.(-3)=-51=-25=1 mod 26 et non pas -1.
De façon général comment trouver un inverse? En te servant de ta relation de Bézout que tu as trouvé: 17.(-3)-26.(-2)=1 d'où 17.(-3)=1+26.2 et donc modulo 26 on a: 17.(-3)=1.
Donc, étant donné a et b deux entiers si on te demande de trouver u tel que au=1 mod b alors la méthode générale c'est de trouver une relation de Bézout entre a et b.
(Remarque que un tel u existe si et seulement si il existe une relation de Bézout entre a et b autrement dit si et seulement si a et b sont premiers entre eux.)
Annuler
connectez vous