Content deleted Content added
→Sieve improvement: Added quadratic residue link. Tags: Mobile edit Mobile app edit Android app edit App select source |
|||
| (227 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 = \left(\frac{c+d}{2}\right)^2 - \left(\frac{c-d}{2}\right)^2.</math>
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
==
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''
| 60,001 || 60,002
|-
! ''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
|-
| ||so <math>a^2</math> can only be||9
|-
| ||and {{mvar|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 <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
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]]
| |||