RSA計算c^d模

Question

在RSA加密算法中，當c和d是大數時，如何計算c^d mod n？

Answer 1

GMP是C/C++軟件庫，這是否對你：mpz_powm，mpz_powm_ui的文件中。使用的方法（在很大程度上）在the wikipedia page中進行了解釋，您可以嘗試閱讀GMP的源代碼，如果您覺得這樣做...

Answer 2

「powMod」操作可以分解爲更小的步驟。

例如5^3 % 6等於((5 * 5) % 6) * 5 % 6而5^4 % 6等於(((5 * 5) % 6) * 5 % 6) * 5 % 6)。正如你所看到的，你可以在指數的子結果中應用模運算來始終使用較小的數值，因此即使在c和d爲高值時也可以更容易計算c^d % n。

欲瞭解更多信息： http://en.wikipedia.org/wiki/Modular_exponentiation

Answer 3

簡單的答案是：使用實現算法的語言和/關於「大整數」，幷包含適合模冪運算的功能。在Java中，這意味着使用java.lang.BigInteger，特別是方法modPow()。由於底層計算機不能真正處理「整數」，但是其中的有限仿真（例如「32位整數」，除了超過32位的高位被丟棄以外，其行爲與整數相似），所以必須應用這種「大整數」實現一些特定的算法，在Handbook of Applied Cryptography（第14章）中有詳細描述。