Fermat's factorization method: Difference between revisions

Revision as of 13:37, 18 February 2022

Revision as of 15:56, 18 February 2022

Line 139:

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.

A further modular improvement can be made by applying the division algorithm as an affine transformation, that is <math>X=\beta x+a</math>, <math>Y=\beta y+b</math>, <math>N=\beta z+r</math>, over any integer ring <math>\mathbb{Z}_\beta</math> where <math>\beta < X</math>. After a small amount of algebra, one can conclude that <math>\lfloor N/\beta^2 \rfloor-s=xy</math> and <math>\lfloor ab/\beta\rfloor=t</math> where s and t are identical to determining the carries one does in multiplying the divisors over base <math>\beta</math>.{{citation needed|date=January 2020}}

==Multiplier improvement==

Line 146 ⟶ 144:

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 the [[rational number]] <math>v/u</math> can be picked near that value. For example, if <math>Y/X \approx q</math>, then <math>X \approx \sqrt{N/q}</math> is a good estimate for the smaller of a divisor pair. <math>Nuv = cv \cdot du</math>, and the factors are roughly equal: Fermat's, applied to ''Nuv'', will find them quickly. Then <math>\gcd(N,cv)=c</math> and <math>\gcd(N,du)=d</math>. (Unless ''c'' divides ''u'' or ''d'' divides ''v''.)

A further generalization of this approach assumes that <math>Y^n/X^m \approx q</math>, meaning that <math>X \approx N^{m/(m+n)}/q^{1/(m+n)} </math>.

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 |author=Lehman, R. Sherman|title=Factoring Large Integers |journal=[[Mathematics of Computation]] |year=1974 |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 |doi=10.2307/2005940|doi-access=free }}</ref>