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

Есть хороший способ вычислить 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

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

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

Хорошо, метод возведения в квадрат работает для вывода

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

: 59357797

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

Я предпринял несколько собственных попыток. Возведение в степень возведением в квадрат пока работает хорошо, но та же проблема с 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 был переменной класса, поэтому, если вы планируете использовать это сами, вы можете добавить его как параметр или что-то в этом роде. Я заставил его работать довольно быстро, потому что

помещает числа экспоненцирования (100000000000000, 1222555345678)

в этот диапазон.

(используя @@ mod = 80233)