digplanet beta 1: Athena
Share digplanet:

Agriculture

Applied sciences

Arts

Belief

Chronology

Culture

Education

Environment

Geography

Health

History

Humanities

Language

Law

Life

Mathematics

Nature

People

Politics

Science

Society

Technology

Fermat's factorization method, named after Pierre de Fermat, is based on the representation of an odd integer as the difference of two squares:

$N = a^2 - b^2.\$

That difference is algebraically 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 = [(c+d)/2]^2 - [(c-d)/2]^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.

## The basic method

One tries various values of a, hoping that $a^2-N = b^2$ is a square.

FermatFactor(N): // N should be odd
a ← ceil(sqrt(N))
b2 ← a*a - N
while b2 isn't a square:
a ← a + 1 // equivalently: b2 ← b2 + 2*a + 1
b2 ← a*a - N // a ← a + 1
endwhile
return a - sqrt(b2) // or a + sqrt(b2)

For example, to factor $N=5959$, our first try for a is the square root of $5959$ rounded up to the next integer which is $78$. Then, $b^2=78^2-5959$. Since b is not an integer, a second try is made by increasing the value of a by 1. The second attempt again fails because b is not an integer.

Try: 1 2 3
a: 78 79 80
b2: 125 282 441
b: 11.18 16.79 21

The third try produces a perfect square so b is an integer. So, $a=80$, $b=21$, and the factors of $5959$ 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 ${\left(4N\right)}^{1/4}$ from $\sqrt N$ the method requires only one step. Note, that this is independent of the size of N.

## Fermat's and trial division

Consider trying to factor the prime number N = 2345678917, but also compute b and ab throughout. Going up from $\sqrt{N}$, we can tabulate:

 a: 48433 48434 48435 48436 b2: 76572 173439 270308 367179 b: 276.7 416.5 519.9 605.9 a − b: 48156.3 48017.5 47915.1 47830.1

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 48432; 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{N}$; use Fermat for factors between $\sqrt{N}$ and $c$. This gives a bound for trial division which is $c - \sqrt{c^2 - N}$. 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:

 a: 60001 60002 b2: 1.25444e+09 1.25456e+09 b: 35418.1 35419.8 a − b: 24582.9 24582.2

## Sieve improvement

It is not necessary to compute all the square-roots of $a^2-N$, nor even examine all the values for $a$. Examine the tableau for $N=2345678917$:

 a: 48433 48434 48435 48436 b2: 76572 173439 270308 367179 b: 276.7 416.5 519.9 605.9

One can quickly tell that none of these values of b2 are squares. Squares end with 0, 1, 4, 5, 9, or 16 modulo 20. The values repeat with each increase of $a$ by 10. For this example, adding '-17' mod 20 (or 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 $a$ is 1 or 9 mod 10; it will produce a b2 which ends in 4 mod 20 and, if square, $b$ will end in 2 or 8 mod 10.

This can be performed with any modulus. Using the same $N=2345678917$,

 modulo 16: Squares are 0, 1, 4, or 9 N mod 16 is 5 so $a^2$ can only be 9 and $a$ must be 3 or 5 or 11 or 13 modulo 16 modulo 9: Squares are 0, 1, 4, or 7 N mod 9 is 7 so $a^2$ can only be 7 and $a$ must be 4 or 5 modulo 9

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:

FermatSieve(N, astart, aend, astep, modulus)
a ← astart
do modulus times:
b2 ← a*a - N
if b2 is a square, modulo modulus:
FermatSieve(N, a, aend, astep * modulus, NextModulus)
endif
a ← a + astep
enddo

But the recursion is stopped when few a-values remain; that is, when (aend-astart)/astep is small. Also, because a's 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. Perhaps it can be arranged for that to happen.

If the approximate ratio of two factors ($d/c$) is known, then the rational number $v/u$ can picked near that value. $Nuv = cv \cdot du$, and the factors are roughly equal: Fermat's, applied to Nuv, will find them 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^{1/3})$ time. See R. Lehman, "Factoring Large Integers", Mathematics of Computation, 28:637–646, 1974.

## Other improvements

The fundamental ideas of Fermat's factorization method are the basis of the quadratic sieve and general number field sieve, the best-known algorithms for factoring large semiprimes, 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.

## References

 151 videos foundNext >
 FamousMathProbs 1: Factoring large numbers into primesThis is the first video of a new series, which will discuss a wide variety of famous (and perhaps not so famous) mathematical problems, ranging from antiquit... Encryption and HUGE numbers - NumberphileBanks, Facebook, Twitter and Google use epic numbers - based on prime factors - to keep our Internet secrets. This is RSA public-key encryption. This video f... Fermat's Little Theorem (Visualization)Fermat's Little Theorem Visualized. Introduction to a key result in elementary number theory using a visualization with beads. Python: Fermat's Primality Test1) Fermat's Little Theorem 2) Fermat's Primality Test 3) Examples of Fermat's Little Theorem 4) Implementing Fermat's Primality Test in Python 5) Class home ... Prime Factorization Part 1 Algorithms - Number Theory - 02 - FactorizationContent Link: https://www.dropbox.com/s/2zaa81a6mhqbxcs/Algorithms_Number_Theory_02_Factorization.cpp Content: What is Factorization? Generating divisors Pri... Prime Factorization vs Factorizationhttp://www.timbedley.com Tim Bedley, veteran teacher, teaches this mini lesson on the difference between finding the PRIME factors for a given number and fin... Fermat's Little TheoremFermat's Little Theorem was observed by Fermat and proven by Euler, who generalized the theorem significantly. This theorem aids in dividing extremely large ... Factoring: The Sum of Two SquaresThe sum of two squares is a simple example of a polynomial that cannot be factored...over the integers. We review the concepts of prime and composite integer... Fermat's Little Theoremวรเศรษฐ สุวรรณิก http://wannik.wordpress.com.
 151 videos foundNext >

We're sorry, but there's no news about "Fermat's factorization method" right now.

 Limit to books that you can completely read online Include partial books (book previews) .gsc-branding { display:block; }

Oops, we seem to be having trouble contacting Twitter

# Talk About Fermat's factorization method

You can talk about Fermat's factorization method with people all over the world in our discussions.

#### Support Wikipedia

A portion of the proceeds from advertising on Digplanet goes to supporting Wikipedia. Please add your support for Wikipedia!