Fermat's factorization method: Difference between revisions

Revision as of 05:09, 9 February 2023

Revision as of 10:25, 6 May 2023

Line 147:

If the approximate ratio of two factors (<math>d/c</math>) is known, then a [[rational number]] <math>v/u</math> can be picked near that value. <math>Nuv = cv \cdot du</math>, and Fermat's method, applied to ''Nuv'', will find the factors <math>cv</math> and <math>du</math> quickly. Then <math>\gcd(N,cv)=c</math> and <math>\gcd(N,du)=d</math>. (Unless ''c'' divides ''u'' or ''d'' divides ''v''.)

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 |jstor=2005940 |doi-access=free }}</ref>

==Other improvements==

Line 171:

==References==

* {{ citation | last = Fermat | title = Oeuvres de Fermat | volume = 2 | page = 256 | year = 1894 }}

* {{ cite journal | last = McKee | first = J | journal = Mathematics of Computation | url = https://www.ams.org/mcom/1999-68-228/S0025-5718-99-01133-3/home.html | title = Speeding Fermat's factoring method | issue = 228 | pages = 1729–1737 | year = 1999 | volume = 68 | doi = 10.1090/S0025-5718-99-01133-3 | doi-access = free }}

==External links==