Skip to main content
 首页 » 编程设计

python之Lenstra 的椭圆曲线分解问题

2024年10月25日15lautakyan007

我正在尝试使用 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 但它似乎有相同的结果。我只是想知道是否有人对这种算法有任何经验,特别是某些数字似乎在很长一段时间内避免了试用过程。

请您参考如下方法:

Lenstra 的算法假设被因式分解的数字与 6 互质(即没有因数 2 或 3)。尝试因子 4 是行不通的。更现实的测试是因子 13290059。

我假设您知道 ECM 对于 40 位数字来说太过分了。