On the parallel generation of the residues for the continued fraction factoring algorithm. (English) Zbl 0617.10005

Following a suggestion of Daniel Shanks, to whom this paper is dedicated, the authors have adapted the quadratic sieve algorithm for factoring large integers, to exploit the architecture of a parallel processor. The massively parallel processor (MPP) at Goddard Space Flight Center can perform 16,384 independent arithmetic operations simultaneously. For the factorization of \(N\), the continued fraction coefficients and related terms of \(\sqrt{N}\) are computed. The authors develop a large step algorithm whereby the \(k\)th terms can be determined from the \(i\)th and \(j\)th terms, where \(i+j\approx k\). The MPP is to be used to compute 16,384 terms, spaced about \(10^ 6\) units apart, and then these are to be factored by trial divisions in parallel by a set of primes in a prime base. The running time on MPP to factor a 70 digit integer is estimated to be in the order of tens of seconds.
Reviewer: M.D.Hendy


11Y05 Factorization
11A55 Continued fractions
11-04 Software, source code, etc. for problems pertaining to number theory
68W10 Parallel algorithms in computer science
Full Text: DOI