整数分解问题

二次筛

比尔·哈特的二次筛也包括在Sage中。二次筛是分解形式数的最佳算法 \(pq\) 最多100位数。它涉及到寻找关系，解决一个线性代数问题模 \(2\) ，然后是保理 \(n\) 使用关系 \(x^2 \equiv y^2 \mod n\) .

sage: qsieve(next_prime(2^90)*next_prime(2^91), time=True)   # not tested
([1237940039285380274899124357, 2475880078570760549798248507],
 '14.94user 0.53system 0:15.72elapsed 98%CPU (0avgtext+0avgdata 0maxresident)k')

在本例中，使用qsieve的速度是Sage的general factor命令的两倍。注意Sage的general factor命令只调用Pari的factor C库函数。

sage: time factor(next_prime(2^90)*next_prime(2^91))     # not tested
CPU times: user 28.71 s, sys: 0.28 s, total: 28.98 s
Wall time: 29.38 s
1237940039285380274899124357 * 2475880078570760549798248507

显然，Sage的factor命令不应该只调用Pari，但是还没有人能抽出时间重写它。

GMP-ECM

保罗齐默尔曼的GMP-ECM包含在Sage中。椭圆曲线的最佳因式分解算法（ECM）是椭圆曲线的最佳形式 \(n=pm\) 在哪里 \(p\) 不是“太大”。ECM是Hendrik Lenstra的一种算法，它通过“假装”来工作 \(n\) 是质数，选择一条随机椭圆曲线 \(\ZZ/n\ZZ\) ，然后在曲线上做算术-，如果做算术的时候出了问题，我们考虑 \(n\) .

在下面的例子中，GMP-ECM比Sage的通用因子函数快10倍以上。再次强调Sage的generic factor命令将从使用GMP-ECM和qsieve的重写中获益。

sage: time ecm.factor(next_prime(2^40) * next_prime(2^300))    # not tested
CPU times: user 0.85 s, sys: 0.01 s, total: 0.86 s
Wall time: 1.73 s
[1099511627791,
 2037035976334486086268445688409378161051468393665936250636140449354381299763336706183397533]
sage: time factor(next_prime(2^40) * next_prime(2^300))        # not tested
CPU times: user 23.82 s, sys: 0.04 s, total: 23.86 s
Wall time: 24.35 s
1099511627791 * 2037035976334486086268445688409378161051468393665936250636140449354381299763336706183397533