Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

On the parallel generation of the residues for the continued fraction factoring algorithm
HTML articles powered by AMS MathViewer

by H. C. Williams and M. C. Wunderlich PDF
Math. Comp. 48 (1987), 405-423 Request permission

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 $\sqrt N$. 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.
References
    G. Chrystal, Textbook of Algebra, Part 2, 2nd ed. reprinted, Dover, New York, 1969, pp. 423-490.
  • Harvey Cohn, A second course in number theory, John Wiley & Sons, Inc., New York-London, 1962. MR 0133281
  • 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
    • L. E. Dickson, History of the Theory of Numbers, Vol. II, reprinted, Chelsea, New York, 1952. E. L. Ince, "Cycles of reduced ideals in quadratic fields," Mathematical Tables, Vol. IV, British Association for the Advancement of Science, London, 1934.
  • 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
  • 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
  • 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
  • Oskar Perron, Die Lehre von den Kettenbrüchen. Bd I. Elementare Kettenbrüche, B. G. Teubner Verlagsgesellschaft, Stuttgart, 1954 (German). 3te Aufl. MR 0064172
  • 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
  • H. Zantema, Class numbers and units, Computational methods in number theory, Part II, Math. Centre Tracts, vol. 155, Math. Centrum, Amsterdam, 1982, pp. 213–234. MR 702518
  • 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
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC: 11Y05
  • Retrieve articles in all journals with MSC: 11Y05
Additional Information
  • © Copyright 1987 American Mathematical Society
  • Journal: Math. Comp. 48 (1987), 405-423
  • MSC: Primary 11Y05
  • DOI: https://doi.org/10.1090/S0025-5718-1987-0866124-1
  • MathSciNet review: 866124