平方同馀

在数论中，平方同馀是个经常被用于整数分解演算法的同馀关系。

由来

给定一正整数 n，费马因式分解法想找到两数 x, y 满足下列方程式：

$x^{2}-y^{2}=n$

从上式我们便可以分解得 n = x² - y² = (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.$

参见

• 同馀关系