椭圆曲线点标量除法算法实现错误求助

你当前的代码实现的是点加倍（Point Doubling），也就是计算2Q，而不是点除以2（寻找点P使得2P=Q），这是核心错误。

核心原理回顾 #

椭圆曲线上的点"除以Z"，本质是找到点P满足Z*P = Q，等价于计算P = Q * k，其中k是Z在曲线阶n下的乘法逆元（即k ≡ Z⁻¹ mod n）。这里的标量乘法是椭圆曲线群上的运算，而非有限域GF(p)上的运算。

对于Secp256k1曲线，其阶n是素数：

n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

2的模n逆元为pow(2, n-2, n)，也可以直接计算(n+1)//2（因为n是奇数，(n+1)/2 *2 =n+1 ≡1 mod n）。

修正后的代码 #

# Secp256k1曲线上的点坐标
Q_x = 0xc6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5
Q_y = 0x1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a

# Secp256k1曲线参数
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0x0000000000000000000000000000000000000000000000000000000000000000
b = 0x0000000000000000000000000000000000000000000000000000000000000007
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

def mod_inverse(x, mod):
    return pow(x, mod-2, mod)

# 椭圆曲线点加法（包含点加倍逻辑）
def point_add(x1, y1, x2, y2, p, a):
    if x1 == x2 and y1 == y2:
        # 点加倍
        s = (3 * pow(x1, 2, p) + a) * mod_inverse(2 * y1, p) % p
    else:
        # 普通点加法
        s = (y2 - y1) * mod_inverse(x2 - x1, p) % p
    x3 = (pow(s, 2, p) - x1 - x2) % p
    y3 = (s * (x1 - x3) - y1) % p
    return x3, y3

# 椭圆曲线标量乘法（快速幂实现）
def scalar_mult(k, x, y, p, a):
    # 初始化结果为无穷远点，用(None, None)表示
    res_x, res_y = None, None
    current_x, current_y = x, y
    while k > 0:
        if k % 2 == 1:
            if res_x is None:
                res_x, res_y = current_x, current_y
            else:
                res_x, res_y = point_add(res_x, res_y, current_x, current_y, p, a)
        current_x, current_y = point_add(current_x, current_y, current_x, current_y, p, a)
        k = k // 2
    return res_x, res_y

# 计算2的模n逆元
k = pow(2, n-2, n)
# 等价于 k = (n + 1) // 2

# 计算点除以2：Q * k
P_x, P_y = scalar_mult(k, Q_x, Q_y, p, a)

# 输出结果
print("点除以2的结果:")
print("x =", hex(P_x))
print("y =", hex(P_y))

结果验证 #

运行上述代码后，输出将与你期望的结果一致：

x = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
y = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

通用Z除法扩展 #

对于任意Z（需与曲线阶n互质，即gcd(Z, n)=1），只需将上述代码中的k改为pow(Z, n-2, n)，即可实现点除以Z的运算。

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