Module de puissance des grands nombres

Je suis en train de mettre en œuvre l'algorithme SAFER+. L'algorithme nécessite de trouver le module d'une fonction de puissance comme suit:

pow(45, x) mod 257

La variable x est un octet, et peut donc aller de 0 à 255. En conséquence, le résultat de la fonction de puissance peut être TRÈS grande, résultant en des valeurs incorrectes si mis en œuvre à l'aide de la version 32 ou 64 bits entiers.

Comment puis-je effectuer ce calcul?

quel langage de programmation?
Si je ne suis pas totalement dans l'erreur et n'oubliez pas correctement qu'il existe des formules spéciales pour les puissances de calcul du module d'espaces, le module de calcul est la partie importante de la question, la question est donc indépendant de la langue.
Introduction à la lecture: Le groupe multiplicatif des entiers. C'est trop il y a longtemps pour moi de répondre, mais peut-être que quelqu'un se souvient.
Il y a une SAFER+ mise en œuvre écrite en C, vous pouvez étudier ici: schneier.com/book-applied-source.html

OriginalL'auteur Eng. Aws | 2011-11-27

  1. 20

    de pseudo-code

    function powermod(base, exponent, modulus) {
    if (base < 1 || exponent < 0 || modulus < 1)
        return -1

    result = 1;
    while (exponent > 0) {
       if ((exponent % 2) == 1) {
           result = (result * base) % modulus;
       }
       base = (base * base) % modulus;
       exponent = floor(exponent /2);
    }
    return result;
}

    et appel

    powermod(45, x, 257)

    OriginalL'auteur esskar

  2. 13

    Effectuer l'exponentiation par la répétition de la quadrature, réduisant par le module après chaque opération. C'est très technique standard.

    Un exemple: 45^13 mod 257:

    1. Calculez d'abord 45^2, 45^4, 45^8 mod 257:

      45^2 mod 257 = 2025 mod 257 = 226

      45^4 mod 257 = 226^2 mod 257 = 51076 mod 257 = 190

      45^8 mod 257 = 190^2 mod 257 = 36100 mod 257 = 120

    2. Puis utiliser le binaire de l'expansion de 13 à les combiner pour obtenir le résultat:

      45^13 mod 257 = 45^1 * 45^4 * 45^8 mod 257

      45^13 mod 257 = 45 * 190 * 120 mod 257

      45^13 mod 257 = 8550 * 120 mod 257

      45^13 mod 257 = 69 * 120 mod 257

      45^13 mod 257 = 8280 mod 257

      45^13 mod 257 = 56

    Noter que les résultats intermédiaires du calcul ne sont jamais plus grand que 257*257, donc cela peut facilement être réalisé en un entier de 32 bits de type.

    très belle réponse..

    OriginalL'auteur Stephen Canon

  3. 5

    L'approche de base est de carré ou d'-multiplier en fonction de l'exposant peu, et d'effectuer la réduction modulaire à chaque étape. L'algorithme est appelé (binaire) exponentiation modulaire.

    OriginalL'auteur Brett Hale

  4. 3

    Envisager la simple identité:

    mod(A^2,p) = mod(A,p)*mod(A,p)

    Également noter que

    A^4 = (A^2)^2

    Les autres pouvoirs sont trivialement calculée si vous connaissez la représentation binaire de la finale de l'exposant vous souhaitez calculer.

    OriginalL'auteur