整数因式分解

二次筛

比尔哈特的二次筛子随Sage一起提供。二次筛法是分解形式数的最佳算法之一 \(pq\) 最高可达100位左右。它涉及到寻找关系，解决模线性代数问题 \(2\) ，然后进行保理 \(n\) 使用关系 \(x^2 \equiv y^2 \mod n\) 。使用QSieve算法可以比使用PARI的默认算法更快。

sage: n = next_prime(2^90)*next_prime(2^91)
sage: n.factor(algorithm="qsieve")
doctest:... RuntimeWarning: the factorization returned
by qsieve may be incomplete (the factors may not be prime)
or even wrong; see qsieve? for details
1237940039285380274899124357 * 2475880078570760549798248507
sage: n.factor()  # uses PARI at the time of writing
1237940039285380274899124357 * 2475880078570760549798248507

GMP-ECM

保罗·齐默尔曼的GMP-ECM包含在Sage中。椭圆曲线因式分解(ECM)算法是分解形式数的最佳算法 \(n=pm\) ，在哪里 \(p\) 并不是“太大”。ECM是Hendrik Lenstra提出的一种算法，它的工作原理是“假装” \(n\) 是素数，选择一条随机的椭圆曲线 \(\ZZ/n\ZZ\) ，并在这条曲线上进行算术--如果在进行算术时出现错误，我们会考虑 \(n\) 。

在下面的例子中，GMP-ECM比Sage的通用因子函数快得多。这再次强调了最佳分解算法可能取决于您的特定问题。

sage: n = next_prime(2^40) * next_prime(2^300)
sage: n.factor(algorithm="ecm")
1099511627791 * 2037035976334486086268445688409378161051468393665936250636140449354381299763336706183397533
sage: n.factor()  # uses PARI at the time of writing
1099511627791 * 2037035976334486086268445688409378161051468393665936250636140449354381299763336706183397533