Algorithme quand tu nous tiens : conditions logiques

Bonjour,

je suis en train de ramer sur les conditions logiques. Je demande à l'utilisateur d'entrer deux nombres a et b tant que le PGCD(a,26) est différent de 1 et que l'inverse modulaire de a par 26 est égal à -1 (retour d'erreur).

Code:

---

1 2 3 4 5 6 7 8

//Initialisation de la clé do{ printf("Entrez la valeur \'a\' de la clef : "); scanf("%d",&a); printf("Entrez la valeur \'b\' de la clef : "); scanf("%d",&b); }while ((PGCD(a,26) != 1) && (inv_mod(a) == -1)); printf("Clef validee ! \n");

---

Ça à l'air tout simple, mais mon programme bug à cause de l'inverse modulaire un peu plus loin. Si ça bug, ça veut dire qu'il laisse passer des valeurs a et b non acceptables par la suite. J'ai beau faire des tables de vérité mais je ne trouve pas mon erreur.

Y aurait-il une âme charitable pour m'aider?

Merci d'avance :)

Avec ton code, la clé est jugée bonne si a et 26 sont premiers entre eux, ou si l'inverse modulaire de a ne renvoie pas -1 (ou les deux).
C'est ce que tu veux ?
Si la clé est bonne à condition que a et 26 soient premiers ET que inv_mod(a)!=-1, la condition est :

Code:

---

1 2	while ((pgcd(a,26)!=1) || (inv_mod(a)==-1))

---

Bonjour,

Juste une remarque : b n'est pas utilisé dans le code!!!

Il faut que les deux propositions soient respectées:
-PGCD(a,26) ==1
-inverse modulaire(a) != -1 (retour d'erreur de la fonction)

Pourquoi le "ou"?

Le b c'est normal, je m'en sers plus tard, mais il n'y a aucune vérification à faire dessus.

Citation:

---

Envoyé par v4np13

Pourquoi le "ou"?

---

regarde ce que tu veux : tu veux avoir "pgcd(a,26)==1 ET inv(a) !=-1)

donc tu boucls tant que cette condition n'est pas verifiée, cad qu'il suffit que l'une des 2 ne soit pas verifiée pour que le a soit mauvais. donc il faut tourner tant que : "pgdc(a,26)!=1 OU inv(a)==-1"

Je viens de tester avec le "ou", effectivement ça fonctionne mais il n'accepte plus aucune valeur à part 1 pour a. 8O Est-ce normal?

La fonction PGCD, je suis sur de son algorithme mais celle de l'inverse modulaire, je ne sais pas. Le prof nous a passé une fonction "bête et méchante" comme il dit pour le faire.

Code:

---

1 2 3 4 5 6 7 8 9 10

/**  * Retourne l'inverse modulaire, en cas d'erreur -1  */ int inv_mod(int a){ int i; for (i=0;i<26;i++){ if (a*(i%26) ==1) return i; } return -1; }

---

J'ai trouvé un de ses anciens slides de cours, où il donnait la clé K(15,7). Elle devrait marcher mais non ?! :?

essaie de remplacer :

Code:

---

1 2

a*(i%26)

---

par

Code:

---

1 2

(a*i)%26

---

au passage, il y a mieux pour calculer l'inverse.. pour 26, a la limite, tu peux meme stocker outes les valeurs dans un tableau en les precalculant..

Youpii !!! :D

Ca marche !! Un gros merci pour le coup de pouce :) Je n'aurai jamais trouvé, on trouve peu d'informations sur l'inverse modulaire avec Google, même sur le forum, on n'en parle pratiquement pas.

Encore merci et bonnes fêtes à vous :)

pour info : l'inverse d'un nombre se trouve en utilisant des calculs de PGCD successifs : on appelle cela l'algorithme d'euclide etendu. si a et 25 sont premier entre eux, on trouve u et v tels que :

Code:

---

1 2	a*u+25*v=1

---

(identité de Bezout)
et donc, a*u=1-25*v==1 modulo 25, donc u est l'inverse de a.