Exponentiation modulaire

[invite13a949b5]

Bonjour, sur Wikipédia, on peut lire :


Une seconde méthode pour calculer l'exponentiation modulaire requiert plus d'opérations que la première méthode. En raison de l'exigence moindre de mémoire requise, les opérations prennent pourtant moins de temps que précédemment. Il en résulte que cet algorithme peut se montrer plus rapide :

* soit par de moindres échanges entre cache (antémémoire) et mémoire
* soit par une moindre utilisation du swapping dans le cas de mémoire virtuelle


Cet algorithme utilise le fait que, pour deux entiers donnés a et b, les premières relations impliquent la suivante :

//Ca veut dire quoi cela? que b' est égale à la valeur de b modulo m ?

L'algorithme suivant :

1. Fixer c = 1, e' = 0.
2. Augmenter e' par 1.
3. Fixer c
4. Si e' < e, aller à l'étape 2. Sinon, c contient la solution correcte de

Notez qu'à chaque passage de l'étape 3, l'équation cdevient vraie. Lorsque l'étape 3 a été exécutée e fois, alors, c contient la réponse qui était cherchée.

Reprenons l'exemple b = 4, e = 13, et m = 497. L'algorithme passe par l'étape 3 treize fois :

* e' = 1. c = (1 × 4) (497) = 4 (497) = 4.
* e' = 2. c = (4 × 4) (497) = 16 (497) = 16.
* e' = 3. c = (16 × 4) (497) = 64 (497) = 64.
* e' = 4. c = (64 × 4) (497) = 256 (497) = 256.
* e' = 5. c = (256 × 4) (497) = 1024 (497) = 30.
* e' = 6. c = (30 × 4) (497) = 120 (497) = 120.
* e' = 7. c = (120 × 4) (497) = 480 (497) = 480.
* e' = 8. c = (480 × 4) (497) = 1920 (497) = 429.
* e' = 9. c = (429 × 4) (497) = 1716 (497) = 225.
* e' = 10. c = (225 × 4) (497) = 900 (497) = 403.
* e' = 11. c = (403 × 4) (497) = 1612 (497) = 121.
* e' = 12. c = (121 × 4) (497) = 484 (497) = 484.
* e' = 13. c = (484 × 4) (497) = 1936 (497) = 445.

La réponse finale pour c est par conséquent 445, comme dans la première méthode.
Je comprends pas trop pq cette algorithme marche, enfin pq on peu faire comme ca la décomposition .
Si quelqu'un peut m'expliquer un peut mieux se serait cool.
Merci d'avance.
-----

[invite13a949b5]

Pas d'idées?

[invite35452583]

//Ca veut dire quoi cela? que b' est égale à la valeur de b modulo m ?

Oui cela veut dire que si a et a' sont égaux modulo m ainsi que b et b' alors a.b et a'b' sont égaux modulo m.
En effet, on a'=a+km b'=b+hm d'où a'b'=(a+km)(b+hm)=ab+ahm+bkm+k hm²=ab+(ah+bk+khm)m.

Donc, dans l'algorithme on a à l'étape 5 c^e'=c⁵=1024 qui est égal à 30 modulo 497.
On a alors c⁶=c⁵⁺¹=c⁵.c, la valeur modulo m de c⁵.c peut se calculer en remplaçant c⁵=1024 par 30. On a donc valeur de c⁶ modulo m est égal à la valeur modulo m de 30.4=120.
On remplace ainsi dès que le résultat intermédiaire est plus grand que m (ex: 1024) par une autre valeur modulo m plus petite (ex:30).
Ceci permet de calculer la valeur modulo m pour des puissances très grandes sans stocker un nombre astronomique.

[invite13a949b5]

humm j'ai un peu du mal mais si je comprends +- :
On prend le reste de chaque modulo .
Exemple 10^3 mod 5 , on va faire :

10^3 mod 5 = (10*10*10) mod 5 =

10^1 mod 5 = R1
10*R1 mod 5 = R2
10*R2 mod 5 = resultat

exact?

[A voir en vidéo sur Futura]

[invite35452583]

humm j'ai un peu du mal mais si je comprends +- :
On prend le reste de chaque modulo .
Exemple 10^3 mod 5 , on va faire :

10^3 mod 5 = (10*10*10) mod 5 =

10^1 mod 5 = R1
10*R1 mod 5 = R2
10*R2 mod 5 = resultat

exact?

L'exemple est mal choisi car 10ⁿ=0 modulo 5 pour tout n>0 donc pas besoin d'algorithme mais oui, c'est ça l'idée.

[invite13a949b5]

Oui je sais lol merci de l'aide sinon