Lenstras 属性错误的椭圆曲线问题
Lenstras Elliptic curve problem with attribute error
为 Lenstra elliptic-curve factorization algorithm 编写了一些代码，我对此非常满意。但是，它只在某些时候有效。添加点的函数应该 return 一个整数或一个点。如果它 returns 是一个整数 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))
大多数时候这会 运行 很好，return 一个整数除数；但是，有时会生成一条曲线，出现以下错误：
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 到 return 中的两个 point_add 调用的结果
如果 int 而不是点 returned.
我将提出一些有点非正统的建议，这些建议会冒犯一些编程纯粹主义者。
我认为您应该在找到可能的因素时使用 Exception 发出信号。
在我看来，这将使您的代码更加清晰易懂，并且因为找到了
factor 是一个 "exceptional" 条件，它不会损害性能。这是代码
使用 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))
我强烈反对对 returning 值使用异常，
但对于某些因式分解算法，包括 Lenstra 的 Elliptic
曲线分解异常条件，无法计算逆，
是触发因素发现的原因，因此很自然地
使用一些附加信息传播异常。
为 Lenstra elliptic-curve factorization algorithm 编写了一些代码，我对此非常满意。但是，它只在某些时候有效。添加点的函数应该 return 一个整数或一个点。如果它 returns 是一个整数 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))
大多数时候这会 运行 很好，return 一个整数除数；但是，有时会生成一条曲线，出现以下错误：
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 到 return 中的两个 point_add 调用的结果
如果 int 而不是点 returned.
我将提出一些有点非正统的建议，这些建议会冒犯一些编程纯粹主义者。
我认为您应该在找到可能的因素时使用 Exception 发出信号。
在我看来，这将使您的代码更加清晰易懂，并且因为找到了
factor 是一个 "exceptional" 条件，它不会损害性能。这是代码
使用 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))
我强烈反对对 returning 值使用异常， 但对于某些因式分解算法，包括 Lenstra 的 Elliptic 曲线分解异常条件，无法计算逆， 是触发因素发现的原因，因此很自然地 使用一些附加信息传播异常。