Pregunta Grandes exponentes en ruby?


Solo estoy haciendo algunos ejercicios relacionados con la Universidad de Diffie Hellmann 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 alrededor? (por ejemplo, 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

5
2017-11-18 20:02


origen


Respuestas:


Tienes que hacer lo que se llama, exponenciación modular.


10
2017-11-18 20:09



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

puts some_large_int.to_bn.mod_exp(exp,mod)

3
2018-04-17 18:03



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

Vas a caminar a través de la exponenciación tú 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 que lo usa para hacer RSA, de un curso que tomé hace un tiempo: Específicamente, en la segunda página, puede ver un ejemplo: http://www.math.uwaterloo.ca/~cd2rober/Math135/RSAExample.pdf

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


2
2017-11-18 20:17



No conozco a Ruby, pero incluso una biblioteca matemática amigable va a tener dificultades para evaluar tal expresión de una manera ingenua (7789 al poder 415492 tiene aproximadamente 1.6 millones de dígitos).

La forma de hacer ejercicio a^b mod p sin explotar es hacer el mod pEn g en cada exponenciación - Supongo que el lenguaje no está funcionando por sí mismo y, por lo tanto, debe ser ayudado.


1
2017-11-18 20:10



He hecho algunos intentos por mi cuenta. La exponenciación por cuadratura funciona bien hasta el momento, pero el mismo problema con bigNum. una cosa tan recursiva 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, sería una idea terrible, como me doy cuenta, confiar en la clase principal de Ruby para cualquier cosa importante. Ruby usa el Tamiz de Eratóstenes para su generador principal, pero lo que es peor, usa la división de Prueba para gcd's y ...

oh, y @@ mod era una variable de clase, así que si planean usar esto, pueden agregarlo como parámetro o algo. He conseguido que funcione bastante rápido para

pone una .exposición (100000000000000, 1222555345678)

números en ese rango

(utilizando @@ mod = 80233)


1
2017-11-23 03:38



OK, tengo el método de cuadratura para trabajar

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 de Crypto


1
2017-11-23 03:55



Si realmente quieres ir a la gran exponenciación modular, 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, donde probado con wolfram alfa


0
2018-02-22 22:47



Esto está inspirado en método binario de derecha a izquierda ejemplo en 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

0
2018-03-18 21:32