已经为 Lenstra elliptic-curve factorization algorithm 编写了一些代码，我对此还算满意。然而，它只在某些时候有效。添加点的函数应返回整数或点。如果它返回整数 d，Lenstra 代码块应该简单地打印 gcd(d,n) 并退出。似乎有时它不会退出，然后尝试将整数放入 add 函数，然后因属性错误而失败。我尝试过修补，但似乎无法纠正。
有人可以告诉我发生了什么事或如何更正代码吗？我很乐意回答任何问题，因为我不是程序员，而且我知道我的代码还很不整洁。
from sympy import mod_inverse
import math
import secrets
from collections import namedtuple
Point = namedtuple("Point", "x y")
def point_valid(P,a,b,p):
O = 'Inf_Point'
if P == O:
return True
else:
return (P.y**2 - (P.x**3 + a*P.x + b)) % p == 0 and 0 <= P.x < p and 0 <= P.y < p
def inverse_point(P,p):
O = 'Inf_Point'
# Just calculates the inverse point
if P == O:
return P
return Point(P.x, (-P.y) % p)
def point_add(P, Q, a, b, p):
O = 'Inf_Point'
# Checking that the points are valid if not raise an exception error
if not (point_valid(P,a,b,p) and point_valid(Q,a,b,p)):
raise ValueError("Invalid inputs")
if P == O:
R = Q
elif Q == O:
R = P
elif Q == inverse_point(P,p):
R = O
else:
if P == Q:
try:
inv = mod_inverse(2 * P.y,p)
except ValueError:
return 2 * P.y
dydx = (3 * P.x**2 + a) * inv
else:
try:
inv = mod_inverse(Q.x - P.x,p)
except ValueError:
return Q.x - P.x
dydx = (Q.y - P.y) * inv
x = (dydx**2 - P.x - Q.x) % p
y = (dydx * (P.x - x) - P.y) % p
R = Point(x, y)
# Making sure the result is on the curve
assert point_valid(R,a,b,p)
# Returning the result
return R
def point_multiply(P,n,a,b,p):
O = 'Inf_Point'
Q = P
R = O
while n > 0:
if n % 2 == 1:
R = point_add(R,Q,a,b,p)
Q = point_add(Q,Q,a,b,p)
n = math.floor(n/2)
if n > 0:
continue
return R
def random_curve(N):
while True:
A = secrets.randbelow(N)
x = secrets.randbelow(N)
y = secrets.randbelow(N)
P = Point(x,y)
B = (y**2 - x**3 - A*x) % N
if (4*A**3 + 27*B**2) % N != 0:
return (A,B,P)
def lenstra(N,B):
a,b,P = random_curve(N)
for i in range(2,B+1):
if type(P)== int:
d = math.gcd(P,N)
if d < N:
return d
elif d == N:
print('start again')
Q = point_multiply(P,i,a,b,N)
P = Q
print(lenstra(8453621,15))
大多数情况下，它会运行良好并返回一个整数除数；但是，有时会生成一条曲线，并出现以下错误:
Traceback (most recent call last):
File "C:/Users/conta/PycharmProjects/Cryptography/Lenstras_Elliptic_Factor.py", line 99, in <module>
Point(x=6653683, y=2444813)
print(lenstra(8453621,15))
Point(x=1943642, y=922559)
File "C:/Users/conta/PycharmProjects/Cryptography/Lenstras_Elliptic_Factor.py", line 96, in lenstra
Q = point_multiply(P,i,a,b,N)
File "C:/Users/conta/PycharmProjects/Cryptography/Lenstras_Elliptic_Factor.py", line 65, in point_multiply
R = point_add(R,Q,a,b,p)
File "C:/Users/conta/PycharmProjects/Cryptography/Lenstras_Elliptic_Factor.py", line 27, in point_add
if not (point_valid(P,a,b,p) and point_valid(Q,a,b,p)):
File "C:/Users/conta/PycharmProjects/Cryptography/Lenstras_Elliptic_Factor.py", line 13, in point_valid
return (P.y**2 - (P.x**3 + a*P.x + b)) % p == 0 and 0 <= P.x < p and 0 <= P.y < p
AttributeError: 'int' object has no attribute 'y'
您可以通过将参数设置为 a= 6518263 b=1551605 P = Point(x=6433033, y=7097171) 来重现此错误，而不是使用随机曲线。它失败了，因为当 P = 11 时，它不会打印并退出——它似乎尝试尝试以 11 作为参数调用 point_multiply 函数。我似乎无法阻止这种行为，我尝试了很多方法。
我发现如果我添加这个:
if type(Q) == int:
return Q
到函数 point_add() 的开头，然后它似乎按预期工作，尽管我觉得这不是理想的。
最佳答案
您没有检查 point_multiply 内两个 point_add 调用的结果以返回
如果返回的是 int 而不是 Point。
我将提出一些有点非正统的建议，这会冒犯一些编程纯粹主义者。
我认为当发现可能的因素时，您应该使用Exception来发出信号。
在我看来，这将使您的代码更加清晰和易于理解，并且因为找到一个
因素是一个“异常(exception)”条件，它不会损害性能。这是代码
使用 NotInvertibleError 用户定义异常的最小修改，并且它
还纠正了一两个错误。
import math
import secrets
from collections import namedtuple
import sympy
Point = namedtuple("Point", "x y")
class NotInvertibleError(Exception):
def __init__(self, value):
self.value = value
def mod_inverse(a, m):
try:
return sympy.mod_inverse(a, m)
except ValueError:
raise NotInvertibleError(a)
def point_valid(P, a, b, p):
O = 'Inf_Point'
if P == O:
return True
else:
return (P.y ** 2 - (P.x ** 3 + a * P.x + b)) % p == 0 and 0 <= P.x < p and 0 <= P.y < p
def inverse_point(P, p):
O = 'Inf_Point'
# Just calculates the inverse point
if P == O:
return P
return Point(P.x, (-P.y) % p)
def point_add(P, Q, a, b, p):
O = 'Inf_Point'
# Checking that the points are valid if not raise an exception error
if not (point_valid(P, a, b, p) and point_valid(Q, a, b, p)):
raise ValueError("Invalid inputs")
if P == O:
R = Q
elif Q == O:
R = P
elif Q == inverse_point(P, p):
R = O
else:
if P == Q:
inv = mod_inverse(2 * P.y, p)
dydx = (3 * P.x ** 2 + a) * inv
else:
inv = mod_inverse(Q.x - P.x, p)
dydx = (Q.y - P.y) * inv
x = (dydx ** 2 - P.x - Q.x) % p
y = (dydx * (P.x - x) - P.y) % p
R = Point(x, y)
# Making sure the result is on the curve
assert point_valid(R, a, b, p)
# Returning the result
return R
def point_multiply(P, n, a, b, p):
O = 'Inf_Point'
Q = P
R = O
while n > 0:
if n % 2 == 1:
R = point_add(R, Q, a, b, p)
Q = point_add(Q, Q, a, b, p)
n = math.floor(n / 2)
if n > 0:
continue
return R
def random_curve(N):
while True:
A = secrets.randbelow(N)
x = secrets.randbelow(N)
y = secrets.randbelow(N)
P = Point(x, y)
B = (y ** 2 - x ** 3 - A * x) % N
if (4 * A ** 3 + 27 * B ** 2) % N != 0:
return (A, B, P)
def lenstra(N, B):
while True:
a, b, P = random_curve(N)
try:
for i in range(2, B + 1):
Q = point_multiply(P, i, a, b, N)
P = Q
except NotInvertibleError as e:
d = math.gcd(e.value, N)
if d < N:
return d
elif d == N:
print("start again")
while True:
print(lenstra(8453621, 15))
我强烈反对使用异常来返回值， 但对于一些因式分解算法，包括 Lenstra 的 Elliptic 曲线因式分解异常条件，无法计算逆， 是触发该因素发现的原因，因此这是很自然的 使用一些附加信息传播异常。
关于python-3.x - Lenstras 椭圆曲线属性错误问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/57579326/