我是一名高中生,正在写一篇关于RSA的论文,我正在用一些非常小的素数做一个例子。我知道系统是如何工作的,但我终生不能使用扩展的欧几里德算法来计算私钥。
以下是我到目前为止所做的工作:
我选择了质数p=37和q=89,我计算了N=3293,,
现在我只需要计算私钥d,它应该满足ed=1 (Mod3168)
使用扩展的欧几里德算法找到d,这样我就得到了-887·25+7·3168=1,我去掉了7,得到d=-887。然而,试图解密一条消息,这是不起作用的。
我从我的书中知道d应该是2281,它是有效的,但我不知道他们是如何得出这个数字的。
有人能帮上忙吗?在过去的4个小时里,我一直在试着解决这个问题,并且到处寻找答案。我手工做了扩展的欧几里德算法,但由于结果是有效的,我的计算应该是正确的。
提前谢谢你,
Mads
发布于 2010-12-13 00:33:12
你太接近了,你会踢到自己的。
具体地说,如果你有mod x,那么A必须满足0<=a<x
。如果不是,则根据需要多次添加或减去x,直到您在此范围内。这就是所谓的模运算。
你可能想要阅读线性同余和数论。在英国,这些主题是学位级别的数学(我猜你会称之为大学),所以如果看起来有点奇怪,不要担心。线性同余简单地说,-887 mod 3168
和2281 mod 3168
实际上是同一件事,因为它们是同一个类的一部分,这个类在所需的范围内被证明为2281 mod 3168
。2281+3168 mod 3168
也会在那个班级里。
玩得开心!
P.S. PARI/GP是理论家用于计算的效用数。
https://stackoverflow.com/questions/4422633
复制相似问题