Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 

 

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
MathSciNet review: 866124
Full-text PDF Free Access

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 $ \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 [Enhancements On Off] (What's this?)

  • [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, 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

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11Y05

Retrieve articles in all journals with MSC: 11Y05


Additional Information

DOI: http://dx.doi.org/10.1090/S0025-5718-1987-0866124-1
Article copyright: © Copyright 1987 American Mathematical Society