Bonsoir
je cherche à coder une petite fonction qui grâce à l'algorithme d'euclide etendu, me donne l'inverse modulo M d'un entier...
j'ai fait ca à partir de l'algorithme pure mais il ya une erreur au niveau du
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); }
if (m!=1) car il me donne toujours que ca n'a pas d'inverse modulo...
L'algo :
Voila merci beaucoup si quelqu'un peut m'aider ou ne serait-ce que me pister!
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
Partager