Python ECC密码学代码出现Exception:not found错误求助

错误根源 #

从报错回溯可以明确：异常来自sqrt(n, q)函数，当代码尝试生成椭圆曲线上的点时，给定x值代入曲线方程后，对应的y² ≡ x³ + ax + b mod q在有限域GF(q)中不存在平方根，因此找不到合法的y坐标，触发了not found异常。这个问题出在ec.at(at)调用的底层逻辑里。

无效方案说明 #

你尝试的use \Exception as Exception;是PHP语法，和Python完全不兼容，对当前问题毫无帮助，直接弃用即可。

可行解决步骤 #

• 校验椭圆曲线参数：先确认a、b、num（推测是有限域阶q）是否符合椭圆曲线规范，必须满足4a³ + 27b² ≠ 0 mod q，否则曲线是奇异的，会出现大量无法生成点的x值。
• 修正at参数的选取逻辑：at对应的x值必须满足x³+ax+b是模q的二次剩余。可以在调用ec.at()前，先用欧拉判别法验证：计算pow(n, (q-1)//2, q)，若结果为1则是二次剩余，才继续生成点；否则更换x值。
• 给EC.at()方法加容错循环：如果at是随机或序列取值，找不到对应点时自动迭代下一个x值，直到找到合法点，示例修改：

def at(self, idx):
    x = idx % self.q
    while True:
        n = (x**3 + self.a * x + self.b) % self.q
        try:
            y1, y2 = sqrt(n, self.q)
            return (x, y1), (x, y2)
        except Exception:
            x = (x + 1) % self.q

• 改用标准曲线参数：直接使用secp256r1、secp256k1这类经过验证的标准椭圆曲线参数，避免自行定义参数导致的兼容性或合法性问题。

调试建议 #

打印触发异常时的n和q值，手动验证n是否为模q的二次剩余：

def is_quadratic_residue(n, q):
    if n == 0:
        return True
    return pow(n, (q-1)//2, q) == 1

如果is_quadratic_residue(n,q)返回True但sqrt函数仍报错，说明你的平方根求解函数实现有问题，需要重新排查逻辑。

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