Python模运算幂函数问题：为何g^(2x+8y)与(g^2x·g^8y)模n不等？

你遇到的问题核心是错误地将指数运算的加法放在了模n的有限域GF(n)中进行，而实际上模n乘法群的指数运算对应的是模φ(n)的整数加法（当g与n互质时），而非模n加法。

具体原因拆解 #

1. 两种计算方式的指数差异

   • 对于lhs0，你计算的指数是int(GF(2)*x + GF(8)*y)，这等价于(2x + 8y) mod n——因为GF(n)中的加法和乘法都是模n运算。
   • 对于lhs1，你计算的是exp1 + exp2 = (2x mod n) + (8y mod n)，这个值等于2x + 8y - k*n（k是2x和8y分别除以n的商的和）。当2x + 8y >= n时，exp1 + exp2会比(2x + 8y) mod n大n（比如当2x modn +8y modn >=n时，(2x+8y)modn = exp1+exp2 -n，而exp1+exp2 = (2x+8y)modn +n）。

2. 费马小定理的影响
   你的n=1000004119是质数（可验证：它不能被小质数整除，素性测试也能确认），根据费马小定理，对于与n互质的g（57与n互质），有：

   g^(n) ≡ g^(n-1) * g ≡ 1 * g ≡ g mod n
   

   所以当exp1 + exp2 = (2x+8y modn) +n时：

   g^(exp1+exp2) ≡ g^((2x+8y modn)+n) ≡ g^(2x+8y modn) * g^n ≡ g^(2x+8y modn) * g modn
   

   而lhs0是g^(2x+8y modn) modn，两者相差一个因子g（57），自然不相等。

3. 小x/y时为什么成立
   当x=420、y=888时，2x+8y=840+7104=7944远小于n，此时：

   • (2x+8y) modn = 2x+8y
   • exp1+exp2=2x+8y
     两个指数完全相等，因此g^exp的结果自然一致，断言通过。

Python底层与溢出问题 #

Python确实没有整数溢出问题——它支持任意精度整数。你的问题和溢出无关，完全是指数运算的模运算规则理解错误导致的。

模运算预防措施 #

• 明确指数运算的模规则：当计算g^a * g^b modn时，等价于g^(a+b) modn（这里a、b是整数）；但如果要利用欧拉/费马定理简化指数，应该将指数模φ(n)（n为质数时φ(n)=n-1），即g^k ≡ g^(k mod φ(n)) modn。
• 避免在GF(n)中计算指数：GF(n)是为有限域中的乘法/加法设计的，不适用于计算乘法群的指数——指数应该是整数运算，必要时模φ(n)而非n。
• 统一指数计算方式：要么直接计算整数加法2*x_int +8*y_int（x_int、y_int是原始整数，而非GF(n)元素），然后模φ(n)后再做幂运算；要么分开计算时，将每个指数也模φ(n)，示例代码如下：

  phi_n = n-1  # 因为n是质数
  lhs1l = pow(g, int(GF(2)*x) % phi_n, n)
  lhs1r = pow(g, int(GF(8)*y) % phi_n, n)
  lhs1 = (lhs1l * lhs1r) % n
  

  这样就能保证指数在模φ(n)下等价，结果一致。

内容的提问来源于stack exchange，提问作者Jimmy Chu