查看“︁平方同餘”︁的源代码

{{unreferenced|time=2019-03-22T13:25:03+00:00}}
在[[数论|數論]]中，'''平方同餘'''是個經常被用於[[整数分解|整數分解]]演算法的[[同餘關係]]。

== 由來 ==
給定一正[[整數]] ''n''，[[Fermat's factorization method|費馬因式分解法]]想找到兩數 ''x'', ''y'' 滿足下列[[方程|方程式]]：

: <math>x^2-y^2=n</math>

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

: <math>x^2 \equiv y^2 \pmod{n}</math>
: <math>x \not\equiv \pm y \pmod{n}</math>

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

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

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

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

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

== 例子 ==

=== 分解 35 ===
我們取 '''''n'' = 35''' 並得： 

: <math>6^2 = 36 \equiv 1 \equiv 1^2 \pmod{35}</math>

因此分解成：

: <math> \gcd( 6-1, 35 ) \cdot \gcd( 6+1, 35 ) = 5 \cdot 7 = 35</math>

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

: <math> 41^2 \equiv 32 \pmod{1649}</math>
: <math> 42^2 \equiv 115 \pmod{1649}</math>
: <math> 43^2 \equiv 200 \pmod{1649}</math>

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

: <math> 32 = 2^5</math>
: <math> 200 = 2^3 \cdot 5^2</math>

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

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

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

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

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

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

== 參見 ==

* [[同餘關係]]

[[Category:等价]]
[[Category:整数分解算法]]
[[Category:同余]]
[[Category:数论中的平方]]