平方同餘

在數論中，平方同餘是個經常被用於整數分解演算法的同餘關係。

由來
給定一正整數 n，費馬因式分解法想找到兩數 x, y 滿足下列方程式：

: x^2-y^2=n

從上式我們便可以分解得 n = x2 - y2 = (x + y)(x - y)。 此演算法在實際用途上較慢因為我們需要試圖找出許多類似的數字，而只有一部分會滿足這個嚴格的式子。 然而， n 也可能可以被分解，如果我們能滿足以下較弱的平方同餘的情況：

: x^2 \equiv y^2 \pmod{n}
: x \not\equiv \pm y \pmod{n}

從上面二式我們可以輕易推得：

: x^2 - y^2 \equiv 0 \pmod{n}
: (x + y)(x - y) \equiv 0 \pmod{n}

這意味著 n 整除乘積 (x + y)(x - y)。 因此 (x + y) 以及 (x − y) 各自包含著 n 的因數， 但那些因數有可能是平凡的（等於 1 或是 n 本身）。 在這樣的情況下，我們需要找到其他的 x 和 y 。計算 (x + y, n) 和 (x - y, n) 的最大公因數將給我們這些因數；而這可以輾轉相除法快速得出。

平方同餘在整數分解演算法裡相當地有用、且廣為使用於，舉例來說，二次篩選法、 普通數域篩選法、連續分數因式分解法、 以及狄克森因式分解法。反過來說，因為要找到模一合數下的平方根概率上在多項式時間等價於分解該數， 任何整數分解演算法皆用於找到一個平方同餘數。

更進一步的一般化
其可以使用因數基底去幫助更快找到平方同餘。 比起從頭開始找 x^2 \equiv y^2 \pmod{n} ，不如我們找到許多的 x^2 \equiv y \pmod{n}，其中 y 只有小的質因數， 並試著去將其中幾個 y 乘在一起去得到一個平方數（在等號的右側）。

例子
分解 35
我們取 *n = 35** 並得：

: 6^2 = 36 \equiv 1 \equiv 1^2 \pmod{35}

因此分解成：

: \gcd( 6-1, 35 ) \cdot \gcd( 6+1, 35 ) = 5 \cdot 7 = 35

分解 1649
設 *n = 1649**， 並作為從一些非平方數的乘積建構出平方同餘的例子（參見 狄克森因式分解法）， 首先我們得到幾個同餘式：

: 41^2 \equiv 32 \pmod{1649}
: 42^2 \equiv 115 \pmod{1649}
: 43^2 \equiv 200 \pmod{1649}

在其之中，有兩個式子的數字只有小質數作為因數：

: 32 = 2^5
: 200 = 2^3 \cdot 5^2

且兩者的其中一個組合滿足質因數的次方皆為偶數，因此形成了一個平方數：

: 32 \cdot 200 = 2^{5+3} \cdot 5^2 = 2^8 \cdot 5^2 = ( 2^4 \cdot 5 )^2 = 80^2

因此得出平方同餘的關係式：

: 32 \cdot 200 = 80^2 \equiv 41^2 \cdot 43^2 \equiv 114^2 \pmod{1649}

所以分別作為 x、y 值的 80 和 114 得出因數：

: \gcd( 114-80, 1649 ) \cdot \gcd( 114+80, 1649 ) = 17 \cdot 97 = 1649.

參見

• 同餘關係