Having written some code for the Lenstra elliptic-curve factorization algorithm, I'm fairly happy with it. However, it only works some of the time. The function that adds points should return either an integer or a point. In the case it returns an integer d the Lenstra block of code should simply print the gcd(d,n) and exit. It seems some of the time it doesn't exit and then tries to put an integer into the add function which then fails with an attribute error. I've tried tinkering and can't seem to correct it.
Could someone please tell me what's going on or how to correct the code? I'm happy to answer any questions as I'm not a programmer and I know my code is far from tidy.
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))
Most of the time this will run fine and return an integer divisor; however, sometimes a curve is generated where I get the following error:
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'
You can reproduce this error by instead of using a random curve you set the parameters as a= 6518263 b=1551605 P = Point(x=6433033, y=7097171). It fails as when P = 11 it doesn't print and exit--it seems to try to try to call the point_multiply function with 11 as a parameter. I can't seem to stop this behavior, and I have tried many methods.
I've found that if I add this:
if type(Q) == int:
return Q
to the start of the function point_add(), then it seems to work as intended, though this isn't, I feel, ideal.
You aren't checking the result of the two point_add calls inside point_multiply to return
if an int instead of a Point is returned.
I'm going to suggest something a little unorthodox that will offend some programming purists.
I think you should use an Exception to signal when a possible factor has been found.
It will make your code much cleaner and understandable in my opinion, and because finding a
factor is an "exceptional" condition it will not harm performance. Here is the code with
the minimal modifications to use an NotInvertibleError user-defined exception, and it
also corrects a bug or two.
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))
I would strongly discourage the use of Exceptions for returning values, but in the case of some factoring algorithms including Lenstra's Elliptic curve factoring the exceptional condition, the failure to compute an inverse, is what triggers the discovery of the factor, thus it is somewhat natural to propagate the exception with a little bit of additional information.