從平方差談起

平方差方法

我們常用的代數恆等式如：

平方差分解式， a²-b² = (a+b)(a-b)，也可在大數分解上幫忙。

若 n+b² = a² ，則有 n = (a+b)(a-b)。我們是可以利用這些方法來判定一數的素性和進行分解，特別是 n=ab 而 a 和 b 相當接近時。我們若用以往的判別法，自 1 而起，往往到最後才知是合數。但用平方差來分解，則快得多。

例 ：分解 8633

1. 我們先在 8633 之上找一平方數 8649 = 93²

2. 判斷 8649-8633=16 是不是平方數，若非再向上找下一個平方數來試。若是即

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

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

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

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

屆時便可斷定 p 是素數。

費馬方法

我們以為上述方法再判別大數的數性時，仍相當費時。故法國數學家費馬 (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.