问RSA:基于扩展欧几里德算法的私钥计算

EN

我是一名高中生，正在写一篇关于RSA的论文，我正在用一些非常小的素数做一个例子。我知道系统是如何工作的，但我终生不能使用扩展的欧几里德算法来计算私钥。

以下是我到目前为止所做的工作：

我选择了质数p=37和q=89，我计算了N=3293，，

• ，我选择了一个数字e，所以e和3168是相对质数。我正在用标准的欧几里德算法检查这个，它工作得很好。My e=25

现在我只需要计算私钥d，它应该满足ed=1 (Mod3168)

使用扩展的欧几里德算法找到d，这样我就得到了-887·25+7·3168=1，我去掉了7，得到d=-887。然而，试图解密一条消息，这是不起作用的。

我从我的书中知道d应该是2281，它是有效的，但我不知道他们是如何得出这个数字的。

有人能帮上忙吗？在过去的4个小时里，我一直在试着解决这个问题，并且到处寻找答案。我手工做了扩展的欧几里德算法，但由于结果是有效的，我的计算应该是正确的。

提前谢谢你，

Mads