Implementing the continued fraction factoring algorithm on parallel machines

Author:
Marvin C. Wunderlich

Journal:
Math. Comp. **44** (1985), 251-260

MSC:
Primary 11Y65; Secondary 11A51, 11Y11

DOI:
https://doi.org/10.1090/S0025-5718-1985-0771047-0

MathSciNet review:
771047

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: An implementation is described of the continued fraction factoring algorithm on the DAP parallel processor located in Queen Mary College in London. The DAP has 4096 parallel processors each containing 16K bits of memory and the suggested implementation incorporates the early abort strategy and the large prime variation.

**[1]**Joseph L. Gerver,*Factoring large numbers with a quadratic sieve*, Math. Comp.**41**(1983), no. 163, 287–294. MR**701639**, https://doi.org/10.1090/S0025-5718-1983-0701639-4**[2]**Donald E. Knuth,*The art of computer programming. Vol. 2*, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR**633878****[3]**Donald E. Knuth and Luis Trabb Pardo,*Analysis of a simple factorization algorithm*, Theoret. Comput. Sci.**3**(1976/77), no. 3, 321–348. MR**0498355**, https://doi.org/10.1016/0304-3975(76)90050-5**[4]**Michael A. Morrison and John Brillhart,*A method of factoring and the factorization of 𝐹₇*, Math. Comp.**29**(1975), 183–205. Collection of articles dedicated to Derrick Henry Lehmer on the occasion of his seventieth birthday. MR**0371800**, https://doi.org/10.1090/S0025-5718-1975-0371800-5**[5]**D. Parkinson & M. C. Wunderlich, "A compact algorithm for Gaussian elimination over implemented on highly parallel computers,"*Parallel Computing*, v. 1, 1984.**[6]**C. Pomerance,*Analysis and comparison of some integer factoring algorithms*, Computational methods in number theory, Part I, Math. Centre Tracts, vol. 154, Math. Centrum, Amsterdam, 1982, pp. 89–139. MR**700260****[7]**Carl Pomerance and Samuel S. Wagstaff Jr.,*Implementation of the continued fraction integer factoring algorithm*, Congr. Numer.**37**(1983), 99–118. MR**703581****[8]**M. C. Wunderlich, "DAP FORTRAN. A versatile language for parallel computing,"*Congr. Numer.*, v. 38, 1983, pp. 261-270.**[9]**Marvin C. Wunderlich,*Factoring numbers on the massively parallel computer*, Advances in cryptology (Santa Barbara, Calif., 1983) Plenum, New York, 1984, pp. 87–102. MR**799724**

Retrieve articles in *Mathematics of Computation*
with MSC:
11Y65,
11A51,
11Y11

Retrieve articles in all journals with MSC: 11Y65, 11A51, 11Y11

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1985-0771047-0

Article copyright:
© Copyright 1985
American Mathematical Society