Fermat's factorization method: Difference between revisions

Revision as of 10:27, 6 May 2023

Revision as of 19:12, 30 July 2023

Line 70:

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>ca_{\mathrm{max}} > \sqrt{N}</math>; use Fermat's method for factors between <math>\sqrt{N}</math> and <math>c</math>. This gives a bound for trial division which is <math>ca_{\mathrm{max}} - \sqrt{ca_{\mathrm{max}}^2 - N}</math>. In the above example, with <math>ca_{\mathrm{max}} = 48436</math> the bound for trial division is 47830. A reasonable choice could be <math>ca_{\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: