Potencia de módulo de números grandes

Estoy tratando de implementar el algoritmo SAFER +. El algoritmo requiere encontrar el módulo de una función de potencia como sigue:Potencia de módulo de números grandes

pow(45, x) mod 257

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

¿Cómo puedo realizar este cálculo?

Fuente

2011-11-27 Eng. Aws

¿Qué lenguaje de programación? – esskar

@esskar: Si no estoy completamente equivocado y recuerdo correctamente que hay fórmulas especiales para calcular las potencias en los espacios del módulo, el cálculo del módulo es la parte importante de la pregunta, por lo que la pregunta es independiente del idioma. – thiton

Lectura introductoria: [El grupo multiplicativo de enteros] (http://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n#Powers_of_odd_primes). Esto fue hace mucho tiempo para que yo respondiera, pero tal vez alguien lo recuerde. – thiton

algunos 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 llaman

powermod(45, x, 257)

Fuente

2011-11-27 16:56:40 esskar

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 llama (binary) modular exponentiation.

Fuente

2011-11-27 16:56:33

Realizar la exponenciación binaria repetido, reduciendo por el módulo después de cada operación. Esta es una técnica muy estándar. 45^13 mod 257::

Primera compute 45^2, 45^4, 45^8 mod 257:

45^2 mod 257 = 2.025 mod 257 = 226

un ejemplo práctico
45^4 mod 257 = 226^2 mod 257 = 51 076 mod 257 = 190

45^8 mod 257 = 190^2 mod 257 = 36 100 mod 257 = 120
continuación, utilizar la expansión binaria de 13 para combinar estos para 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 = 8.550 * 120 mod 257

45^13 mod 257 = 69 * 120 mod 257

45^13 mod 257 = 8.280 mod 257

45^13 mod 257 = 56

Tenga en cuenta que los resultados intermedios de la computación nunca son más grandes que 257 * 257, por lo que este se puede realizar fácilmente en un tipo entero de 32 bits.

Fuente

2011-11-27 17:00:20

respuesta más hermosa. – Kokizzu

Considérese la identidad simple:

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

También tenga en cuenta que

A^4 = (A^2)^2

Otras potencias se calculan trivialmente si conoce la representación binaria del exponente final que se quiera calcular.

Fuente

2011-11-27 17:14:48

Potencia de módulo de números grandes

Respuesta

Cuestiones relacionadas