BigInteger型を必要としない、yを法とするxの乗数(y< 1000の場合)を計算するアルゴリズムはありますか?
-
22-07-2019 - |
質問
私が現在使用しているアルゴリズムは、非常に高速で非常に多くの数値に達します。アルゴリズムのステップで、 x を y に適用されたtotient関数の結果に上げます。その結果、非常に大きな数に遭遇する可能性があります。
たとえば10の53を法とする乗法の順序を計算する場合:
10^totient(53) == 10^52 == 1 * 10^52
次のアルゴリズムは、大きな数を避けるという点では少し良くなりますが、 10 ^ mOrder がデータ型の容量よりも大きい場合は失敗します:
mOrder = 1
while 10^mOrder % 53 != 1
if mOrder >= i
mOrder = 0;
break
else
mOrder = mOrder + 1
解決
モジュラー累乗法を使用すると、cよりもはるかに大きな値を取得せずに(10 ^ mOrder%53)または一般的に(a ^ b mod c)を計算できます。詳細については、 Wikipedia をご覧ください。このサンプルコードもあります:
Bignum modpow(Bignum base, Bignum exponent, Bignum modulus) {
Bignum result = 1;
while (exponent > 0) {
if ((exponent & 1) == 1) {
// multiply in this bit's contribution while using modulus to keep result small
result = (result * base) % modulus;
}
// move to the next bit of the exponent, square (and mod) the base accordingly
exponent >>= 1;
base = (base * base) % modulus;
}
return result;
}
他のヒント
なぜべき乗するのですか?ループでモジュロ n を乗算することはできませんか?
(defun multiplicative-order (a n) (if (> (gcd a n) 1) 0 (do ((order 1 (+ order 1)) (mod-exp (mod a n) (mod (* mod-exp a) n))) ((= mod-exp 1) order))))
または、ptheudo(sic)コードで:
def multiplicative_order (a, n) :
if gcd (a, n) > 1 :
return 0
else:
order = 1
mod_exp = a mod n
while mod_exp != 1 :
order += 1
mod_exp = (mod_exp * a) mod n
return order
所属していません StackOverflow