¿Grandes exponentes en Ruby?

Question

Solo estoy haciendo algunos ejercicios de Diffie Hellmann relacionados con la Universidad y traté de usar Ruby para ello.Lamentablemente, Ruby no parece ser capaz de lidiar con grandes exponentes:

advertencia:en a**b, b puede ser demasiado grande
Yaya
[...]

¿Hay alguna manera de evitarlo?(p.ej.¿una clase especial de matemáticas o algo parecido?)

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

Es necesario hacer lo que se llama, exponenciación modular .

Answer 2

Si usted puede utilizar los enlaces de OpenSSL, puede hacerlo rápida exponenciación modular en Ruby

puts some_large_int.to_bn.mod_exp(exp,mod)

Answer 3

Hay una buena manera de calcular a ^ b mod n sin conseguir estos números enormes.

Vas a caminar a través de la potenciación a sí mismo, teniendo el módulo en cada etapa. Hay un truco donde se puede descomponer en una serie de potencias 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 alguna muestra pseudocódigo de Wikipedia: http: // en. wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method

Answer 4

No sé rubí, pero incluso una biblioteca matemática bignum ambiente va a luchar para evaluar una expresión como la forma ingenua (7789 a 415.492 el poder tiene aproximadamente 1,6 millones de dígitos).

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

Answer 5

He hecho algunos intentos por mi cuenta.La exponenciación al cuadrado funciona bien hasta ahora, pero el mismo problema con bigNum.algo tan recursivo como

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

sin embargo, me estoy dando cuenta de que sería una idea terrible confiar en la clase principal de Ruby para cualquier cosa sustancial.Ruby usa el Tamiz de Eratóstenes como generador principal, pero aún peor, usa la división de prueba para mcd y demás...

Ah, y @@mod era una variable de clase, por lo que si planean usarla ustedes mismos, es posible que quieran agregarla como parámetro o algo así.He conseguido que funcione bastante rápido para

pone una exponenciación (100000000000000, 1222555345678)

números en ese rango.

(usando @@mod = 80233)

Answer 6

OK, consiguió el método de cuadratura a trabajar por

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

salida: 59357797

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

Answer 7

Si realmente quieres ir a la exponenciación modular BIG, aquí es 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, donde probado con Wolfram alfa

Answer 8

Este es inspirada por de derecha a izquierda método binario ejemplo 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