java - モジュラスによる大きなべき乗の計算

Question

私は現在、次のような値を計算する必要がある何かに取り組んでいます

(65^17) mod 3233 = *

上記の問題の答えは 2790 ですが、65 ^ 17 は Math.pow によって返される値よりも大きいため、常に間違った答えになります。

BigIntegers (および組み込みの modPow) を使用して実装を作成しましたが、可能であればそれらを避けたいと考えています。

BigIntegers の使用を回避する別の方法はありますか?

Answer 1

if x = y (mod n) and u = v (mod n) then x.u = y.v (mod n)(「.」は乗算を表します)

これを繰り返し適用すると、65^17 mod 3233 が減少します。

例えば

65 * 65 (mod 3233) = 992

65 * 992 (mod 3233) = 3053

3053 * 65 (mod 3233) = 1232
.
.
.

実際、計算したのでこれを短縮できます65^4 (mod 3233) = 1232

そう、

65^8 (mod 3233) = 1232 * 1232 (mod 3233) = 1547

65^16 (mod 3233) = 1547 * 1547 = 789

そして最後に、

65^17 = 789 * 65 (mod 3233) =  2790

Answer 2

Mitch Wheat の驚くほど簡潔だがやや不可解な¹の回答が意味することは、これが機能するはずであるということです (疑似コード):

   res = 1
   for i in 1 to 17:
       res = (res * 65) mod 3233

モジュラス演算の数学的特性のため、これには BigInteger を使用する必要はまったくありません。

FWIW、 usingMath.pow()が機能しない理由は、浮動小数点演算を使用して65 ^{17を計算するためです。}の結果はpowとして正確に表すには大きすぎるdoubleため、最下位桁の一部が失われます。つまり、数字の「右端」にあるものです。残念ながら、これらの数字はモジュラスを取るときに重要です。

---

^{1 - ... 数学が得意なスキルの 1 つでない場合 ....}