從平方差談起

平方差方法

我們常用的恆等式如：

平方差恆等式 (Difference-of-square Identity)， a²-b² = (a+b)(a-b)，也可在大數分解 (Factorization) 上幫忙。

若 n+b² = a² ，則有 n = a²-b² = (a+b)(a-b)。我們是可以利用這些方法來判定一數的素性 (Primality) 和進行分解，特別是 n=ab 而 a 和 b 相當接近時。

例 ：分解 8633

我們先在 8633 之上 加上 1，即 8634 ，看看這是否平方數 (Square Number)。答案否定。這樣便把加上的數換上另一個平方數，即 8633 + 4 = 8637，又看看此數是否平方數。若非便再向換上另一個平方數。

直至得到的總和是一個平方數為止。最終我們有，8633 + 16 = 8649 = 93² 。若是即

8633 = 8649 -16 = 93² - 4² = (93+4)(93-4) = 97 * 89

這方法一直找下去是一定會找到符合條件的平方數的，

因為，若該數是素數  p ，p = 1*p 即 a + b = p 及 a - b = 1。

a=(p+1)/2 及 b= (p-1)/2

屆時便可斷定 p 是素數。

這樣兩個因子 (Factor) 可再以同樣的方法進行分解，直至全為素數為止。

這方法和試除法 (Trial Division) 相比，最大好處是不用以較小的素數作計算工具，但心算起來不太方便：一是因為計算過程較試除法為複雜，二是我們不大熟知平方數的數值。但這些在程式計算也不算什麼一回事。 但這方法亦有缺點：一是其只適用於 a 、 b 均為整數的情況，即兩因子奇偶性 (Parity) 相同的情況：換句話說，分解奇數問題不大，但分解偶數則行不得了。二是分解以後，各因子還得判定素性，不像試除法那樣，分解出來的定是素數。

費馬方法

我們以為上述方法再判別大數的數性時，仍相當費時。故法國數學家費馬 (Pierre de Fermat 1601-1665) 作出下面的修訂，因而得稱費馬方法 (Fermat's Method) 或費馬分解方法 (Fermat's Factorization Method) ：

因 n+b² 為平方數，則必有 x 使 b 的奇因子 p 滿足下式，

x²=n (mod p) ；即 x² 與 n 在模 p 下同餘，意思指 x² 和 n 在除以 p 時，餘數相同。

這我們稱 n為模 p 的二次剩餘 (Quadratic Residue)，即 (n/p) = 1，當中 (*) 為勒讓德符號 (Legendre Symbol)，式中的 (n/p) = n^(p-1)/2 (mod p) ，若 p 為素數且 n 和 p 互素 (Coprime)；

反之，沒有數 x 使 x²=n (mod p)，這我們稱 n為模 p 的二次非剩餘 (Quadratic Non-residue)，記成 (n/p) 則不等於 1了。

所以我們只要測試使 (n/p) = 1 的素因子 p 和其乘積便可，大大減少了測試的數目。

參考文獻及網址：

Weisstein, E. W. "Fermat's Factorization Method." From MathWorld. http://mathworld.wolfram.com/FermatsFactorizationMethod.html.