“Fermat's Factorization Method”的概念、定义、习题解题方法及翻译-数学辞典

单词

Fermat's Factorization Method

释义

Fermat's Factorization Method

Given a number , look for Integers and such that . Then

(1)

and

is factored. Any Odd Number can be represented in this form since then

and

are Odd, and

			(2)
			(3)

Adding and subtracting,

			(4)
			(5)

so solving for

and

gives

			(6)
			(7)

Therefore,

(8)

As the first trial for

, try

, where

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 canassume, so most combinations can be eliminated. If

is not a Square Number, then try

(10)


			(11)

Continue with


			(12)

so subsequent differences are obtained simply by adding two.

Maurice Kraitchik sped up the Algorithm by looking for and satisfying

(13)

i.e.,

. This congruence has uninteresting solutions

and interesting solutions

. It turns out that if

is Odd and Divisible by at least two differentPrimes, then at least half of the solutions to

with

Coprime to

are interesting. Forsuch solutions,

is neither

nor 1 and is therefore a nontrivial factor of

(Pomerance 1996). ThisAlgorithm can be used to prove primality, but is not practical. In 1931, Lehmer and Powers discovered how to searchfor 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 theQuadratic Sieve Factorization Method was developed.

See also Prime Factorization Algorithms, Smooth Number

References

Lehmer, D. H. and Powers, R. E. ``On Factoring Large Numbers.'' Bull. Amer. Math. Soc. 37, 770-776, 1931.

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.

随便看

数学辞典收录了8975条数学词条，基本涵盖了常用数学知识及数学英语单词词组的翻译及用法，是数学学习的有利工具。