A method of factoring and the factorization of

Authors:
Michael A. Morrison and John Brillhart

Journal:
Math. Comp. **29** (1975), 183-205

MSC:
Primary 10A25; Secondary 10-04

DOI:
https://doi.org/10.1090/S0025-5718-1975-0371800-5

Erratum:
Math. Comp. **35** (1980), 1444.

MathSciNet review:
0371800

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The continued fraction method for factoring integers, which was introduced by D. H. Lehmer and R. E. Powers, is discussed along with its computer implementation. The power of the method is demonstrated by the factorization of the seventh Fermat number and other large numbers of interest.

**[1]**J. BRILLHART & J. L. SELFRIDGE, "Some factorizations of and related results,"*Math. Comp.*, v. 21, 1967, pp. 87-96; Corrigendum,*ibid.*, v. 21, 1967, p. 751. MR**37**#131. MR**0224532 (37:131)****[2]**J. BRILLHART, D. H. LEHMER & J. L. SELFRIDGE, "New primality criteria and factorizations of ,"*Math. Comp.*(To appear.) MR**0384673 (52:5546)****[3]**D. JARDEN,*Recurring Sequences*, 2nd ed., Riveon Lematematika, Jerusalem, 1966, pp. 40-59. MR**33**#5548.**[4]**D. KNUTH,*The Art of Computer Programming*, Vol. 2:*Semi-Numerical Algorithms*, Addison-Wesley, Reading, Mass., 1969. MR**44**#3531. MR**633878 (83i:68003)****[5]**M. KRAITCHIK,*Recherches sur la théorie des nombres*. Tome II, Gauthier-Villars, Paris, 1929.**[6]**M. KRAITCHIK,*Théorie des nombres*. Tome II, Gauthier-Villars, Paris, 1926, pp. 195-208.**[7]**A. M. LEGENDRE,*Théorie des nombres*. Tome I, 3rd ed., Paris, 1830, pp. 334-341; Also under the title,*Zahlentheorie*, translated by H. Maser, Teubner, Leipzig, 1893, pp. 329-336.**[8]**D. H. LEHMER, "A photo electric number sieve,"*Amer. Math. Monthly*, v. 40, 1933, pp. 401-406. MR**1522863****[9]**D. H. LEHMER, "Computer technology applied to the theory of numbers,"*Studies in Number Theory*, Math. Assoc. Amer., distributed by Prentice-Hall, Englewood Cliffs, N.J., 1969, pp. 117-151. MR**40**#84. MR**0246815 (40:84)****[10]**D. H. LEHMER, "An announcement concerning the delay line sieve DLS-127,"*Math. Comp.*, v. 20, 1966, pp. 645-646.**[11]**D. H. LEHMER & R. E. POWERS, "On factoring large numbers,"*Bull. Amer. Math. Soc.*, v. 37, 1931, pp. 770-776. MR**1562254****[12]**D. N. LEHMER, "Hunting big game in the theory of numbers,"*Scripta Math.*, 1933, pp. 229-235.**[13]**D. N. LEHMER,*Factor Stencils*, rev. and extended by J. D. Elder, Carnegie Inst. of Washington, Washington, 1939. MR**1**#133. MR**0000817 (1:133a)****[14]**J. C. MOREHEAD, "Note on Fermat's numbers,"*Bull. Amer. Math. Soc.*, v. 11, 1905, pp. 543-545. MR**1558255****[15]**M. A. MORRISON & J. BRILLHART, "The factorization of ,"*Bull. Amer. Math. Soc.*, v. 77, 1971, p. 264. MR**42**#3012. MR**0268113 (42:3012)****[16]**F. PROTH,*Comptes Rendus*, Paris, v. 87, 1878, p. 374.**[17]**D. SHANKS, "Class number, a theory of factorization, and genera,"*Proc. Sympos. Pure Math.*, v. 20, Amer. Math. Soc., Providence, R.I., 1971, pp. 415-440. MR**47**#4932. MR**0316385 (47:4932)****[18]**A. E. WESTERN, "Note on Fermat's numbers and the converse of Fermat's theorem,"*Proc. London Math. Soc.*, v. 3, 1905, xxi-xxii.

Retrieve articles in *Mathematics of Computation*
with MSC:
10A25,
10-04

Retrieve articles in all journals with MSC: 10A25, 10-04

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1975-0371800-5

Keywords:
Factorization of integers,
Fermat numbers,
continued fraction method

Article copyright:
© Copyright 1975
American Mathematical Society