|
=== Premise ===
An optimal <math>a_{\mathrm{max}}</math> can be computed using derivative methods. This derivation assumes you didint use any seiving.
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 seving 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>
<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} +2dd\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} +2dd\left(1+\frac{1}{l}\right) - \sqrt{2\sqrt{N}d + d^2} = \frac{d}{dd} \sqrt{N} + \frac{d}{dd} 2dd\left(1+\frac{1}{l}\right) - \frac{d}{dd} \sqrt{2\sqrt{N}d + d^2} </math>
Notice theBecause <math>\sqrt{N}</math> term dosent depend on <math>d</math> sowe itscan derivativedrop respectthat toderivative d is 0term
Forfor the <math>2d </math> term we can use the constant multiple rule to get <math>\frac{d}{dd} 2d \to 2 left(1+\frac{d1}{ddl} d \right)</math> butterm, noticeuse the derivativemultiple ofrule <math>d</math> is just 1 so <math>2 \frac{d}{dd} d left(fg\to 2 right)'=f'g+g'f</math>.:
<math> C\left( -d\ sqrt{N} left(1+ \frac{ 2\sqrt{N}1}{ \sqrt{3l} },N\right) \right)' = \sqrt{N} +2d'\left( -\sqrt{N} 1+ \frac{ 2\sqrt{N}1}{ \sqrt{3}l}\right) - \sqrt{2\sqrt{N}+\left( -\sqrt{N} 1+ \frac{ 2\sqrt{N}1}{ \sqrt{3}l}\right) 'd += \left( -\sqrt{N} 1+ \frac{ 2\sqrt{N}1}{ \sqrt{3}l}\right) ^2}</math> Simplyfing▼For the last term <math>\sqrt{2\sqrt{N}d + d^2} </math> we use the chain rule:
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} \to \frac{\left(2\sqrt{N}d + d^2\right)^{-\frac{1}{2}}}{2}\frac{d}{dd}2\sqrt{N}d + d^2 </math> ▼
Use linearity on the term to get <math>\frac{d}{dd}\sqrt{2\sqrt{N}d + d^2} = \tofrac{\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}{dd2}}}{2} \left(2\sqrt{N} + 2d\right) = \left(2\sqrt{N}d + d^2\right)^{-\frac{1}{2}}\left(\sqrt{N} + d\right)</math>Substuting known 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>
For the first term, use the constant multiple rule and the power rule to get:
To find the minimum, notice at the minimum the derivative vanishes, so st the derivative to 0
<math>\frac{d}{dd}2\sqrt{N}d \to 2\sqrt{N}\frac{d}{dd}d \to 2\sqrt{N} </math> ▼
▲<math>\ frac{d}{dd}\sqrt{left(2\sqrt{N}d + d^2 } \ to right)^{-\frac{ 1}{2}}\left( 2\sqrt{N} d + d ^2\right) ^{- = 0 \to \frac{ 1}\sqrt{ 2}N} + d}{ 2}\ fracsqrt{ d}{dd}2\sqrt{N}d + d^2 }} = 1+\frac{1}{l}</math>
For the second term use the power rule: <math>\frac{d}{dd}d^2 = 2d </math>
Square both sudes to remvoe the root then cross multiply
So subsututing known derivatives we get
<math>\left(\frac{\sqrt{N} + d}{dd}\sqrt{2\sqrt{N}d + d^2}}\right)^2 = \left(1+\frac{d1}{ddl}d\right)^2 \to \frac{\left(\sqrt{N} + d\right)^2}{2\sqrt{N}d + 2dd^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>\frac{\left(2\sqrt{N}d + d^2\right)^{-\frac{1}{2}}}{2}\frac{d}{dd}2\sqrt{N}d + d^2 \to \frac{\left(2\sqrt{N}d + d^2\right)^{-\frac{1}{2}}}{2}2\left(\sqrt{N}+d\right) = \left(2\sqrt{N}d + d^2\right)^{-\frac{1}{2}}\left(\sqrt{N}+d\right)</math><math>\frac{d}{dd} \sqrt{N} + \frac{d}{dd} 2d - \frac{d}{dd} \sqrt{2\sqrt{N}d + d^2} = \frac{d}{dd} \sqrt{N} + \frac{d}{dd} 2d - \frac{d}{dd} \sqrt{2\sqrt{N}d + d^2} = 2 - \left(2\sqrt{N}d + d^2\right)^{-\frac{1}{2}}\left(\sqrt{N}+d\right) </math>Setting this to 0 gives you the optimal d
<math>\left(\sqrt{N} + d\right)^2 -= \left(2\sqrt{N}d + d^2\right)^{-\left(1+\frac{1}{2}l}\left(\sqrt{N}+d\right) = 0^2 \to \frac{\sqrt{N} +d}{\sqrt{ 2\sqrt{N}d+d^2}} = 2 \to left(2\sqrt{N}+d =+ d^2\sqrt{2right)\sqrtleft(1+\frac{N1}d+d{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
Eliminating the square root
<math>N + 2\sqrt{N}d+d^2 = 2 \sqrt{left(2\sqrt{N}d + d^2} \to right)\left(1+\sqrtfrac{N1}{l}+d\right)^2 \to N = 4\left(2\sqrt{N}d+d^2\right)\left[\left(1+\frac{1}{l}\right)^2-1\right] </math>
Simplify the bracket
Simplifying
<math> \left(1+\sqrtfrac{N1}{l}+d\right)^2-1 = 41^2 + 2\times1\times\frac{1}{l}+\left(2\sqrtfrac{N1}{l}d+d^2\right)^2 \to- 1 = \sqrtfrac{N}^2}{l}+2\sqrtfrac{N1}d+d{l^2} = 8\sqrtfrac{N}d2l+2d1}{l^2} </math>
So the equation is now
Subtract RHS from both sides and combining like terms
<math> \sqrt{N}^2+2\sqrt{N}d+d^2 = 8\sqrt{N}d+2d^2 \to N+left(2\sqrt{N}d+d^2 - 8\sqrtright)\frac{N2l+1}d+2d{l^2 = 0} \to N-6\sqrt{N}d-3dNl^2 = 0 \to 6left(2\sqrt{N}d+3dd^2-N = 0\right)\left(2l+1\right) </math>Apply the quadratic formula
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>d = \frac{-2\sqrt{N}\pm\sqrt{\left(2N\right)^2-4\times1\times\left(-\frac{N}{3}\right)}}{2} \to -\sqrt{N} \pm \frac{2\sqrt{N}}{\sqrt{3}}</math> ▼
<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> d > 0 </math> take the positive solution. ▼
Since <math>2l+1 \neq 0 </math>, you could divide through by it to get
Now get the optimal <math>a_{\mathrm{max}}</math> from the optimal <math>d</math>
<math>a_{\mathrm{max}}d^2 =+ 2\sqrt{N} + d \to \sqrt{N} + -\sqrt{N} + \frac{Nl^2\sqrt{N}}{\sqrt{3}2l+1} = \frac{2\sqrt{N}}{\sqrt{3}}0 </math>
This is the quadratic equation we been looking for, we can now apply the quardratic formula:
So under then permise of no seiving, optimally you should chose <math> \frac{2\sqrt{N}}{\sqrt{3}} </math>
▲<math>d = \frac{-2\sqrt{N}\pm\sqrt{\left( 2N2\sqrt{N}\right)^2-4\times1\times\left(-\frac{ NNl^2}{ 32l+1}\right)}}{2} \to -\sqrt{N} \pm \frac{2\sqrt{N} \frac{l+1}{\sqrt{ 32l+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_{\ fracmathrm{ dmax} {dd} 2 = \sqrt{N} + d \to 2\sqrt{N} + -\sqrt{N} + \sqrt{N}\frac{ dl+1}{ dd\sqrt{2l+1}} d \to= 2\sqrt{N} \frac{l+1}{\sqrt{2l+1}}</math>
=== Cost ===
SubstuteSubstude our optimal <math> -\sqrt{N} + \frac{2\sqrt{N}}{\sqrt{3}} d</math> forinto <math>C\left( d , N,l\right) </math> we get
<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 a equation, we get <math>\frac{\sqrt{N}\left(\sqrt{2l+1}-1\right)}{l}</math>.
=== Facts ===
▲<math>C\left(-\sqrt{N} + \frac{2\sqrt{N}}{\sqrt{3}},N\right) = \sqrt{N} +2\left(-\sqrt{N} + \frac{2\sqrt{N}}{\sqrt{3}}\right) - \sqrt{2\sqrt{N}\left(-\sqrt{N} + \frac{2\sqrt{N}}{\sqrt{3}}\right) + \left(-\sqrt{N} + \frac{2\sqrt{N}}{\sqrt{3}}\right)^2}</math>Simplyfing
* If <math>\sqrt{N}l +2\left(-\sqrt{N}= +1</math> \frac{2\sqrt{N}}{\sqrt{3}}\right)that -means \sqrtno sieving, <math>a_{2\sqrtmathrm{Nmax}\left(-\sqrt{N} += \frac{2\sqrt{N}}{\sqrt{3}}\right)</math> +and \left(-\sqrt{N}the +cost \frac{2\sqrt{N}}{\sqrt{3}}\right)^2} \tobecomes <math>\sqrt{N}\left(\sqrt{3}-1\right)</math>
</math>, which is still better than pure trial divison or pure fermat
=== Example ===
So using Fermat + Trial divison we get a cost of <math>\sqrt{N}\left(\sqrt{3}-1\right)</math> which is a imporvement over plain trial division
Using the same <math>N=2345678917</math>, if theres no sieving then you should choose <math>a_{\mathrm{max}}</math> around 55924.69838392813. If we are seiving 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>
==Multiplier improvement==
| 