Bonsoir

je cherche à coder une petite fonction qui grâce à l'algorithme d'euclide etendu, me donne l'inverse modulo M d'un entier...

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
/**********************************************************/
/**********************euclide etendu**********************/
/*********************************************************/
 
 
int euclide(int w,int m){
 
 
    int t0=0,t=1;
    int q;
    int r=w-q*m;
    int tmp;
 
 
        printf("\n\nEntrer W : ");
        scanf("%d",&w);
        printf("\nEntrer M (tous les calculs sont faits MOD M) : ");
        scanf("%d",&m);
 
    do{
        tmp=t0-q*t;
        if (tmp>=0) {
                    tmp=tmp % w;
                    }
		else {
             tmp = w-(-tmp % w);
             }
		t0=t;
		t=tmp;
		w=m;
		m=r;
		r=w-q*m;
    }
    while(r>0);
 
    if (m!=1) {
               printf("%d n'a pas d'inverse modulo %d\n\n",m,w);
               }
	else 
    printf ("%d -1 MOD %d = %d",m,w,t);
}
j'ai fait ca à partir de l'algorithme pure mais il ya une erreur au niveau du

if (m!=1) car il me donne toujours que ca n'a pas d'inverse modulo...

L'algo :

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
 
algo d'euclide etendu
 
no := n
bo := b
to := 0
t := 1
q := nombre entier immédiatement inférieur ou égal à no / bo
r := no - q • bo
Tant que r > 0 faire
   Début
      temp := to - q • t
      Si temp 0 alors temp := temp mod n, sinon temp := n - ((-temp) mod n)
      to := t
      t := temp
      no := bo
      bo := r
      q := nombre entier immédiatement inférieur ou égal à no / bo
      r := no - q • bo
   Fin
Si bo 1 alors b n'a pas d'inverse modulo n, sinon b-1 mod n = t
Voila merci beaucoup si quelqu'un peut m'aider ou ne serait-ce que me pister!