Répondre à la discussion
Affichage des résultats 1 à 6 sur 6

Exponentiation modulaire



  1. #1
    aoc

    Exponentiation modulaire


    ------

    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.

    -----

  2. Publicité
  3. #2
    aoc

    Re : Exponentiation modulaire

    Pas d'idées?

  4. #3
    homotopie

    Re : Exponentiation modulaire

    Citation Envoyé par aoc Voir le message
    //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 ce'=c5=1024 qui est égal à 30 modulo 497.
    On a alors c6=c5+1=c5.c, la valeur modulo m de c5.c peut se calculer en remplaçant c5=1024 par 30. On a donc valeur de c6 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.

  5. #4
    aoc

    Re : Exponentiation modulaire

    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?

  6. #5
    homotopie

    Re : Exponentiation modulaire

    Citation Envoyé par aoc Voir le message
    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 10n=0 modulo 5 pour tout n>0 donc pas besoin d'algorithme mais oui, c'est ça l'idée.

  7. A voir en vidéo sur Futura
  8. #6
    aoc

    Re : Exponentiation modulaire

    Oui je sais lol merci de l'aide sinon

  9. Publicité

Sur le même thème :

Discussions similaires

  1. Puissance Modulaire
    Par aoc dans le forum Mathématiques du supérieur
    Réponses: 5
    Dernier message: 29/12/2007, 22h28
  2. Arithmètique Modulaire
    Par Haexyrus dans le forum Mathématiques du collège et du lycée
    Réponses: 6
    Dernier message: 27/12/2007, 21h37
  3. Groupe modulaire et volume
    Par martini_bird dans le forum Mathématiques du supérieur
    Réponses: 5
    Dernier message: 06/04/2006, 16h30
  4. Verification equation modulaire
    Par GalacticSwirl dans le forum Mathématiques du supérieur
    Réponses: 5
    Dernier message: 11/03/2006, 14h25
  5. probleme d'arithmetique modulaire
    Par planck dans le forum Mathématiques du supérieur
    Réponses: 0
    Dernier message: 09/01/2005, 10h01