Content deleted Content added
Captainfranz (talk | contribs) No edit summary |
→Sieve improvement: Added quadratic residue link. Tags: Mobile edit Mobile app edit Android app edit App select source |
||
| (196 intermediate revisions by more than 100 users not shown) | |||
Line 1:
{{Short description|Factorization method based on the difference of two squares}}{{For|Fermat's method on determining extreme values|Interior extremum theorem}}{{Refimprove|date=February 2022}}
'''Fermat's factorization method''', named after [[Pierre de Fermat]], is based on the representation of an [[even and odd numbers|odd]] [[integer]] as the [[difference of two squares]]:
:<math>N = a^2 - b^2.</math>
That difference is [[algebra]]ically factorable as <math>(a+b)(a-b)</math>; if neither factor equals one, it is a proper factorization of ''N''.
Each odd number has such a representation. Indeed, if <math>N=cd</math> is a factorization of ''N'', then
:<math>N =
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 by itself.
==
One tries various values of ''a'', hoping that <math>a^2-N = b^2</math>
a ← a + 1
// equivalently:
// a ← a + 1
'''return''' a - {{Not a typo|sqrt(b2)}} ''// or a + {{Not a typo|sqrt(b2)}}''
For example, to factor <math>N = 5959</math>, the first try for ''a'' is the square root of {{math|5959}} rounded up to the next integer, which is {{math|78}}. Then <math>b^2 = 78^2-5959 = 125</math>. 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.
{| class="wikitable" style="text-align:right;"
! Try:
| 1 || 2 || 3
|-
! ''a''
| 78 || 79 || 80
|-
! ''b''<sup>2</sup>
| 125 || 282 || 441
|-
! ''b''
| 11.18 || 16.79 || 21
|}
Suppose N has more than two prime factors. That procedure first finds the factorization with the least values of ''a'' and ''b''. That is, <math>a + b</math> is the smallest factor ≥ the square-root of ''N'', and so <math>a - b = N/(a + b)</math> is the largest factor ≤ root-''N''. If the procedure finds <math>N=1 \cdot N</math>, that shows that ''N'' is prime.
For <math>N = cd</math>, let ''c'' be the largest subroot factor. <math>a = (c+d)/2</math>, so the number of steps is approximately <math>(c + d)/2 - \sqrt N = (\sqrt d - \sqrt c)^2 / 2 = (\sqrt N - c)^2 / 2c</math>.
If ''N'' is prime (so that <math>c = 1</math>), one needs <math>O(N)</math> 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 <math>{\left(4N\right)}^{1/4}</math> from <math>\sqrt N</math>, the method requires only one step; this is independent of the size of ''N''.{{Citation needed|date=January 2015}}
==Fermat's and trial division==
Consider trying to factor the prime number {{nowrap|1=''N'' = 2,345,678,917}}, but also compute ''b'' and {{nowrap|''a'' − ''b''}} throughout. Going up from <math>\sqrt{N}</math> rounded up to the next integer, which is 48,433, we can tabulate:
{| class="wikitable"
|-
! Try
| {{ordinal|1}} || {{ordinal|2}} || {{ordinal|3}} || {{ordinal|4}}
|-
! ''a''
| 48,433 || 48,434 || 48,435 || 48,436
|-
! ''b''<sup>2</sup>
| 76,572 || 173,439 || 270,308 || 367,179
|-
! ''b''
| 276.7 || 416.5 || 519.9 || 605.9
|-
! ''a'' − ''b''
| 48,156.3 || 48,017.5 || 47,915.1 || 47,830.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 <math>a-b=47830.1</math>, 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 <math>a_{\mathrm{max}} > \sqrt{N}</math>; use Fermat's method for factors between <math>\sqrt{N}</math> and <math>a_{\mathrm{max}}</math>. This gives a bound for trial division which is <math>a_{\mathrm{max}} - \sqrt{a_{\mathrm{max}}^2 - N}</math>. In the above example, with <math>a_{\mathrm{max}} = 48436</math> the bound for trial division is 47830. A reasonable choice could be <math>a_{\mathrm{max}} = 55000</math> giving a bound of 28937.
In this regard, Fermat's method gives diminishing returns. One would surely stop before this point:
{| class="wikitable"
|-
! ''a''
|-
! ''b''<sup>2</sup>
| 1,254,441,084 || 1,254,561,087
|-
! ''b''
| 35,418.1 || 35,419.8
|-
! ''a'' − ''b''
| 24,582.9 || 24,582.2
|}
==Sieve improvement==
{| class="wikitable" style="text-align:right;"
|-
! ''a''
| 48,433 || 48,434 || 48,435 || 48,436
|-
! ''b''<sup>2</sup>
| 76,572 || 173,439 || 270,308 || 367,179
|-
! ''b''
| 276.7 || 416.5 || 519.9 || 605.9
|}
It is not necessary to compute all the square-roots of <math>a^2-N</math>, nor even examine all the values for {{mvar|a}}. Squares are always congruent to 0, 1, 4, 5, 9, 16 [[Modular arithmetic|modulo]] 20, because these are the [[quadratic residue]]s of 20. The values repeat with each increase of {{mvar|a}} by 10. In this example, N is 17 mod 20, so subtracting 17 mod 20 (or adding 3), <math>a^2-N</math> 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, <math>a^2</math> must be 1 mod 20, which means that {{mvar|a}} is 1, 9, 11 or 19 mod 20; it will produce a <math>b^2</math> which ends in 4 mod 20 and, if square, {{mvar|b}} will end in 2 or 8 mod 10.
This can be performed with any modulus. Using the same <math>N=2345678917</math>,
{|
|-
|modulo 16:||Squares are ||0, 1, 4, or 9
|-
| ||N mod 16 is||5
|-
|-
|-
|modulo 9: ||Squares are ||0, 1, 4, or 7
|-
| ||N mod 9 is||7
|-
| ||so <math>a^2</math> can only be||7
|-
| ||and {{mvar|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:
a ← astart
b2 ← a*a - N
a ← a + astep
But
== Optimal <math>a_{\mathrm{max}}</math> ==
=== Premise ===
An optimal <math>a_{\mathrm{max}}</math> can be computed using derivative methods.
The cost of executing Fermat’s method from <math>\sqrt{N}</math> up to <math>a_{\mathrm{max}}</math> is roughly proportional to a constant we will call <math>d</math>. Using sieving we can reduce it by some constant we call <math>l</math>. In the combined method the trial division bound becomes <math>a_{\mathrm{max}} - \sqrt{a_{\mathrm{max}}^2 - N}</math>. Writing <math>a_{\mathrm{max}} = \sqrt{N} + d</math>, one gets:
<math>a^2_{\mathrm{max}} - N = (\sqrt{N} + d)^2 - N = \sqrt{N}^2 + 2\sqrt{N}d + d^2 - N = 2\sqrt{N}d + d^2</math>
Substitute the new formula, we get
<math>a_{\mathrm{max}} - \sqrt{a_{\mathrm{max}}^2 - N} \to a_{\mathrm{max}} - \sqrt{2\sqrt{N}d + d^2} </math>
The goal is to choose a <math>a_{\mathrm{max}}</math> such that <math>C\left(d,N,l\right) = \frac{d}{l} + \left(a_{\mathrm{max}} - \sqrt{2\sqrt{N}d + d^2}\right) \to d\frac{1}{l}+ \left(\sqrt{N}+d\right) - \sqrt{2\sqrt{N}d + d^2} = \sqrt{N} +d\left(1+\frac{1}{l}\right) - \sqrt{2\sqrt{N}d + d^2}</math> is minimized.
=== Finding the Optimum ===
[[Derivative|Differentiate]] <math>C\left( d , N,l\right) </math> with respect to <math>d</math>. Due to the linearity of derivatives
<math>\frac{d}{dd}\sqrt{N} +d\left(1+\frac{1}{l}\right) - \sqrt{2\sqrt{N}d + d^2} = \frac{d}{dd}\sqrt{N} +\frac{d}{dd}d\left(1+\frac{1}{l}\right) - \frac{d}{dd}\sqrt{2\sqrt{N}d + d^2}</math>
Because <math>\sqrt{N}</math> doesn't depend on <math>d</math> we can drop that derivative term
for the <math>d\left(1+\frac{1}{l}\right)</math> term, use the multiple rule <math>\left(fg\right)'=f'g+g'f</math>:
<math>\left(d\left(1+\frac{1}{l}\right)\right)' = d'\left(1+\frac{1}{l}\right)+\left(1+\frac{1}{l}\right)'d = \left(1+\frac{1}{l}\right)</math>
For the last term, we use the chain rule <math>\left(f\left(g\right)\right)' = f'\left(g\right)g'</math> and the power rule <math>x^n = nx^{n-1}</math>
<math>\frac{d}{dd}\sqrt{2\sqrt{N}d + d^2} = \frac{\left(2\sqrt{N}d + d^2\right)^{-\frac{1}{2}}}{2} \frac{d}{dd}2\sqrt{N}d + d^2 = \frac{\left(2\sqrt{N}d + d^2\right)^{-\frac{1}{2}}}{2} \left(2\sqrt{N} + 2d\right) = \left(2\sqrt{N}d + d^2\right)^{-\frac{1}{2}}\left(\sqrt{N} + d\right)</math>Substitute the known derivate formulas
<math>\frac{d}{dd}\sqrt{N} +\frac{d}{dd}d\left(1+\frac{1}{l}\right) - \frac{d}{dd}\sqrt{2\sqrt{N}d + d^2} = \left(1+\frac{1}{l}\right) - \left(2\sqrt{N}d + d^2\right)^{-\frac{1}{2}}\left(\sqrt{N} + d\right) </math>
To find the minimum, notice at the minimum the derivative vanishes, so st the derivative to 0
<math>\left(2\sqrt{N}d + d^2\right)^{-\frac{1}{2}}\left(\sqrt{N} + d\right) = 0 \to \frac{\sqrt{N} + d}{\sqrt{2\sqrt{N}d + d^2}} = 1+\frac{1}{l}</math>
Square both sides to remove the root then cross multiply
<math>\left(\frac{\sqrt{N} + d}{\sqrt{2\sqrt{N}d + d^2}}\right)^2 = \left(1+\frac{1}{l}\right)^2 \to \frac{\left(\sqrt{N} + d\right)^2}{2\sqrt{N}d + d^2} = \left(1+\frac{1}{l}\right)^2 \to \left(\sqrt{N} + d\right)^2 = \left(2\sqrt{N}d + d^2\right)\left(1+\frac{1}{l}\right)^2</math>
Expand LHS
<math>\left(\sqrt{N} + d\right)^2 = \left(2\sqrt{N}d + d^2\right)\left(1+\frac{1}{l}\right)^2 \to N + 2\sqrt{N}d+d^2 = \left(2\sqrt{N}d + d^2\right)\left(1+\frac{1}{l}\right)^2 </math>
Bring the right side to the left, Factor the common factor, Then, bring the second term to the right-hand side
<math>N + 2\sqrt{N}d+d^2 = \left(2\sqrt{N}d + d^2\right)\left(1+\frac{1}{l}\right)^2 \to N = \left(2\sqrt{N}d+d^2\right)\left[\left(1+\frac{1}{l}\right)^2-1\right] </math>
Simplify the bracket
<math>\left(1+\frac{1}{l}\right)^2-1 = 1^2 + 2\times1\times\frac{1}{l}+\left(\frac{1}{l}\right)^2 - 1 = \frac{2}{l}+\frac{1}{l^2} = \frac{2l+1}{l^2} </math>
So, the equation is now
<math>N = \left(2\sqrt{N}d+d^2\right)\frac{2l+1}{l^2} \to Nl^2 = \left(2\sqrt{N}d+d^2\right)\left(2l+1\right) </math>
To apply the quadratic formula to solve <math>d</math> we have to rewrite the equation to a quadratic. Write the right side as:
<math>\left(2\sqrt{N}d+d^2\right)\left(2l+1\right) \to \left(2l+1\right)2\sqrt{N}d+\left(2l+1\right)d^2 </math>
Since <math>2l+1 \neq 0 </math>, you could divide through by it to get
<math>d^2 + 2\sqrt{N}d - \frac{Nl^2}{2l+1} = 0 </math>
This is the quadratic equation we been looking for, we can now apply the quardratic formula:
<math>d=\frac{-2\sqrt{N}\pm\sqrt{\left(2\sqrt{N}\right)^2-4\times1\times\left(-\frac{Nl^2}{2l+1}\right)}}{2} \to -\sqrt{N} \pm \sqrt{N}\frac{l+1}{\sqrt{2l+1}} </math>
Since <math>d>0</math> we take the positive solution. Since <math>a_{\mathrm{max}} = \sqrt{N} + d</math> one gets:
<math>a_{\mathrm{max}} = \sqrt{N} + d \to \sqrt{N} + -\sqrt{N} + \sqrt{N}\frac{l+1}{\sqrt{2l+1}} = \sqrt{N}\frac{l+1}{\sqrt{2l+1}}</math>
=== Cost ===
Substitute our optimal <math>d</math> into <math>C\left( d , N,l\right) </math>
<math>\sqrt{N} +d\left(1+\frac{1}{l}\right) - \sqrt{2\sqrt{N}d + d^2} \to \sqrt{N} +\left(-\sqrt{N} + \sqrt{N}\frac{l+1}{\sqrt{2l+1}}\right)\left(1+\frac{1}{l}\right) - \sqrt{2\sqrt{N}\left(-\sqrt{N} + \sqrt{N}\frac{l+1}{\sqrt{2l+1}}\right) + \left(-\sqrt{N} + \sqrt{N}\frac{l+1}{\sqrt{2l+1}}\right)^2} </math>
Simplifying the monster of an equation, we get <math>\frac{\sqrt{N}\left(\sqrt{2l+1}-1\right)}{l}</math>.
=== Facts ===
* If <math>l = 1</math> that means no sieving, <math>a_{\mathrm{max}} = \frac{2\sqrt{N}}{3}</math> and the cost becomes <math>\sqrt{N}\left(\sqrt{3}-1\right)
</math>, which is still better than pure trial division or pure Fermat
* The <math>a_{\mathrm{max}} - \sqrt{a_{\mathrm{max}}^2 - N}</math> which is the trial division bound becomes <math>\frac{\sqrt{N}}{\sqrt{2l+1}}</math> when subsututing the optimal.
=== Example ===
Using the same <math>N=2345678917</math>, if there's no sieving then you should choose <math>a_{\mathrm{max}}</math> around 55924.69838392813, the reasonable choice <math>a_{\mathrm{max}} = 55000</math> is not that far off from the optimal with a bound of 28937, but the optimal choice gets a bound of 27962. If we are sieving modulo 20, then <math>l = \frac{1}{\frac{4}{20}} = 5</math> and you should choose around <math>\sqrt{2345678917}\frac{6}{\sqrt{11}} \approx 87617.1636423325</math> and this should intuitively make sense. If the Fermat part costs less, the spend more time in the Fermat part to lower <math>a_{\mathrm{max}} - \sqrt{a_{\mathrm{max}}^2 - N}</math>
==Multiplier improvement==
Fermat's method works best when there is a factor near the square-root of ''N''
If
Generally,
==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 <math>a^2 - n</math>, 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 squares mod ''n'' that, if nontrivial, can be used to factor ''n''.
==See also==
*[[Completing the square]]
*[[Factorization of polynomials]]
*[[Factor theorem]]
*[[FOIL rule]]
*[[Monoid factorisation]]
*[[Pascal's triangle]]
*[[Prime factor]]
*[[Factorization]]
*[[Euler's factorization method]]
*[[Integer factorization]]
*[[Program synthesis]]
*[[Table of Gaussian integer factorizations]]
*[[Unique factorization ___domain|Unique factorization]]
==Notes==
{{reflist}}
==References==
*{{citation |last=Fermat |year=1894|title=Oeuvres de Fermat |volume=2 |page=256}}
*{{cite journal |last=McKee |first=J |year=1999 |title=Speeding Fermat's factoring method |journal=Mathematics of Computation |doi=10.1090/S0025-5718-99-01133-3 |doi-access=free |volume=68 |issue=228 |pages=1729–1737 |url=https://www.ams.org/mcom/1999-68-228/S0025-5718-99-01133-3/home.html}}
==External links==
*[http://kadinumberprops.blogspot.in/2012/11/fermats-factorization-running-time.html Fermat's factorization running time], at blogspot.in
*[https://windowspros.ru/projects/fermat-factorization-online-calculator/ Fermat's Factorization Online Calculator], at windowspros.ru
{{number theoretic algorithms}}
[[Category:Integer factorization algorithms]]
| |||