如何在Python3中求解含未知变量s的模运算与指数方程？

问题分析 #

原方程包含模p下的逆元pow(2*s, -1, p)，SymPy无法直接处理带模逆元的方程，因此需要先将方程转化为模p下的整式方程，消除分式项，再求解多项式的根。

步骤1：方程整式化 #

原方程：

y ≡ [sm(s² - x) - 3m²(s² - x)²*(2s)⁻¹ - s*x] mod p

由于(2s)⁻¹是模p下2s的逆元，等价于(2s)*inv ≡ 1 mod p。两边同时乘以2s（需注意s≠0 mod p，后续单独验证s=0是否为解），得到：

2sy ≡ 2s²m*(s² - x) - 3m²(s² - x)² - 2s²*x mod p

展开并整理所有项，合并同类项后得到关于s²的二次方程（令t = s²）：

(2m - 3m²)t² + (-2m x - 2x - 2y + 6m² x)t - 3m² x² ≡ 0 mod p

先求解t，再通过求t的平方根模p得到s的可能值。

步骤2：代码实现 #

方法1：使用SymPy处理有限域 #

利用SymPy的GF(p)（有限域）构造多项式，直接求解根：

from sympy import symbols, GF, Poly, solve

# 替换为实际已知参数
x_val = 5
m_val = 2
p_val = 101
y_val = 30

# 1. 初始化有限域GF(p)
F = GF(p_val)

# 2. 将参数转换为有限域元素
x = F(x_val)
m = F(m_val)
y = F(y_val)

# 3. 构造关于t的二次多项式（t = s²）
t = symbols('t')
a = 2*m - 3*m**2
b = -2*m*x - 2*x - 2*y + 6*m**2*x
c = -3*m**2*x**2

poly_t = Poly(a*t**2 + b*t + c, t, domain=F)
t_solutions = solve(poly_t, t)

# 4. 对每个t解求s的平方根（模p下）
s_solutions = []
for t_val in t_solutions:
    roots = [r for r in F if r**2 == t_val]
    s_solutions.extend(roots)

# s=0时原方程中逆元项无意义，直接跳过验证
print("所有可能的s解（模p）：", s_solutions)

方法2：暴力枚举法（适合小p值） #

当p较小时，直接枚举0到p-1的所有可能s，验证是否满足原方程：

# 替换为实际已知参数
x = 5
m = 2
p = 101
y = 30

solutions = []
for s_candidate in range(p):
    try:
        # 计算原方程左侧值
        term1 = s_candidate * (s_candidate**2 - x) * m
        term2 = 3 * ((s_candidate**2 - x) * m) ** 2 * pow(2 * s_candidate, -1, p)
        term3 = s_candidate * x
        left = (term1 - term2 - term3) % p
        if left == y:
            solutions.append(s_candidate)
    except ValueError:
        # s=0时逆元不存在，直接跳过
        continue

print("所有可能的s解：", solutions)

关键注意事项 #

• s=0的有效性：原方程中pow(2*s, -1, p)要求2s与p互质，因此s=0不是有效解（0无逆元）。
• 平方根存在性：模p下并非所有t都存在平方根，当p为奇素数时，可通过欧拉判别法t^((p-1)/2) ≡ 1 mod p判断是否存在平方根。
• 特殊情况处理：若m=0，原方程简化为y ≡ -s*x mod p，可直接求解s ≡ -y*x⁻¹ mod p（x与p互质时）。

内容的提问来源于stack exchange，提问作者Aviril Smith