## 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

### MSC:

 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: