Fea程序密码学

Question

我只是想知道是否有人能帮我处理一个简单程序的代码。我已经编写了这个程序，但是我似乎在试图用e和n的大值来计算值。

但现在，当我试图计算以下fea(2, 968365546456, 132132156132132)时，会出现一个错误，即：

错误，(在fea中)数值异常:溢出

有人能帮我处理代码吗?这样我就可以修复错误了吗？我想它还需要一个if语句吗？

到目前为止我的代码是：

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

程序

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

计算功率的最佳方法之一是模幂的平方和乘算法。

此算法如下所示

​

​

例如

​

该算法的主要步骤如下：

​

​

假设我们要计算a^b mod n，这一行

对于i从0到b，而2^i <= b做c := c+1端do

计算数字b的二进制长度。

对于i从0到c-1，如果irem(m，2，'q') =1，则B1，c-i := 1结束，如果；m := q端

获得数字b的二进制形式并将其放置在矩阵中。这条线

对于i to c，m := irem(m^2，n)；如果B1，i=1，则m := irem(m*a，n)结束如果结束do

做正方形和乘法算法。请做一个例子来学习它。

如果您想获得(a^b mod n)，您应该首先运行proce代码，然后编写Pow(a，b，n)并输入键。例如，对于您的数字，运行过程之后，您应该编写

Pow(2,968365546456,132132156132132)

在输入键后，您将看到以下消息

2^(968365546456) mod (132132156132132) = (131464616935876)

请看源代码。这一领域最好的书是枫树密码学概论。