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), 405423
MSC:
Primary 11Y05
MathSciNet review:
866124
Fulltext 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 widelyspaced 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 widelyspaced numbers referred to above.
 [1]
G. Chrystal, Textbook of Algebra, Part 2, 2nd ed. reprinted, Dover, New York, 1969, pp. 423490.
 [2]
Harvey
Cohn, A second course in number theory, John Wiley & Sons,
Inc., New YorkLondon, 1962. MR 0133281
(24 #A3115)
 [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
(86j:11128)
 [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
(86g:11080)
 [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
(51 #8017), http://dx.doi.org/10.1090/S00255718197503718005
 [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
(16,239e)
 [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
(84i:10005)
 [11]
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)
 [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
(85g:11118b)
 [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
(52 #10672)
 [1]
 G. Chrystal, Textbook of Algebra, Part 2, 2nd ed. reprinted, Dover, New York, 1969, pp. 423490.
 [2]
 H. Cohn, A Second Course in Number Theory, Wiley, New York, 1962. MR 0133281 (24:A3115)
 [3]
 J. A. Davis & D. B. Holdridge, "Factorization using the quadratic sieve algorithm," Advances in Cryptology, Proceedings of Crypto 83, Plenum Press, New York, 1984, pp. 103113. MR 799725 (86j:11128)
 [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 number of quadratic fields," London Math. Soc. Lecture Note Ser., v. 56, 1982, pp. 123150. MR 697260 (86g:11080)
 [7]
 Paul Lévy, "Sur le développement en fraction continue d'un nombre choisi au hasard," Compositio Math., v. 3, 1936, pp. 286303. MR 1556945
 [8]
 M. A. Morrison & J. Brillhart, "A method of factoring and the factorization of ," Math. Comp., v. 29, 1975, pp. 183205. MR 0371800 (51:8017)
 [9]
 Oskar Perron, Die Lehre von den Kettenbrüchen, Bd. I, 3rd ed., B. G. Teubner, Stuttgart, 1954. MR 0064172 (16:239e)
 [10]
 C. Pomerance, "Analysis and comparison of some integer factoring algorithms," Computational Methods in Number Theory (H. W. Lenstra. Jr. and R. Tijdeman, eds.), Math. Centrum Tracts, Number 154, Part I, Amsterdam, 1983, pp. 89139. MR 700260 (84i:10005)
 [11]
 C. Pomerance & S. S. Wagstaff, Jr., Implementation of the Continued Fraction Integer Factoring Algorithm, Proc. 12th Winnipeg Conf. on Numerical Methods of Computing, Congress. Numer., v. 37, 1983, pp. 99118. MR 703581 (85c:11124)
 [12]
 R. G. Schoof, "Quadratic fields and factorization," Computational Methods in Number Theory (H. W. Lenstra, Jr. and R. Tijdeman, eds.), Math. Centrum Tracts, Number 155, Part II, Amsterdam, 1983, pp. 235286. MR 702519 (85g:11118b)
 [13]
 D. Shanks, The Infrastructure of a Real Quadratic Field und its Applications, Proc. 1972 Number Theory Conference, Boulder, Colorado, 1972, pp. 217224. MR 0389842 (52:10672)
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/S00255718198708661241
PII:
S 00255718(1987)08661241
Article copyright:
© Copyright 1987
American Mathematical Society
