Implementing the continued fraction factoring algorithm on parallel machines
Author:
Marvin C. Wunderlich
Journal:
Math. Comp. 44 (1985), 251260
MSC:
Primary 11Y65; Secondary 11A51, 11Y11
MathSciNet review:
771047
Fulltext PDF Free Access
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
(85c:11122), http://dx.doi.org/10.1090/S00255718198307016394
 [2]
Donald
E. Knuth, The art of computer programming. Vol. 2, 2nd ed.,
AddisonWesley Publishing Co., Reading, Mass., 1981. Seminumerical
algorithms; AddisonWesley Series in Computer Science and Information
Processing. MR
633878 (83i:68003)
 [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
(58 #16485)
 [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
(51 #8017), http://dx.doi.org/10.1090/S00255718197503718005
 [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
(84i:10005)
 [7]
Carl
Pomerance and Samuel
S. Wagstaff Jr., Implementation of the continued fraction integer
factoring algorithm, Congr. Numer. 37 (1983),
99–118. MR
703581 (85c:11124)
 [8]
M. C. Wunderlich, "DAP FORTRAN. A versatile language for parallel computing," Congr. Numer., v. 38, 1983, pp. 261270.
 [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
 [1]
 J. L. Gerver, "Factoring large numbers with a quadratic sieve," Math. Comp., v. 41, 1983, pp. 287294. MR 701639 (85c:11122)
 [2]
 D. E. Knuth, The Art of Computer Programming, Vol. 2, Seminumerical Algorithms, 2nd ed., AddisonWesley, Reading, Mass., 1981. MR 633878 (83i:68003)
 [3]
 D. E. Knuth & L. Trabb Pardo, "Analysis of a simple factorization algorithm," Theoret. Comput. Sci., v. 3, 1976, pp. 321348. MR 0498355 (58:16485)
 [4]
 M. A. Morrison & J. Brillhart, "A method of factoring and the factorization of ," Math. Comp., v. 29, 1975, pp. 183205. MR 0371800 (51:8017)
 [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, MC tract 154 (H. W. Lenstra and R. Tijdeman, eds.), pp. 89139. MR 700260 (84i:10005)
 [7]
 C. Pomerance & S. S. Wagstaff, Jr., "Implementation of the continued fraction factoring algorithm," Congr. Numer., v. 37, 1983, pp. 99118. MR 703581 (85c:11124)
 [8]
 M. C. Wunderlich, "DAP FORTRAN. A versatile language for parallel computing," Congr. Numer., v. 38, 1983, pp. 261270.
 [9]
 M. C. Wunderlich, "Factoring numbers on the massively parallel computer," Advances in Cryptology (David Chaum, ed.), 1984, pp. 87102. MR 799724
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
11Y65,
11A51,
11Y11
Retrieve articles in all journals
with MSC:
11Y65,
11A51,
11Y11
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198507710470
PII:
S 00255718(1985)07710470
Article copyright:
© Copyright 1985
American Mathematical Society
