Algorithme d'Euclide etendu

Version imprimable

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:

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:

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!

Salut

tu as juste oublié qq affaires

Code:

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
43
44
45
46
47
48
49
50
51
 
void euclide(int w,int m);
 
void main(void)
{
     int i,j;
     printf("\n\nEntrer W : ");
     scanf("%d",&i);
     printf("\nEntrer M (tous les calculs sont faits MOD M) : ");
     scanf("%d",&j);
     euclide(i,j);
}
 
void euclide(int w,int m)
{
     int ww = w;
     int mm = m;
     int t0 = 0;
     int t = 1;
     int q = (int) mm/ww;
     int r = mm - q * ww;
     int tmp = 0;
 
   while(r > 0)
   {
        tmp = t0 - q * t;
 
        if (tmp >= 0)
	 {
              tmp = tmp % m;
         }
         else
         {
             tmp = m - ((-tmp) % m);
         }
 
	 t0 = t;
	 t = tmp;
	 mm = ww;
	 ww = r;
	 q = (int) mm/ww;
	 r = mm - q * ww;
    }
 
    if (ww!=1)
    {
	printf("%d   n'a pas d'inverse modulo   %d\n\n",w,m);
    }
    else 
       printf ("L'inverse de %d  MOD  %d  =  %d\n ",w,m,t);
}

désolé j'ai foutu de la merde dans ton code

Bonne chance :)

09/04/2008, 03h24
YASIR

Comment ca tu as foutu la merde ?
Tu ne sais pas ce que tu as fait ?

de toute facon j'ai trouvé

fallait changer une portion de code et remplacer par cela
Code:

1 2 3 4 5 6 int d=m,i=1,res; while((d+1)%n!=0){ i++; d=m*i; res=(d+1)/n;

09/04/2008, 03h53
bobmidou

je rigole

au lieu de w et m j ai mis ww mm :)
09/04/2008, 19h15
YASIR

Ce n'est pas grave lol j'ai fini par trouver une autre solution:)