On the parallel generation of the residues for the continued fraction factoring algorithm

Authors:
H. C. Williams and M. C. Wunderlich

Journal:
Math. Comp. **48** (1987), 405-423

MSC:
Primary 11Y05

DOI:
https://doi.org/10.1090/S0025-5718-1987-0866124-1

MathSciNet review:
866124

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In order to implement the continued fraction algorithm on a highly parallel computer, like the Massively Parallel Processor, it is necessary to be able to compute certain numbers which occur at widely-spaced intervals within the continued fraction expansion of . where *N* is the number to be factored. In this paper several properties of the continued fraction expansion of a quadratic irrational are developed. These results are then applied to the development of a very simple algorithm for finding the widely-spaced numbers referred to above.

**[1]**G. Chrystal,*Textbook of Algebra*, Part 2, 2nd ed. reprinted, Dover, New York, 1969, pp. 423-490.**[2]**Harvey Cohn,*A second course in number theory*, John Wiley & Sons, Inc., New York-London, 1962. MR**0133281****[3]**J. A. Davis and D. B. Holdridge,*Factorization using the quadratic sieve algorithm*, Advances in cryptology (Santa Barbara, Calif., 1983) Plenum, New York, 1984, pp. 103–113. MR**799725****[4]**L. E. Dickson,*History of the Theory of Numbers*, Vol. II, reprinted, Chelsea, New York, 1952.**[5]**E. L. Ince, "Cycles of reduced ideals in quadratic fields,"*Mathematical Tables*, Vol. IV, British Association for the Advancement of Science, London, 1934.**[6]**H. W. Lenstra Jr.,*On the calculation of regulators and class numbers of quadratic fields*, Number theory days, 1980 (Exeter, 1980) London Math. Soc. Lecture Note Ser., vol. 56, Cambridge Univ. Press, Cambridge, 1982, pp. 123–150. MR**697260****[7]**Paul Lévy,*Sur le développement en fraction continue d’un nombre choisi au hasard*, Compositio Math.**3**(1936), 286–303 (French). MR**1556945****[8]**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**[9]**Oskar Perron,*Die Lehre von den Kettenbrüchen. Bd I. Elementare Kettenbrüche*, B. G. Teubner Verlagsgesellschaft, Stuttgart, 1954 (German). 3te Aufl. MR**0064172****[10]**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****[11]**Carl Pomerance and Samuel S. Wagstaff Jr.,*Implementation of the continued fraction integer factoring algorithm*, Congr. Numer.**37**(1983), 99–118. MR**703581****[12]**R. J. Schoof,*Quadratic fields and factorization*, Computational methods in number theory, Part II, Math. Centre Tracts, vol. 155, Math. Centrum, Amsterdam, 1982, pp. 235–286. MR**702519****[13]**Daniel Shanks,*The infrastructure of a real quadratic field and its applications*, Proceedings of the Number Theory Conference (Univ. Colorado, Boulder, Colo., 1972) Univ. Colorado, Boulder, Colo., 1972, pp. 217–224. MR**0389842**

Retrieve articles in *Mathematics of Computation*
with MSC:
11Y05

Retrieve articles in all journals with MSC: 11Y05

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1987-0866124-1

Article copyright:
© Copyright 1987
American Mathematical Society