Проблемы разложения эллиптической кривой Ленстра

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), а алгоритм проходит весь путь через и ничего не возвращает. Поэтому, когда алгоритм пытается определить большее число, которое 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

Алгоритм Ленстра предполагает, что число, которое учитывается, является совместным с 6 (т. Е. Не имеет коэффициентов 2 или 3). Пытаться к коэффициенту 4 не получится. Более реалистичным критерием является фактор 13290059.

Я предполагаю, что вы знаете, что ECM является огромным излишеством для 40-битных чисел.