python - 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() 是 Miller-Rabin test试验次数设置为 20。似乎对于一些合数，例如 4，它没有找到非平凡的 gcd(x-x0)，而是算法一直通过什么都不返回。因此，当算法尝试分解一个更大的数(例如 12)时，例如 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 位数字来说太过分了。