Большие экспоненты в рубине?

Question

Я просто делаю некоторые связанные с университетом упражнения Диффи-Хеллмана и пытался использовать для этого рубин К сожалению, рубин, похоже, не в состоянии справиться с большими показателями:

предупреждение: в a ** b, b может быть слишком большим
NaN
[...]

Есть ли способ обойти это? (например, специальный математический класс или что-то в этом роде?)

p.s. вот код, о котором идет речь:

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

Вам нужно сделать то, что называется, модульное возведение в степень .

Answer 2

Если вы можете использовать привязки OpenSSL, вы можете выполнить быстрое модульное возведение в степень в Ruby

puts some_large_int.to_bn.mod_exp(exp,mod)

Answer 3

Есть хороший способ вычислить a ^ b mod n без получения этих огромных чисел.

Вы сами пройдете через возведение в степень, беря модуль на каждой стадии. Есть трюк, в котором вы можете разбить его на серию из двух сил.

Вот ссылка с примером использования RSA для курса, который я недавно изучал: В частности, на второй странице вы можете увидеть пример: http://www.math.uwaterloo.ca/~cd2rober/Math135/RSAExample.pdf

Более подробное объяснение с некоторыми примерами псевдокода из Википедии: http://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method

Answer 4

ОК, метод квадратов работает на

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

выход: 59357797

Я думаю, этого должно быть достаточно для любой проблемы, которая может возникнуть у вас на курсе Crypto

Answer 5

Я сделал несколько собственных попыток. Пока возведение в квадрат по квадрату работает хорошо, но та же проблема с bigNum. такая рекурсивная вещь как

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

однако, как я понимаю, было бы ужасной идеей полагаться на первоклассный класс ruby ​​в отношении чего-либо существенного. Руби использует Сито Эратосфена для своего основного генератора, но, что еще хуже, он использует пробное деление для gcd и тому подобного ...

о, и @@ mod была переменной класса, поэтому, если вы планируете использовать это сами, вы можете добавить ее в качестве параметра или чего-то еще. Я заставил его работать довольно быстро за

ставит aexponentiation (100000000000000, 1222555345678)

чисел в этом диапазоне.

(с использованием @@ mod = 80233)

Answer 6

Я не знаю ruby, но даже математическая библиотека, дружественная к bignum, будет изо всех сил пытаться оценить такое выражение наивным способом (7789 к власти 415492 имеет приблизительно 1,6 миллиона цифр).

Способ отработать a^b mod p без взрыва - это делать mod p ing при каждом возведении в степень - я бы предположил, что язык не работает сам по себе и поэтому должен помочь.

Answer 7

Это вдохновлено двоичным методом справа налево пример в Википедии:

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

Answer 8

Если вы действительно хотите перейти к БОЛЬШОМУ модульному возведению в степень, вот реализация со страницы вики.

#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

Результаты, где тестировались с вольфрам альфа