平方同余

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

由来

给定一正整数 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.$

参见

• 同余关系