主题
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 改进为连分数分解算法，这是在二次筛法分解方法开发之前使用的最快算法。

另请参阅

质因数分解算法, 光滑数

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 上被引用

费马分解法

引用为

Weisstein, Eric W. "费马分解法。" 来自 MathWorld——Wolfram 网络资源。 https://mathworld.net.cn/FermatsFactorizationMethod.html

主题分类