Fermat's factorization method: Difference between revisions

Revision as of 04:09, 13 June 2025

Latest revision as of 18:33, 28 August 2025

(2 intermediate revisions by one other user not shown)

Line 1:

{{Short description|MathematicsFactorization equationmethod 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>

Line 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 149:

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 sevingsieving 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>

subsututingSubstitute 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>

Line 164:

<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> dosentdoesn'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>:

Line 172:

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>SubstutingSubstitute 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>

Line 180:

<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 sudessides to remvoeremove 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>

Line 196:

<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>

Line 217:

=== Cost ===

SubstudeSubstitute 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 aan 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 divisondivision or pure fermatFermat

* 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 theresthere'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 seivingsieving 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 thsthis should intuitvlyintuitively make sense. If the fermatFermat part costs less, the spend more time in the fermatFermat part to lower <math>a_{\mathrm{max}} - \sqrt{a_{\mathrm{max}}^2 - N}</math>

==Multiplier improvement==