Potencia de módulo de grandes números

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?

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) 

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.

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) .

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.