0

下周我将接受测试，我正在运行一些带有素数的基本示例。书中的例子似乎没有遇到这个问题

第一步 - 选择两个素数（我选择 p=3，q=7）

第二步 - 计算 n=pq = 21

第三步 - 计算 totient(n) = tot(p)*tot(q) = 2*6 = 12

第四步——选择 e 使得 1 < e < tot(n) 使得 gcd(e,tot(n))=1 （互质）。我选择了 e=5。

第五步 - 选择 d 使得 d*e % tot(n) = 1。

据我了解， d 必须是整数。这是错误的结论吗？或者 5 在这种情况下不是有效的 e ？

4

2 回答 2

1

是的，它必须是整数。第五步正在寻找的是模乘逆。基本上，d是一个整数，d*e = m*tot(n) + 1对于某个整数m，或者换一种说法，d*e是一个多于 的倍数tot(n)。只要e和tot(n)互质，e就会有一个逆 - 在你的例子中，d恰好是 5: d*e = 5*5 = 25 = 2*tot(n) + 1。

于 2013-10-18T16:45:39.567 回答
1

是的，d是一个整数，计算为e的模逆。这是一个计算数字x关于模数m的倒数的函数：

function inverse(x, m)
    a, b, u := 0, m, 1
    while x > 0
        q := b // m
        x, a, b, u := b % x, u, x, a - q * u
    if b == 1 return a % m
    error "must be coprime"

如果您想了解更多信息，我的博客上有一个 RSA 计算示例。

于 2013-10-18T17:00:31.640 回答