大数的快速幂和取模运算

Question

大数的快速幂和取模运算

6

我将一些基数 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中的错误吗？

- user unknown

我猜在计算 pm1 时使用 pot 而不是 pot2 是一个打字错误？否则会导致堆栈溢出。 - Daniel C. Sobral

3个回答

2

虽然不熟悉Scala，但是……

def powMod (b: Long, pot: Int, mod: Long) : Long = {  
      if (pot == 1) b % mod else { 
          val pot2 = pot/2 
          val pm1 = powMod (b, pot, mod)              
          val pm2 = powMod (b, pot-pot2, mod)            
          (pm1 * pm2) % mod  
      }  
}

你是想说

你的意思是

          val pm1 = powMod (b, pot2, mod)

注意 pot2 而不是 pot。

奇怪的是，它似乎应该无限循环/溢出堆栈，但谁知道 Scala 在做什么。

- Aryabhatta

是的，你说得完全正确，我已经相应地更正了我的代码。错误是在我试图改进变量名时犯的，所以现在出现了描述的错误，否则它会无限循环，在你所写的那样导致堆栈溢出。 - user unknown

1

好的伙计们，我花了一些时间，最终打破了一个长期存在但从未被证明的假设，即如果你将两个64位正整数值（也称为Longs，在实际中只有63位）相乘，你可能会溢出并得到负值，但不会溢出以达到正（但错误的）值。

所以我尝试在我的代码中加入一个保护措施，用BigInt来计算我的值，它太大了，但是这个保护措施是不够的，因为我测试的是res < 0。res < pm1 && res < pm2也不足够。

为了提高速度，我使用了一个mutable.HashMap，现在代码看起来像这样：

val MVL : Long = Integer.MAX_VALUE
var modPow = new scala.collection.mutable.HashMap [(Long, Int, Long), Long ] () 

def powMod (b: Long, pot: Int, mod: Long) : Long = { 
      if (pot == 1) b % mod else modPow.getOrElseUpdate ((b, pot, mod), {
    val pot2= pot/2
    val pm1 = powMod (b, pot2, mod)             
    val pm2 = powMod (b, pot-pot2, mod)
    val res = (pm1 * pm2) 
    // avoid Long-overrun
    if (pm1 < MVL && pm2 < MVL)
        res % mod else {
            val f1: BigInt = pm1
            val f2: BigInt = pm2
            val erg = (f1 * f2) % mod
            erg.longValue 
        }
      })
}

你可能会问自己，是否真的需要长声明的MVL，或者是否

if (pm1 < Integer.MAX_VALUE && ...

也许会奏效。不，不会的。:) 要避免另一个陷阱。:)

最后它相当快速而且正确，并且我学到了两个有关内存越界和 MAX_VALUE - 比较的教训。

- user unknown

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Daniel C. Sobral · Accepted Answer

我认为答案在这里：

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

就是这样。