Content deleted Content added
Ltypestar2 (talk | contribs) mNo edit summary |
Ltypestar2 (talk | contribs) mNo edit summary |
||
Line 227:
* 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 divison 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 theres 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 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> and ths should intuitvly 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==
| |||