如何通过模NP'的模逆运算求解同余方程中的乘数multiplier

已知参数 #

• 椭圆曲线阶 N = 115792089237316195423570985008687907852837564279074904382605163141518161494337
• 素数域模数 p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
• 已知余数值 Gx = 18330083172231516910921476241581278950469869051063175177377276968000913867056

待求解方程 #

题目给出的同余关系如下，其中NP' = (N + p)/2为运算模数：

((N - 1) * multiplier) mod NP' = Gx

求解步骤 #

这是标准的一元线性同余方程，形式为a * x ≡ b mod m，当系数a和模数m互素时，可以通过模逆运算直接得到唯一解，具体操作如下：

1. 先计算确定模数m = (N + p) // 2：N和p均为奇数，二者之和为偶数，除以2后得到整数结果，不存在余数。
2. 提取方程系数：左侧乘系数a = N - 1，方程右侧常数项b = Gx，方程转化为标准形式a * multiplier ≡ b mod m。
3. 验证互素性：针对这组secp256k1曲线的关联参数，可验证gcd(a, m) = 1，a在模m下的乘法逆元存在，方程有唯一模m解。
4. 计算模逆元：使用扩展欧几里得算法计算a在模m下的逆元a_inv，满足(a * a_inv) mod m = 1；如果提前确认m为素数，也可以用费马小定理简化计算，即a_inv = pow(a, m-2, m)。
5. 计算结果：方程两边同时乘以a_inv，即可得到解：multiplier = (b * a_inv) mod m。

可直接运行的计算代码 #

使用Python原生大整数支持即可完成计算，无需额外依赖：

N = 115792089237316195423570985008687907852837564279074904382605163141518161494337
p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
Gx = 18330083172231516910921476241581278950469869051063175177377276968000913867056

m = (N + p) // 2
a = N - 1
# Python 3.8及以上版本支持pow三参数传入-1直接计算模逆
a_inv = pow(a, -1, m)
multiplier = (Gx * a_inv) % m

# 结果校验
assert ((N - 1) * multiplier) % m == Gx, "计算结果错误"
print(f"求解得到的multiplier = {multiplier}")

注意：所有参数均为256位大整数，不要尝试手动计算，必须通过支持高精度整数运算的工具完成求解。

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