Shanks's square forms factorization: Difference between revisions

Revision as of 21:30, 3 December 2023

Latest revision as of 23:04, 26 August 2025

(2 intermediate revisions by 2 users not shown)

Line 1:

{{Short description|Integer factorization algorithm}}

{{more footnotes|date=March 2015}}

'''Shanks's square forms factorization''' is a method for [[integer factorization]] devised by [[Daniel Shanks]] as an improvement on [[Fermat's factorization method]].

The success of Fermat's method depends on finding integers <math>x</math> and <math>y</math> such that <math>x^2-y^2=N</math>, where <math>N</math> is the integer to be factored. An improvement (noticed by [[Maurice Kraitchik|Kraitchik]]) is to look for integers <math>x</math> and <math>y</math> such that <math>x^2\equiv y^2\pmod{N}</math>. Finding a suitable pair <math>(x, y)</math> does not guarantee a factorization of <math>N</math>, but it implies that <math>N</math> is a factor of <math>x^2-y^2=(x-y)(x+y)</math>, and there is a good chance that the [[prime divisor]]s of <math>N</math> are distributed between these two factors, so that calculation of the [[greatest common divisor]] of <math>N</math> and <math>x-y</math> will give a non-trivial factor of <math>N</math>.

Line 42 ⟶ 43:

Then if <math>f=\gcd(N,P_i)</math> is not equal to <math>1</math> and not equal to <math>N</math>, then <math>f</math> is a non-trivial factor of <math>N</math>. Otherwise try another value of <math>k</math>.{{cn|date=October 2023}}

Shanks's method has time complexity <math>O(\sqrt[4]{N})</math>.<ref>{{Harvcol|Riesel|1994|p=189}}</ref>

Stephen S. McMath wrote

a more detailed discussion of the mathematics of Shanks's method,

together with a proof of its correctness.<ref>{{Cite CiteSeerX|title=Daniel Shanks' Square Forms Factorization| year=2004 |citeseerx = 10.1.1.107.9984}}</ref>

Line 211 ⟶ 212:

* {{cite book

| last=Riesel | first=Hans | authorlink=Hans Riesel

| title=Prime Numbers and VomputerComputer Methods for Factorization

| publisher=Birkhauser

|edition = 2nd