Lenstra椭圆曲线因式分解问题

Question

我正在尝试使用Hendrik Lenstra's elliptic curve factoring method来分解小的(少于40位)复合整数。

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)

其中is_probably_prime()是试验次数设置为20的Miller-Rabin test。似乎对于某些合成数，例如4，它找不到非平凡的gcd(x-x0)，相反，算法一直走到最后，什么也不返回。因此，当算法尝试分解一个4除以的更大的数字时，例如12，return lenstra_elliptic_curve_factor(int(d)) + lenstra_elliptic_curve_factor(int(N/d))会在列表中添加一个"NoneType“。例如

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

我得到了

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

我已经尝试增加N**10测试的曲线数量，但似乎有相同的结果。我只是想知道是否有人对这个算法有任何经验，特别是在某些数字似乎会在令人难以置信的长时间内避开试验过程的地方。

Answer 1

Lenstra的算法假设被分解的数字是6的共同质数(也就是说，没有2或3的因子)。尝试因数4将不起作用。一个更现实的测试是因数13290059。

我假设您知道ECM对于40位数字来说是过度杀伤力。