大数字的动力和模数

Question

我向幂p提出了一些基础b并取其模数.

假设b = 55170或55172且m = 3043839241(恰好是55171的平方).linux-calculator 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,这得到偶数或奇数ds 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吗？

Answer 1

我想答案就在这里：

scala> math.sqrt(Long.MaxValue).toLong < 3043839241L
res9: Boolean = true

这意味着即使对于小于该特定模块值的数字，也可能会出现长时间溢出。让我们尝试抓住它：

scala> 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)
     |           val partial = ((pm1 % mod) * (pm2 % mod)).ensuring(res =>
     |             res > pm1 % mod && res > pm2 % mod, "Long overflow multiplying "+pm1+" by "+pm2)
     |           partial % mod
     |       }
     | }
powMod: (b: Long,pot: Int,mod: Long)Long

scala> powMod (55170, 5606, 3043839241L)
java.lang.AssertionError: assertion failed: Long overflow multiplying 3042625480 by 3042625480

你有它。