Криптология программы Fea

Question

Мне просто интересно, может ли кто-нибудь дать мне руку с кодом для простой программы. Я написал программу, но, похоже, я пытаюсь вычислить значения с большими значениями e и n.

Но теперь, когда я пытаюсь вычислить следующий fea(2, 968365546456, 132132156132132) он приходит с ошибкой, говоря:

Ошибка, (в FEA) числовом исключение: Переполнение

Может кто-нибудь помочь мне с код, чтобы я мог исправить ошибку? Я предполагаю, что это потребует утверждения if if?

Мой код до сих пор:

fea := proc (x, e, n) 
    (x^e) mod n; 
end proc; 

The procedure

Answer 1

помощь страницу для темы mod состояния это:

"To compute `mod`(i^n,m) where i is an integer, it is undesirable 
to use this "obvious" syntax because the powering will be 
performed first over the integers (possibly resulting in a very 
large integer) before reduction modulo m. Rather, the inert 
operator &^ should be used: i &^ n mod m. In the latter form, 
the powering will be performed intelligently by the mod operation." 

Итак, давайте посмотрим:

restart; 

12367^ 13 mod 87; # for basic test 

          67 

fea := proc (x, e, n) 
    (x &^ e) mod n; 
end proc: 

fea(12367, 13, 87); 

          67 

# The following returns very quickly. 

fea(2, 968365546456, 132132156132132); 

       131464616935876 

Вашего оригинал пытается вычислить промежуточный результат:

restart; 

2^968365546456; 
Error, numeric exception: overflow 

Answer 2

Один из лучшего метода для расчета мощности является Square and Multiply Algorithm for Modular Exponentiation.

Этот алгоритм в виде

Например

кленовый прок этого алгоритма следующим образом

предположим, что мы хотим для вычисления a^b mod n. Эта линия

для г от 0 до б, а 2^я < = Ь сделать C: = C + 1 конец делают

вычислить длину двоичного числа Ь. Эта строка

для i от 0 до c-1, если iirem (m, 2, 'q') = 1, тогда B [1, c-i]: = 1 end if; m: = q end do

получить двоичную форму числа b и поместить в матрицу. Эта строка

для i до c do m: = irem (m^2, n); если B [1, i] = 1, то m: = irem (m * a, n) end if end do

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

Если вы хотите получить (a^b mod n), вы должны сначала запустить код proce и после этого написать Pow (a, b, n) и ввести ключ.Например, для ваших чисел, после запуска проц вы должны написать

Pow (2, 968365546456, 132132156132132)

и после ввода ключей вы увидите следующее сообщение

2^(968365546456) мод (132132156132132) = (131464616935876)

См. source code. Лучшая книга в этом поле - Introduction to Cryptography with Maple.