×

A Monte Carlo factoring algorithm with linear storage. (English) Zbl 0559.10004

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

MSC:

11A41 Primes
11E41 Class numbers of quadratic and Hermitian forms
68Q25 Analysis of algorithms and problem complexity
11R11 Quadratic extensions

Citations:

Zbl 0223.12006
PDFBibTeX XMLCite
Full Text: DOI