Content deleted Content added
m →Basic method: Small fix for the complexity argument. |
→Sieve improvement: Added quadratic residue link. Tags: Mobile edit Mobile app edit Android app edit App select source |
||
| (47 intermediate revisions by 28 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 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.
==Basic method==
Line 24 ⟶ 25:
'''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
{| class="wikitable" style="text-align:right;"
Line 40 ⟶ 41:
|}
The third try produces the perfect square of 441.
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.
Line 49 ⟶ 50:
==Fermat's and trial division==
Consider trying to factor the prime number {{nowrap|1=''N'' =
{| class="wikitable"
|-
! Try
| {{ordinal|1}} || {{ordinal|2}} || {{ordinal|3}} || {{ordinal|4}}
|-
! ''a''
Line 65 ⟶ 69:
|}
In practice, one wouldn't bother with that last row
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>
In this regard, Fermat's method gives diminishing returns. One would surely stop before this point:
Line 103 ⟶ 107:
|}
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>,
Line 140 ⟶ 144:
But the [[Recursion (computer science)|recursion]] is stopped when few ''a''-values remain; that is, when ({{Not a typo|aend-astart}})/{{Not a typo|astep}} is small. Also, because ''a'''s step-size is constant, one can compute successive b2's with additions.
== 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 the approximate ratio of two factors (<math>d/c</math>) is known, then a [[rational number]] <math>v/u</math> can be picked near that value. <math>Nuv = cv \cdot du</math>, and Fermat's method, applied to ''Nuv'', will find the factors <math>cv</math> and <math>du</math> quickly. Then <math>\gcd(N,cv)=c</math> and <math>\gcd(N,du)=d</math>. (Unless ''c'' divides ''u'' or ''d'' divides ''v''.)
Generally, if the ratio is not known, various <math>u/v</math> 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 <math>O(N^{1/3})</math> time.<ref>{{cite journal |last=Lehman |first=R. Sherman |year=1974 |title=Factoring Large Integers |journal=[[Mathematics of Computation]] |doi=10.2307/2005940 |doi-access=free |jstor=2005940 |volume=28 |issue=126 |pages=637–646 |url=https://www.ams.org/journals/mcom/1974-28-126/S0025-5718-1974-0340163-2/S0025-5718-1974-0340163-2.pdf}}</ref>
==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==
Line 182 ⟶ 262:
==References==
*
*
==External links==
*
*
{{number theoretic algorithms}}
| |||