|
|
|
|
Fermat method
|
(Algorithm)
|
|
|
The Fermat method is a factorization algorithm for odd integers that tries to represent them as the difference of two square numbers.
Call the Fermat method algorithm with an integer $n = 2x + 1$ .
- Initialize the iterator $i = \lceil \sqrt{n} \rceil$ and test cap at $\sqrt{i^2 - n}$ .
- Compute $j = \sqrt{i^2 - n}$ .
- Test if $j$ is an integer. If it is, break out of subroutine and return $i - j$ .
- Increment iterator $i$ once. If $i < \frac{n + 9}{6}$ , go to step 2.
- Return $n$ .
For example, $n = 221$ . The square root is approximately 15, so that's what we set our iterator's initial state to. The test cap is 39.
At $i = 15$ , we find that $\sqrt{15^2 - 221} = 2$ , clearly an integer.
Then, $15 - 2 = 13$ and $15 + 2 = 17$ . By multiplication, we verify that $221 = 13 \cdot 17$ , indeed. By trial division, this would have taken 15 test divisions.
However, there are integers for which trial division performs much better than the Fermat method, such as numbers of the form $3p$ where $p$ is an odd prime greater than 3.
- 1
- R. Crandall & C. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001: 5.1
|
"Fermat method" is owned by PrimeFan.
|
|
(view preamble | get metadata)
| Other names: |
Fermat's method, Fermat factorization method, Fermat's factorization method |
This object's parent.
|
|
Cross-references: prime, odd, divisions, trial division, multiplication, square root, iterator, integer, numbers, square, difference, represent, odd integers, algorithm
There are 4 references to this entry.
This is version 3 of Fermat method, born on 2007-02-01, modified 2007-02-22.
Object id is 8855, canonical name is FermatMethod.
Accessed 4043 times total.
Classification:
| AMS MSC: | 11A41 (Number theory :: Elementary number theory :: Primes) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|