解释 pow(g, exp, p)

16 2025-09-03 09:00

在 Python 中，pow(g, exp, p) 是一个内置函数，用于计算模幂运算。具体来说，它计算的是：

text

g^exp mod p

即 g 的 exp 次幂对 p 取模的结果。

为什么这在寻找原根时很重要？

在寻找质数 p 的原根时，我们需要找到一个数 g，使得 g 的阶（即满足 g^k ≡ 1 mod p 的最小正整数 k）等于 p-1。

为了验证一个候选数 g 是否是原根，我们需要检查对于 p-1 的所有质因数 q，都有：

text

g^((p-1)/q) ≢ 1 mod p

pow(g, exp, p) 函数正是用来高效计算这些模幂运算的。

假设我们想计算 2^10 mod 11：

python

result = pow(2, 10, 11)  # 结果是 1，因为 2^10 = 1024，1024 mod 11 = 1

在寻找原根的程序中，我们使用这个函数来高效地检查候选数是否满足原根的条件，而不需要处理极大的中间结果。