algorithm - the - potenciacion algoritmo

Potencia de módulo de grandes números

Question

Estoy tratando de implementar el algoritmo SAFER +. El algoritmo requiere encontrar el módulo de una función de potencia de la siguiente manera:

pow(45, x) mod 257

La variable x es un byte y, por lo tanto, puede ir de 0 a 255. Por consiguiente, el resultado de la función de potencia puede ser MUY grande, lo que da como resultado valores incorrectos si se implementa con enteros de 32 o 64 bits.

¿Cómo puedo realizar este cálculo?

Answer 1

Considera la identidad simple:

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

También tenga en cuenta que

A^4 = (A^2)^2

Se calculan trivialmente otros poderes si conoce la representación binaria del exponente final que desea calcular.

Answer 2

El enfoque básico es cuadrar o multiplicar según el bit de exponente y realizar la reducción modular en cada paso. El algoritmo se denomina exponenciación modular (binaria) .

Answer 3

Realice la exponenciación mediante cuadratura repetida, reduciendo por el módulo después de cada operación. Esta es una técnica muy estándar.

Un ejemplo trabajado: 45^13 mod 257 :

1. Primero calcule 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. Luego use la expansión binaria de 13 para combinarlos y obtener el resultado:

   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

Tenga en cuenta que los resultados intermedios del cálculo nunca son mayores que 257 * 257, por lo que esto puede realizarse fácilmente en un tipo entero de 32 bits.

Answer 4

algún pseudo código

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;
}

y llama

powermod(45, x, 257)