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

Williams, H. C.; Wunderlich, M. C.

Math. Comput. 48, 405-423 (1987).

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

Keywords:

quadratic irrational; continued fraction algorithm; CFRAC; computational number theory; factorization; quadratic sieve algorithm; large integers; parallel processor