Schnorr, C. P.; Lenstra, H. W. jun. A Monte Carlo factoring algorithm with linear storage. (English) Zbl 0559.10004 Math. Comput. 43, 289-311 (1984). The authors present a variation of the Shanks algorithm [see D. Shanks, Proc. Symp. Pure Math. 20, 415-440 (1971; Zbl 0223.12006)] for factoring n by constructing ambiguous forms of distriminant \(d=-n\) or - 4n. The running time T(n) is proportional to the number of compositions in the class group of discriminant d which are required. It satisfies \(prob[T(m)<n^{1/2r}]\gtrsim (r-2)^{-(r-2)}\) for random m in [n/2,n]. A further analysis is made for the effectiveness of the algorithm with accompanying tables. The storage is linear. Reviewer: Harvey Cohn Cited in 1 ReviewCited in 20 Documents MSC: 11A41 Primes 11E41 Class numbers of quadratic and Hermitian forms 68Q25 Analysis of algorithms and problem complexity 11R11 Quadratic extensions Keywords:factorization; Shanks algorithm; ambiguous forms; running time; class group; effectiveness Citations:Zbl 0223.12006 PDFBibTeX XMLCite \textit{C. P. Schnorr} and \textit{H. W. Lenstra jun.}, Math. Comput. 43, 289--311 (1984; Zbl 0559.10004) Full Text: DOI