title: Lenstra's elliptic curve factorization problems
body: <p>I'm trying to use <a href="http://en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorization" rel="nofollow">Hendrik Lenstra's elliptic curve factoring method</a> to factor small (less than 40 bits) composite integers. </p>
  
  <pre><code>import math 
  from fractions import gcd
  import random 
  
  def lenstra_elliptic_curve_factor(N):
       """ Lenstra's elliptic curve factoring method """
  
      if N &lt;=0:
      raise Exception("Integer %s must be possitive " % N) 
  
      # Can't be 1 and can't factor a prime! 
      if 1 &lt;= N &lt;= 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)
  </code></pre>
  
  <p>Where <code>is_probably_prime()</code> is the <a href="http://rosettacode.org/wiki/Miller-Rabin_primality_test#Python" rel="nofollow">Miller-Rabin test</a> with number of trials set to 20. It seems that for some composite numbers, for example 4, it doesn't find non-trivial <code>gcd(x-x0)</code>, 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, <code>return lenstra_elliptic_curve_factor(int(d)) + lenstra_elliptic_curve_factor(int(N/d))</code> adds a "NoneType" to a list. For example </p>
  
  <pre><code>for x in xrange(0,3241):
      print x, lenstra_elliptic_curve_factor(x) 
  </code></pre>
  
  <p>I get </p>
  
  <pre><code>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 &lt;module&gt;
       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
  </code></pre>
  
  <p>I've tried increasing the number of curves tested to <code>N**10</code> 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. </p>