Discussion :

[v4np13]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[borisd]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Graffito]

Bonjour,

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

[v4np13]

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.

[jobherzt]

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"

[v4np13]

Je viens de tester avec le "ou", effectivement ça fonctionne mais il n'accepte plus aucune valeur à part 1 pour a. 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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ?!

[jobherzt]

essaie de remplacer :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
a*(i%26)

par

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
(a*i)%26

[jobherzt]

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..

[v4np13]

Youpii !!!

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

[jobherzt]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.