HOME

TheInfoList



OR:

Fermat's factorization method, named after
Pierre de Fermat Pierre de Fermat (; between 31 October and 6 December 1607 – 12 January 1665) was a French mathematician who is given credit for early developments that led to infinitesimal calculus, including his technique of adequality. In particular, he ...
, is based on the representation of an
odd Odd means unpaired, occasional, strange or unusual, or a person who is viewed as eccentric. Odd may also refer to: Acronym * ODD (Text Encoding Initiative) ("One Document Does it all"), an abstracted literate-programming format for describing X ...
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
as the
difference of two squares In mathematics, the difference of two squares is a squared (multiplied by itself) number subtracted from another squared number. Every difference of squares may be factored according to the identity :a^2-b^2 = (a+b)(a-b) in elementary algebra. ...
: :N = a^2 - b^2. That difference is
algebra Algebra () is one of the broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathematics. Elementary a ...
ically factorable as (a+b)(a-b); if neither factor equals one, it is a proper factorization of ''N''. Each odd number has such a representation. Indeed, if N=cd is a factorization of ''N'', then :N = \left(\frac\right)^2 - \left(\frac\right)^2 Since ''N'' is odd, then ''c'' and ''d'' are also odd, so those halves are integers. (A multiple of four is also a difference of squares: let ''c'' and ''d'' be even.) In its simplest form, Fermat's method might be even slower than trial division (worst case). Nonetheless, the combination of trial division and Fermat's is more effective than either.


Basic method

One tries various values of ''a'', hoping that a^2-N = b^2, a square. FermatFactor(N): ''// N should be odd'' a ← b2 ← a*a - N repeat until b2 is a square: a ← a + 1 b2 ← a*a - N // equivalently: // b2 ← b2 + 2*a + 1'' // a ← a + 1 return a - ''// or a + '' For example, to factor N = 5959, the first try for ''a'' is the square root of rounded up to the next integer, which is . Then, b^2 = 78^2-5959 = 125. Since 125 is not a square, a second try is made by increasing the value of ''a'' by 1. The second attempt also fails, because 282 is again not a square. The third try produces the perfect square of 441. So, a = 80, b = 21, and the factors of are a - b = 59 and a + b = 101. Suppose N has more than two prime factors. That procedure first finds the factorization with the least values of ''a'' and ''b''. That is, a + b is the smallest factor ≥ the square-root of ''N'', and so a - b = N/(a + b) is the largest factor ≤ root-''N''. If the procedure finds N=1 \cdot N, that shows that ''N'' is prime. For N = cd, let ''c'' be the largest subroot factor. a = (c+d)/2, so the number of steps is approximately (c + d)/2 - \sqrt N = (\sqrt d - \sqrt c)^2 / 2 = (\sqrt N - c)^2 / 2c. If ''N'' is prime (so that c = 1), one needs O(N) steps. This is a bad way to prove primality. But if ''N'' has a factor close to its square root, the method works quickly. More precisely, if ''c'' differs less than ^ from \sqrt N, the method requires only one step; this is independent of the size of ''N''.


Fermat's and trial division

Consider trying to factor the prime number , but also compute ''b'' and throughout. Going up from \sqrt, we can tabulate: In practice, one wouldn't bother with that last row until ''b'' is an integer. But observe that if ''N'' had a subroot factor above a-b=47830.1, Fermat's method would have found it already. Trial division would normally try up to 48,432; but after only four Fermat steps, we need only divide up to 47830, to find a factor or prove primality. This all suggests a combined factoring method. Choose some bound c > \sqrt; use Fermat's method for factors between \sqrt and c. This gives a bound for trial division which is c - \sqrt. In the above example, with c = 48436 the bound for trial division is 47830. A reasonable choice could be c = 55000 giving a bound of 28937. In this regard, Fermat's method gives diminishing returns. One would surely stop before this point:


Sieve improvement

When considering the table for N=2345678917, one can quickly tell that none of the values of b^2 are squares: It is not necessary to compute all the square-roots of a^2-N, nor even examine all the values for . Squares are always congruent to 0, 1, 4, 5, 9, 16
modulo In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another (called the '' modulus'' of the operation). Given two positive numbers and , modulo (often abbreviated as ) is t ...
20. The values repeat with each increase of by 10. In this example, N is 17 mod 20, so subtracting 17 mod 20 (or adding 3), a^2-N produces 3, 4, 7, 8, 12, and 19 modulo 20 for these values. It is apparent that only the 4 from this list can be a square. Thus, a^2 must be 1 mod 20, which means that is 1, 9, 11 or 19 mod 20; it will produce a b^2 which ends in 4 mod 20 and, if square, will end in 2 or 8 mod 10. This can be performed with any modulus. Using the same N=2345678917, One generally chooses a power of a different prime for each modulus. Given a sequence of ''a''-values (start, end, and step) and a modulus, one can proceed thus: , astart, aend, astep, modulus) a ← astart do modulus times: b2 ← a*a - N if b2 is a square, modulo modulus: , a, aend, astep * modulus, NextModulus) endif a ← a + astep enddo But the
recursion Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
is stopped when few ''a''-values remain; that is, when ()/ is small. Also, because ''as step-size is constant, one can compute successive b2's with additions.


