Python 中的求模运算的数学幂函数

Question

我正在用模算术学习群同态（一个数学概念）。基本上，我想证明

g^(2x+8y) mod n

等于

(g^(2x) . g^(8y)) mod n

。

我有以下Python代码：

g = 57
n = 1000004119

import galois
GF = galois.GF(n)

# Adjusted values
x = GF(261099267)
y = GF(684728868)

# Direct calculation in field
lhs0 = pow(g, int(GF(2) * x + GF(8) * y), n)
print(f"lhs0 (direct calculation): {lhs0}")

# Separate exponent computations
exp1 = int(GF(2) * x)
exp2 = int(GF(8) * y)
print(f"exp1: {exp1}, exp2: {exp2}")

# Separate pow computations
lhs1l = pow(g, exp1, n)
lhs1r = pow(g, exp2, n)
lhs1 = (lhs1l * lhs1r) % n
print(f"lhs1l: {lhs1l}, lhs1r: {lhs1r}, lhs1: {lhs1}")

# Validate all expected relationships
assert lhs0 == lhs1, f"Final mismatch, lhs0: {lhs0}, lhs1: {lhs1}"

最后一个断言语句将失败并显示

Final mismatch, lhs0: 366446438, lhs1: 887364586

这是为什么？

---

仅供参考，如果我将上面的 x 和 y 值更改为：

x = GF(420)
y = GF(888)

assert 语句将会通过。 Python 代码下面发生了什么？

我希望Python中不会出现溢出错误。如果有的话，在Python中进行大整数模运算时应该采取什么预防措施？谢谢。

Answer 1

在朋友的帮助下，我了解到，当 2x + 8y > n 时，

g^(2x+8y) mod n

不一定等于

(g^(2x) . g^(8y)) mod n

。

基本上，

x + y = z

必须在整数域中成立，而不仅仅是模算术（伽罗瓦域），才能使

g^(x+y) mod n = g^x . g^y mod n

成立。

如果 x = GF(261099267), y = GF(684728868)，则

2x + 8y = 6,000,029,478，大于

n

(1,000,004,119)。

但是在 x = GF(420), y = GF(888) 的情况下，那么

2x + 8y = 7,944，小于

n

。在这种情况下，同态关系成立。