查找模平方

Question

我目前正在寫，需要計算的程序：

（X^2）mod y操作

這兩個數字都是整數。兩者都可以是大數字，儘管它們從未超過10^9。

這仍然足以滿足x平方的整數。速度對於此代碼至關重要，因此漸進式乘法不可用。

謝謝。

Answer 1

您可以從this post

這需要一個基準應該是一個比較簡單的例子。 4^23 = 2^46。現在，由於2^5 =32≡1（mod31），

2^46 =（2^5）9×2 = 32^9×2≡1×2≡2（mod31）

Answer 2

的解決方案非常簡單。我用龍，而不是整數，它的工作原理。