我是一名高中生，正在写一篇关于 RSA 的论文，我正在用一些非常小的素数做一个例子。我了解系统的工作原理，但我一生都无法使用扩展欧几里得算法来计算私钥。
这是我到目前为止所做的：
- 我选择了素数 p=37
q=89 并计算出 N=3293
- 我已经计算出 (p-1)(q-1)=3168
- 我选择了一个数字 e，使得 e 和 3168 互质。我正在使用标准欧几里得算法来检查这一点，效果非常好。我的 e=25
现在我只需要计算私钥 d，它应该满足 ed=1 (mod 3168)
使用扩展欧几里得算法找到 d 使得 de+tN=1 我得到 -887•25+7•3168 =1。我把 7 扔掉，得到 d=-887。然而，尝试解密消息却行不通。
我从我的书中知道 d 应该是 2281，并且它有效，但我不知道他们是如何得出这个数字的。
有人可以帮忙吗？在过去的 4 个小时里我一直在尝试解决这个问题，并到处寻找答案。我正在手工执行扩展欧几里得算法，但由于结果有效，我的计算应该是正确的。
预先感谢，
麦兹
I'm a high school student writing a paper on RSA, and I'm doing an example with some very small prime numbers. I understand how the system works, but I can't for the life of me calculate the private key using the extended euclidean algorithm.
Here's what I have done so far:
- I have chosen the prime numbers p=37
and q=89 and calculated N=3293
- I have calculated (p-1)(q-1)=3168
- I have chosen a number e so that e and 3168 are relatively prime. I'm checking this with the standard euclidean algorithm, and that works very well. My e=25
Now I just have to calculate the private key d, which should satisfy ed=1 (mod 3168)
Using the Extended Euclidean Algorithm to find d such that de+tN=1 I get -887•25+7•3168=1. I throw the 7 away and get d=-887. Trying to decrypt a message, however, this doesn't work.
I know from my book that d should be 2281, and it works, but I can't figure out how they arrive at that number.
Can anyone help? I've tried solving this problem for the last 4 hours, and have looked for an answer everywhere. I'm doing the Extended Euclidean Algorithm by hand, but since the result works my calculations should be right.
Thanks in advance,
Mads
发布评论
评论（1）
你离得太近了，你会踢自己的。
3168-887=2281。
具体来说，如果有 mod x，则 A 必须满足
0<=a。如果不是，请根据需要多次添加或减去 x，直到达到此范围。这称为模运算。 您可能想阅读线性同余和数论。这些主题是英国的学位水平数学（我猜你称之为大学），所以不要担心它看起来有点奇怪。线性同余只是说
-887 mod 3168和2281 mod 3168实际上是同一件事，因为它们是同一类的一部分，该类结果为2281 mod 3168在所需范围内。2281+3168 mod 3168也属于该类别。玩得开心！
PS PARI/GP 是一个实用数论学家用于计算的工具。可能值得一看。
You're so close you're going to kick yourself.
3168-887=2281.
Specifically, If you have a mod x, then A must satisfy
0<=a<x. If it doesn't, add or subtract x as many times as necessary until you are in this range. This is called modular arithmetic.You might want to read up on linear congruences and number theory. These topics are degree level mathematics in the UK (what you'd call college I guess) so don't worry if it seems a bit odd. A linear congruence simply says that
-887 mod 3168and2281 mod 3168are actually the same thing because they are part of the same class, the class that turns out as2281 mod 3168in the required range.2281+3168 mod 3168would also be in that class.Have fun!
P.S. PARI/GP is a utility number theorists use for calculations. Might be worth a look.