algorithm - RSA 分解，c^d % n 的解释

Question

在我的 RSA 中，我使用以下代码计算 c^d % m。 但是，我不确定这个包含双 mod 操作的版本如何在后台运行。

function [f] = rsa ( m, d, c )    
f = 1;
for index = 1:d
        f = f *  mod(c , m );
        f = mod( f, m);
end

还有另一种方法使用指数 d 的二进制展开，其中指数由 2^n 的和表示，这是我所知道的。

有人能帮帮我吗？谢谢。

Answer 1

如果您暂时忽略 mod 函数调用，循环的每次迭代只会将 f(从 1 开始)乘以 c。

因此，在d次迭代后，f将等于

1*c*c*...*c = c^d

然后您可以在最后应用模数运算来计算“c^d%m”。

但是，这样做很可能会溢出，因此代码改为在每次迭代期间计算模数以防止溢出。

总而言之，这段代码只是对“c^d%m”进行暴力计算。这种方法在实践中会太慢，因为 d 在 RSA 中往往是一个非常大的数字。