Implementing the continued fraction factoring algorithm on parallel machines

Wunderlich, Marvin C.

doi:10.1090/S0025-5718-1985-0771047-0

Implementing the continued fraction factoring algorithm on parallel machines
HTML articles powered by AMS MathViewer

by Marvin C. Wunderlich PDF

Math. Comp. 44 (1985), 251-260 Request permission

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.

References

Joseph L. Gerver, Factoring large numbers with a quadratic sieve, Math. Comp. 41 (1983), no. 163, 287–294. MR 701639, DOI 10.1090/S0025-5718-1983-0701639-4
Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
Donald E. Knuth and Luis Trabb Pardo, Analysis of a simple factorization algorithm, Theoret. Comput. Sci. 3 (1976/77), no. 3, 321–348. MR 498355, DOI 10.1016/0304-3975(76)90050-5
Michael A. Morrison and John Brillhart, A method of factoring and the factorization of $F_{7}$, Math. Comp. 29 (1975), 183–205. MR 371800, DOI 10.1090/S0025-5718-1975-0371800-5

Parallel Computing

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
Carl Pomerance and Samuel S. Wagstaff Jr., Implementation of the continued fraction integer factoring algorithm, Congr. Numer. 37 (1983), 99–118. MR 703581

Congr. Numer.

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