使用gmpy2的Python程序崩溃（Scala可运行）：mpz溢出/核心转储

我在使用gmpy2库运行模幂运算时遇到程序崩溃问题，但相同逻辑在Scala中用BigInteger.modPow()能正常运行并输出'good'。想确认这是gmpy2的已知bug，还是我的Python代码存在错误？

Scala 可正常运行代码 #

import java.math.BigInteger

import java.nio.charset.StandardCharsets
import java.util.Base64


object Example extends App {
  val pstr: String ="134078079299425970995740249982058461274793658205923933" +
    "77723561443721764030073546976801874298166903427690031" +
    "858186486050853753882811946569946433649006084171"
  val gstr = "11717829880366207009516117596335367088558084999998952205"  +
    "59997945906392949973658374667057217647146031292859482967"  +
    "5428279466566527115212748467589894601965568"
  val hstr = "323947510405045044356526437872806578864909752095244"  +
    "952783479245297198197614329255807385693795855318053"  +
    "2878928001494706097394108577585732452307673444020333"


  val decodedBytes = Base64.getDecoder.decode("Mzc1Mzc0MjE3ODMw")
  val decodedString = new String(decodedBytes, StandardCharsets.UTF_8)     // obfuscated ... can't fall into wrong hands

  val p: BigInteger = new BigInteger(pstr)
  val g: BigInteger = new BigInteger(gstr)
  val h: BigInteger = new BigInteger(hstr)
  val exponent: BigInteger = new BigInteger(decodedString)

  val recover = g.modPow(exponent, p)

  if (recover == h)
    print("good")
  else
    print("bad")
}

Python 崩溃代码 #

import gmpy2
import base64

pstr = "134078079299425970995740249982058461274793658205923933" + \
       "77723561443721764030073546976801874298166903427690031" + \
       "858186486050853753882811946569946433649006084171"

gstr = "11717829880366207009516117596335367088558084999998952205" + \
       "59997945906392949973658374667057217647146031292859482967" + \
       "5428279466566527115212748467589894601965568"

hstr = "323947510405045044356526437872806578864909752095244" + \
       "952783479245297198197614329255807385693795855318053" + \
       "2878928001494706097394108577585732452307673444020333"

p = gmpy2.mpz(pstr)
g = gmpy2.mpz(gstr)
h = gmpy2.mpz(hstr)

secret_exponent_encoded = base64.b64decode(b'Mzc1Mzc0MjE3ODMw').decode('utf-8')
exponent = gmpy2.mpz(secret_exponent_encoded)
recover = (g ** exponent) % p

if (recover == h):
    print("true")
else:
    print("false")

问题原因与修正 #

崩溃的核心原因是Python代码中使用了(g ** exponent) % p的写法：这种方式会先计算g的exponent次幂，生成一个极其庞大的中间值，直接耗尽内存导致程序崩溃。而Scala的BigInteger.modPow()是高效模幂运算，会在计算过程中持续取模，不会生成超大中间值。

gmpy2同样提供了高效的模幂实现，只需将崩溃代码中的模幂计算替换为gmpy2.pow(g, exponent, p)即可。

修正后的Python代码：

import gmpy2
import base64

pstr = "134078079299425970995740249982058461274793658205923933" + \
       "77723561443721764030073546976801874298166903427690031" + \
       "858186486050853753882811946569946433649006084171"

gstr = "11717829880366207009516117596335367088558084999998952205" + \
       "59997945906392949973658374667057217647146031292859482967" + \
       "5428279466566527115212748467589894601965568"

hstr = "323947510405045044356526437872806578864909752095244" + \
       "952783479245297198197614329255807385693795855318053" + \
       "2878928001494706097394108577585732452307673444020333"

p = gmpy2.mpz(pstr)
g = gmpy2.mpz(gstr)
h = gmpy2.mpz(hstr)

secret_exponent_encoded = base64.b64decode(b'Mzc1Mzc0MjE3ODMw').decode('utf-8')
exponent = gmpy2.mpz(secret_exponent_encoded)
# 使用gmpy2内置的高效模幂函数
recover = gmpy2.pow(g, exponent, p)

if recover == h:
    print("true")
else:
    print("false")

内容的提问来源于stack exchange，提问作者Chris Bedford