Grandes exponentes en Ruby?

Question

Estoy haciendo algunos ejercicios Diffie Hellmann relacionados con la Universidad e intenté usar ruby ​​para ello. Lamentablemente, rubí no parece ser capaz de hacer frente a grandes exponentes:

advertencia: en un ** B, B puede ser demasiado grande
NaN
[...]

¿Hay algún camino a su alrededor? (por ejemplo, una clase de matemática especial o algo por el estilo)

p.s. aquí está el código en cuestión:

generator = 7789 
prime = 1017473 
alice_secret = 415492 
bob_secret = 725193 

puts from_alice_to_bob = (generator**alice_secret) % prime 
puts from_bob_to_alice = (generator**bob_secret) % prime 

puts bobs_key_calculation = (from_alice_to_bob**bob_secret) % prime 
puts alices_key_calculation = (from_bob_to_alice**alice_secret) % prime 

Answer 1

Que tiene que hacer lo que se llama, modular exponentiation.

Answer 2

No sé ruby, pero incluso una biblioteca matemática amigable con bignum va a tener dificultades para evaluar esa expresión de la manera ingenua (7789 a la potencia 415492 tiene aproximadamente 1,6 millones de dígitos).

La manera de trabajar a^b mod p sin volar es hacer la mod p ing en cada exponenciación - yo supongo que la lengua no está funcionando esto por sí solo y por lo tanto debe ser ayudado.

Answer 3

Hay una buena forma de calcular un^n mod n sin obtener estos enormes números.

Usted va a caminar a través de la exponenciación usted mismo, tomando el módulo en cada etapa. Hay un truco en el que puedes dividirlo en una serie de poderes de dos.

Aquí hay un enlace con un ejemplo de usarlo para hacer RSA, de un curso que tomé hace un tiempo: En concreto, en la segunda página, se puede ver un ejemplo: http://www.math.uwaterloo.ca/~cd2rober/Math135/RSAExample.pdf

Más explicación con un poco de la muestra pseudocódigo de la wikipedia: http://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method

Answer 4

He hecho algunos intentos por mi cuenta. La exponenciación por cuadratura funciona bien hasta el momento, pero el mismo problema con bigNum. tal cosa como recursiva

def exponentiation(base, exp, y = 1) 
    if(exp == 0) 
     return y 
    end 
    case exp%2 
     when 0 then 
      exp = exp/2 
      base = (base*base)%@@mod 
      exponentiation(base, exp, y) 
     when 1 then 
      y = (base*y)%@@mod 
      exp = exp - 1 
      exponentiation(base, exp, y) 
    end 
end 

embargo

, sería, como me estoy dando cuenta, una idea terrible que depender de la clase privilegiada de ruby ​​como algo sustancial. Ruby usa el tamiz de Eratosthenes para su generador principal, pero lo que es peor, usa la división de prueba para gcd y tal ...

oh, y @@ mod era una variable de clase, así que si planeas usar esto por ti mismo , es posible que desee agregarlo como un param o algo así. he conseguido que funcione con bastante rapidez para

pone a.exponentiation (100000000000000, 1222555345678)

números en ese rango.

(usando @@ mod = 80233)

Answer 5

bien, tiene el método de cuadratura a trabajar para

a = Mod.new(80233788) 
puts a.exponentiation(298989898980988987789898789098767978698745859720452521, 12225553456987474747474744778) 

de salida: 59357797

creo que debería ser suficiente para cualquier problema que pueda tener en su curso Crypto

Answer 6

Si puede usar los enlaces OpenSSL entonces puede hacer una exponenciación modular rápida en Ruby

puts some_large_int.to_bn.mod_exp(exp,mod) 

Answer 7

Si realmente desea ir a la exponenciación modular GRANDE, aquí hay una implementación de la página wiki.

#base expantion number to selected base 
def baseExpantion(number, base) 
    q = number 
    k = "" 
    while q > 0 do 
    a = q % base 
    q = q/base 
    k = a.to_s() + k 
    end 
    return k 
end 

#iterative for modular exponentiation 
def modular(n, b, m) 
    x = 1 
    power = baseExpantion(b, 2) #base two 
    i = power.size - 1 
    if power.split("")[i] == "1" 
     x = x * n 
     x = x % m 
    end 
    while i > 0 do 
     n *= n 
     n = n % m 
     if power.split("")[i-1] == "1" 
     x *= n 
     x = x % m 
     end 
     i -= 1 
    end 
    return x 
end 

resultados, cuando probaron con Wolfram Alpha

Answer 8

está inspirado en la right-to-left binary method ejemplo en la Wikipedia:

def powmod(base, exponent, modulus) 
    return modulus==1 ? 0 : begin 
    result = 1 
    base = base % modulus 
    while exponent > 0 
     result = result*base%modulus if exponent%2 == 1 
     exponent = exponent >> 1 
     base = base*base%modulus 
    end 
    result 
    end 
end 

No