Multiplier improvement

Fermat's method works best when there is a factor near the square-root of ''N''. If the approximate ratio of two factors (d/c) is known, then a
rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ration ...
v/u can be picked near that value. Nuv = cv \cdot du, and Fermat's method, applied to ''Nuv'', will find the factors cv and du quickly. Then \gcd(N,cv)=c and \gcd(N,du)=d. (Unless ''c'' divides ''u'' or ''d'' divides ''v''.) Generally, if the ratio is not known, various u/v values can be tried, and try to factor each resulting ''Nuv''. R. Lehman devised a systematic way to do this, so that Fermat's plus trial division can factor N in O(N^) time.


Other improvements

The fundamental ideas of Fermat's factorization method are the basis of the
quadratic sieve The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). It is still the fastest for integers under 100 decimal digits or so, and is considerab ...
and
general number field sieve In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than . Heuristically, its complexity for factoring an integer (consisting of bits) is of the form :\exp\left( ...
, the best-known algorithms for factoring large
semiprimes In mathematics, a semiprime is a natural number that is the product of exactly two prime numbers. The two primes in the product may equal each other, so the semiprimes include the squares of prime numbers. Because there are infinitely many prime ...
, which are the "worst-case". The primary improvement that quadratic sieve makes over Fermat's factorization method is that instead of simply finding a square in the sequence of a^2 - n, it finds a subset of elements of this sequence whose ''product'' is a square, and it does this in a highly efficient manner. The end result is the same: a difference of square mod ''n'' that, if nontrivial, can be used to factor ''n''.


See also

*
Completing the square : In elementary algebra, completing the square is a technique for converting a quadratic polynomial of the form :ax^2 + bx + c to the form :a(x-h)^2 + k for some values of ''h'' and ''k''. In other words, completing the square places a perfe ...
*
Factorization of polynomials In mathematics and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field or in the integers as the product of irreducible factors with coefficients in the same dom ...
*
Factor theorem In algebra, the factor theorem is a theorem linking factors and zeros of a polynomial. It is a special case of the polynomial remainder theorem. The factor theorem states that a polynomial f(x) has a factor (x - \alpha) if and only if f(\alpha)=0 ...
*
FOIL rule In secondary school, ''FOIL'' is a mnemonic for the standard method of multiplying two binomials—hence the method may be referred to as the FOIL method. The word ''FOIL'' is an acronym for the four terms of the product: * First ("first" ...
*
Monoid factorisation In mathematics, a factorisation of a free monoid is a sequence of subsets of words with the property that every word in the free monoid can be written as a concatenation of elements drawn from the subsets. The Chen–Fox–Lyndon theorem states tha ...
*
Pascal's triangle In mathematics, Pascal's triangle is a triangular array of the binomial coefficients that arises in probability theory, combinatorics, and algebra. In much of the Western world, it is named after the French mathematician Blaise Pascal, although ot ...
*
Prime factor A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
*
Factorization In mathematics, factorization (or factorisation, see American and British English spelling differences#-ise, -ize (-isation, -ization), English spelling differences) or factoring consists of writing a number or another mathematical object as a p ...
*
Euler's factorization method Euler's factorization method is a technique for factoring a number by writing it as a sum of two squares in two different ways. For example the number 1000009 can be written as 1000^2 + 3^2 or as 972^2 + 235^2 and Euler's method gives the factoriza ...
*
Integer factorization In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization. When the numbers are suf ...
*
Program synthesis In computer science, program synthesis is the task to construct a program that provably satisfies a given high-level formal specification. In contrast to program verification, the program is to be constructed rather than given; however, both fields ...
*
Table of Gaussian integer factorizations A Gaussian integer is either the zero, one of the four units (±1, ±''i''), a Gaussian prime or composite. The article is a table of Gaussian Integers followed either by an explicit factorization or followed by the label (p) if the integer is a Ga ...
*
Unique factorization In mathematics, a unique factorization domain (UFD) (also sometimes called a factorial ring following the terminology of Bourbaki) is a ring in which a statement analogous to the fundamental theorem of arithmetic holds. Specifically, a UFD is a ...


Notes


References

* *


External links


Fermat's factorization running time
at blogspot.in
Fermat's Factorization Online Calculator
at windowspros.ru {{number theoretic algorithms Integer factorization algorithms