Dixon 因式分解法

为了找到 整数 和 使得

(1)

（费马因式分解法的一种变形），在这种情况下，有 50% 的几率 是 的一个 因子，选择一个 随机 整数 ，计算

(2)

并尝试分解 。如果 不容易分解（直至某个小的试除数 ），尝试另一个 。在实践中，试用的 通常取为 ，其中 , 2, ..., 这使得可以使用 二次筛法 因式分解方法。继续寻找并分解 ，直到找到 ，其中 是 素数计数函数。现在对于每个 ，写出

(3)

并形成 指数向量

(4)

现在，如果对于任何 ， 都是偶数，那么 是一个 平方数，并且我们找到了方程 (◇) 的解。否则，寻找一个 线性组合 ，使得所有元素都是偶数，即，

(5)

(6)

由于这必须仅在模 2 下求解，因此可以通过将 s 替换为

(7)

高斯消元法 然后可以用来求解

(8)

对于 ，其中 是一个等于 (mod 2) 的 向量。一旦 已知，那么我们有

(9)

其中乘积是对所有 取的，对于这些 。两边都是 完全平方数，因此我们有 50% 的几率，这会产生 的一个非平凡因子。如果不是，那么我们继续使用不同的 并重复该过程。不能保证此方法会产生因子，但在实践中，它比任何使用试除数的方法产生因子的速度都快。它特别适合并行处理，因为每个处理器都可以处理不同的 值。