A new factorization technique using quadratic forms
Derrick Henry Lehmer, Emma T. Lehmer · Mathematics of Computation · 1974
The paper presents a practical method for factoring an arbitrary N by representing N or λ N \lambda N by one of at most three quadratic forms: λ N = x 2 − D y 2 , λ = 1 , − 1 , 2 , D = − 1 , ± 2 , ± 3 , ± 6 \lambda N = {x^2} - D{y^2},\lambda = 1, - 1,2,D = - 1, \pm 2, \pm 3, \pm 6 . These three forms appropriate to N , together with inequalities for y , are given for all N prime to 6. Presently available sieving facilities make the method quite effective and economical for numbers N having 20 to 25 digits. Four examples arising from aliquot series are discussed in detail.