Fermat,s Factorization Method
المؤلف:
Lehmer, D. H. and Powers, R. E.
المصدر:
"On Factoring Large Numbers." Bull. Amer. Math. Soc. 37
الجزء والصفحة:
...
13-9-2020
1055
Fermat's Factorization Method
Given a number 
, Fermat's factorization methods look for integers 
and 
such that 
. Then
 |
(1)
|
and 
is factored. A modified form of this observation leads to Dixon's factorization method and the quadratic sieve.
Every positive odd integer can be represented in the form 
by writing 
(with 
) and noting that this gives
Adding and subtracting,
so solving for 
and 
gives
Therefore,
![x^2-y^2=1/4[(a+b)^2-(a-b)^2]=ab.](https://mathworld.wolfram.com/images/equations/FermatsFactorizationMethod/NumberedEquation2.gif) |
(8)
|
As the first trial for 
, try ![x_1=[sqrt(n)]](https://mathworld.wolfram.com/images/equations/FermatsFactorizationMethod/Inline30.gif)
, where ![[x]](https://mathworld.wolfram.com/images/equations/FermatsFactorizationMethod/Inline31.gif)
is the ceiling function. Then check if
 |
(9)
|
is a square number. There are only 22 combinations of the last two digits which a square number can assume, so most combinations can be eliminated. If 
is not a square number, then try
 |
(10)
|
so
Continue with
so subsequent differences are obtained simply by adding two.
Maurice Kraitchik sped up the algorithm by looking for 
and 
satisfying
 |
(20)
|
i.e., 
. This congruence has uninteresting solutions 
and interesting solutions 
. It turns out that if 
is odd and divisible by at least two different primes, then at least half of the solutions to 
with 
relatively prime to 
are interesting. For such solutions, 
is neither 
nor 1 and is therefore a nontrivial factor of 
(Pomerance 1996). This algorithm can be used to prove primality, but is not practical. In 1931, Lehmer and Powers discovered how to search for such pairs using continued fractions. This method was improved by Morrison and Brillhart (1975) into the continued fraction factorization algorithm, which was the fastest algorithm in use before the quadratic sieve factorization method was developed.
REFERENCES:
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 
." Math. Comput. 29, 183-205, 1975.
Pomerance, C. "A Tale of Two Sieves." Not. Amer. Math. Soc. 43, 1473-1485, 1996.
الاكثر قراءة في نظرية الاعداد
اخر الاخبار
اخبار العتبة العباسية المقدسة
