Lenstra's elliptic curve factorization problems

Question

I'm trying to use Hendrik Lenstra's elliptic curve factoring method to factor small (less than 40 bits) composite integers.

import math 
from fractions import gcd
import random 

def lenstra_elliptic_curve_factor(N):
     """ Lenstra's elliptic curve factoring method """

    if N <=0:
    raise Exception("Integer %s must be possitive " % N) 

    # Can't be 1 and can't factor a prime! 
    if 1 <= N <= 2 or is_probable_prime(N):
        return [N]

    # random point in the plain (values less than N)
    x0, y0 = random.randrange(1, N), random.randrange(1, N)

    factors = list()
    bound = int(math.sqrt(N))

    for a in xrange(2,N):
        # Build curve out of random points
        b = y0**2 - x0**3 - a*x0

        # Check curve is not singular 
        if 4*a**3 - 27*b**2 ==0:
            continue

        # Initially double point 
        s = 3*x0**2 + a
        (x,y) = (s**2 - 2*x0, s*((s**2 - 2*x0) - x0) - y0)

    # Keep adding points until gcd(x-x0,N) != 1
    for k in xrange(2,bound):
        for i in xrange(0,math.factorial(k)):
            d = gcd(x- x0,N)
            if d != 1:
                return lenstra_elliptic_curve_factor(int(d)) + lenstra_elliptic_curve_factor(int(N/d))
            else:
                # Point doubling arithmetic 
                s = (y - y0) * modInv(x - x0,N)
                x = s**2 - x - x0  
                y = - y + s * (s**2 - x - x0 - x)

Where is_probably_prime() is the Miller-Rabin test with number of trials set to 20. It seems that for some composite numbers, for example 4, it doesn't find non-trivial gcd(x-x0), instead the algorithm goes all the way through and returns nothing. So when the algorithm tries to factor a larger number which 4 divides, like 12 for example, return lenstra_elliptic_curve_factor(int(d)) + lenstra_elliptic_curve_factor(int(N/d)) adds a "NoneType" to a list. For example

for x in xrange(0,3241):
    print x, lenstra_elliptic_curve_factor(x) 

I get

0 [0]
1 [1]
2 [2]
3 [3]
4 None
5 [5]
6 None
7 [7]
8 None
9 [3, 3]
10 [2, 5]
11 [11]
12

Traceback (most recent call last):
File "/AVcrypto/util.py", line 160, in <module>
     print x, lenstra_elliptic_curve_factor(x) 
File "/Users/Kevin/gd/proj/curr/honproj/AVcrypto/util.py", line 104, in lenstra_elliptic_curve_factor
     return lenstra_elliptic_curve_factor(int(d)) + lenstra_elliptic_curve_factor(int(N/d))
TypeError: can only concatenate list (not "NoneType") to list

I've tried increasing the number of curves tested to N**10 but it seems to have the same result. I'm just wondering if anyone has any experience with this algorithm, specifically where certain numbers seem to avoid the trial process for an incredibly long time.

Answer 1

Lenstra's algorithm assumes that the number being factored is co-prime to 6 (that is, has no factors of 2 or 3). Trying to factor 4 will not work. A more realistic test is to factor 13290059.

I assume you know that ECM is vast overkill for 40-bit numbers.