Dixon 因式分解法

為了找到 整數 和 使得

(1)

（費馬因式分解法的一種變形），在這種情況下，有 50% 的機率 是 的一個 因子，選擇一個 隨機 整數 ，計算

(2)

並嘗試分解 。如果 不容易分解（直至某個小的試除數 ），嘗試另一個 。在實踐中，試用的 通常取為 ，其中 , 2, ..., 這使得可以使用 二次篩法 因式分解方法。繼續尋找並分解 ，直到找到 ，其中 是 素數計數函式。現在對於每個 ，寫出

(3)

並形成 指數向量

(4)

現在，如果對於任何 ， 都是偶數，那麼 是一個 平方數，並且我們找到了方程 (◇) 的解。否則，尋找一個 線性組合 ，使得所有元素都是偶數，即，

(5)

(6)

由於這必須僅在模 2 下求解，因此可以透過將 s 替換為

(7)

高斯消元法 然後可以用來求解

(8)

對於 ，其中 是一個等於 (mod 2) 的 向量。一旦 已知，那麼我們有

(9)

其中乘積是對所有 取的，對於這些 。兩邊都是 完全平方數，因此我們有 50% 的機率，這會產生 的一個非平凡因子。如果不是，那麼我們繼續使用不同的 並重復該過程。不能保證此方法會產生因子，但在實踐中，它比任何使用試除數的方法產生因子的速度都快。它特別適合並行處理，因為每個處理器都可以處理不同的 值。