我目前使用的算法很快就会达到极高的数字。我要将 x 提高到应用于 y 的 totient 函数的结果的算法中的一个步骤。结果是您可能会遇到非常大的数字。
例如。在计算 multiplicative order 时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
最佳答案
使用模幂运算,可以计算 (10 ^ mOrder % 53) 或一般来说,任何 (a ^ b mod c) 而不会得到比 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;
}
关于algorithm - 是否有一种不需要 BigInteger 类型的算法来计算 x modulo y(对于 y < 1000)的乘法阶数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/642234/