主題
Search

費馬分解法

給定一個數 n，費馬分解法尋找整數 x 和 y 使得 n=x^2-y^2。那麼

n=(x-y)(x+y)
(1)

並且 n 被分解。對此觀察的修改形式導致了 Dixon 分解法 和 二次篩法。

每個正奇數都可以表示成 n=x^2-y^2 的形式，透過寫作 n=ab （其中 a>b）並注意到這給出了

a=x+y
(2)
b=x-y.
(3)

加法和減法，

a+b=2x
(4)
a-b=2y,
(5)

因此求解 x 和 y 得到

x=1/2(a+b)
(6)
y=1/2(a-b).
(7)

因此，

x^2-y^2=1/4[(a+b)^2-(a-b)^2]=ab.
(8)

作為 x 的第一次嘗試，嘗試 x_1=[sqrt(n)]，其中 [x] 是上限函式。然後檢查是否

Deltax_1=x_1^2-n
(9)

是一個平方數。僅有最後兩位數字的 22 種組合可以是平方數，因此可以排除大多數組合。如果 Deltax_1 不是一個平方數，那麼嘗試

x_2=x_1+1,
(10)

所以

Deltax_2=x_2^2-n
(11)
=(x_1+1)^2-n
(12)
=x_1^2+2x_1+1-n
(13)
=Deltax_1+2x_1+1.
(14)

繼續

Deltax_3=x_3^2-n
(15)
=(x_2+1)^2-n
(16)
=x_2^2+2x_2+1-n
(17)
=Deltax_2+2x_2+1
(18)
=Deltax_2+2x_1+3,
(19)

因此隨後的差值可以透過簡單地加二獲得。

Maurice Kraitchik 透過尋找滿足以下條件的 x 和 y 加速了演算法

x^2=y^2 (mod n),
(20)

即，n|(x^2-y^2)。這個同餘式有不有趣的解 x=+/-y (mod n) 和有趣的解 x≢+/-y (mod n)。結果表明，如果 n 是奇數且可被至少兩個不同的素數整除，那麼至少一半的 x^2=y^2 (mod n) 的解（其中 xy 與 n 互質）是有趣的。對於這樣的解，(n,x-y) 既不是 n 也不是 1，因此是的 n 一個非平凡因子 (Pomerance 1996)。這個演算法可以用來證明素性，但並不實用。1931 年，Lehmer 和 Powers 發現瞭如何使用連分數搜尋這樣的對。這種方法在 1975 年被 Morrison 和 Brillhart 改進為連分數分解演算法，這是在二次篩法分解方法開發之前使用的最快演算法。

另請參閱

質因數分解演算法, 光滑數

使用 探索

參考文獻

Lehmer, D. H. and Powers, R. E. "On Factoring Large Numbers." Bull. Amer. Math. Soc. 37, 770-776, 1931.McKee, J. "Speeding Fermat's Factoring Method." Math. Comput. 68, 1729-1738, 1999.Morrison, M. A. and Brillhart, J. "A Method of Factoring and the Factorization of F_7." Math. Comput. 29, 183-205, 1975.Pomerance, C. "A Tale of Two Sieves." Not. Amer. Math. Soc. 43, 1473-1485, 1996.

在 上被引用

費馬分解法

引用為

Weisstein, Eric W. "費馬分解法。" 來自 ——Wolfram 網路資源。 https://mathworld.tw/FermatsFactorizationMethod.html

主題分類