我将一些基数 b 提高到 p 次幂,然后对其取模 m。
我们假设 b=55170 或 55172,m=3043839241(这恰好是 55171 的平方)。Linux 计算器 bc
给出以下结果(我们需要这个来进行控制):
echo "p=5606;b=55171;m=b*b;((b-1)^p)%m;((b+1)^p)%m" | bc
2734550616
309288627
现在计算55170^5606会得到一个相当大的数字,但由于我需要执行模操作,所以我认为可以规避使用BigInt,原因是:
(a*b) % c == ((a%c) * (b%c))%c i.e.
(9*7) % 5 == ((9%5) * (7%5))%5 =>
63 % 5 == (4 * 2) %5 =>
3 == 8 % 5
...并且a^d = a^(b+c) = a^b * a^c,因此我可以将b+c除以2,得到偶数或奇数的结果d/2和d-(d/2),因此对于8^5,我可以计算8^2 * 8^3。
因此我的(有缺陷的)方法总是在运行时截断除数,看起来像这样:
def powMod (b: Long, pot: Int, mod: Long) : Long = {
if (pot == 1) b % mod else {
val pot2 = pot/2
val pm1 = powMod (b, pot2, mod)
val pm2 = powMod (b, pot-pot2, mod)
(pm1 * pm2) % mod
}
}
并且输入一些值,
powMod (55170, 5606, 3043839241L)
res2: Long = 1885539617
powMod (55172, 5606, 3043839241L)
res4: Long = 309288627
我们可以看到,第二个结果与上面的完全相同,但第一个结果看起来有些不同。我正在做很多这样的计算,只要它们在Int范围内,它们似乎是准确的,但我看不到任何错误。使用BigInt也可以,但速度太慢了:
def calc2 (n: Int, pri: Long) = {
val p: BigInt = pri
val p3 = p * p
val p1 = (p-1).pow (n) % (p3)
val p2 = (p+1).pow (n) % (p3)
print ("p1: " + p1 + " p2: " + p2)
}
calc2 (5606, 55171)
p1: 2734550616 p2: 309288627
与bc相同的结果。有人能看出powMod中的错误吗?
pm1
时使用pot
而不是pot2
是一个打字错误?否则会导致堆栈溢出。 - Daniel C. Sobral