A method of factoring and the factorization of
Authors:
Michael A. Morrison and John Brillhart
Journal:
Math. Comp. 29 (1975), 183205
MSC:
Primary 10A25; Secondary 1004
Erratum:
Math. Comp. 35 (1980), 1444.
MathSciNet review:
0371800
Fulltext PDF Free Access
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]
John
Brillhart and J.
L. Selfridge, Some factorizations of 2ⁿ±1 and related
results, Math. Comp. 21 (1967), 8796; corrigendum, ibid.
21 (1967), 751. MR 0224532
(37 #131)
 [2]
John
Brillhart, D.
H. Lehmer, and J.
L. Selfridge, New primality criteria and
factorizations of 2^{𝑚}±1, Math.
Comp. 29 (1975),
620–647. MR 0384673
(52 #5546), http://dx.doi.org/10.1090/S00255718197503846731
 [3]
D. JARDEN, Recurring Sequences, 2nd ed., Riveon Lematematika, Jerusalem, 1966, pp. 4059. MR 33 #5548.
 [4]
Donald
E. Knuth, The art of computer programming. Vol. 2, 2nd ed.,
AddisonWesley Publishing Co., Reading, Mass., 1981. Seminumerical
algorithms; AddisonWesley Series in Computer Science and Information
Processing. MR
633878 (83i:68003)
 [5]
M. KRAITCHIK, Recherches sur la théorie des nombres. Tome II, GauthierVillars, Paris, 1929.
 [6]
M. KRAITCHIK, Théorie des nombres. Tome II, GauthierVillars, Paris, 1926, pp. 195208.
 [7]
A. M. LEGENDRE, Théorie des nombres. Tome I, 3rd ed., Paris, 1830, pp. 334341; Also under the title, Zahlentheorie, translated by H. Maser, Teubner, Leipzig, 1893, pp. 329336.
 [8]
D.
H. Lehmer, A PhotoElectric Number Sieve, Amer. Math. Monthly
40 (1933), no. 7, 401–406. MR
1522863, http://dx.doi.org/10.2307/2302134
 [9]
D.
H. Lehmer, Computer technology applied to the theory of
numbers, Studies in Number Theory, Math. Assoc. Amer. (distributed by
PrenticeHall, Englewood Cliffs, N.J.), 1969, pp. 117–151. MR 0246815
(40 #84)
 [10]
D. H. LEHMER, "An announcement concerning the delay line sieve DLS127," Math. Comp., v. 20, 1966, pp. 645646.
 [11]
D.
H. Lehmer and R.
E. Powers, On factoring large numbers,
Bull. Amer. Math. Soc. 37 (1931),
no. 10, 770–776. MR
1562254, http://dx.doi.org/10.1090/S00029904193105271X
 [12]
D. N. LEHMER, "Hunting big game in the theory of numbers," Scripta Math., 1933, pp. 229235.
 [13]
D.
N. Lehmer, Factor Stencils, Carnegie Institution of
Washington, Washington, 1939. Revised and extended by John D. Elder. MR 0000817
(1,133a)
 [14]
J.
C. Morehead, Note on Fermat’s
numbers, Bull. Amer. Math. Soc.
11 (1905), no. 10,
543–545. MR
1558255, http://dx.doi.org/10.1090/S000299041905012556
 [15]
Michael
A. Morrison and John
Brillhart, The factorization of
𝐹₇, Bull. Amer. Math. Soc.
77 (1971), 264. MR 0268113
(42 #3012), http://dx.doi.org/10.1090/S000299041971127118
 [16]
F. PROTH, Comptes Rendus, Paris, v. 87, 1878, p. 374.
 [17]
Daniel
Shanks, Class number, a theory of factorization, and genera,
1969 Number Theory Institute (Proc. Sympos. Pure Math., Vol. XX, State
Univ. New York, Stony Brook, N.Y., 1969) Amer. Math. Soc., Providence,
R.I., 1971, pp. 415–440. 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, xxixxii.
 [1]
 J. BRILLHART & J. L. SELFRIDGE, "Some factorizations of and related results," Math. Comp., v. 21, 1967, pp. 8796; 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. 4059. MR 33 #5548.
 [4]
 D. KNUTH, The Art of Computer Programming, Vol. 2: SemiNumerical Algorithms, AddisonWesley, Reading, Mass., 1969. MR 44 #3531. MR 633878 (83i:68003)
 [5]
 M. KRAITCHIK, Recherches sur la théorie des nombres. Tome II, GauthierVillars, Paris, 1929.
 [6]
 M. KRAITCHIK, Théorie des nombres. Tome II, GauthierVillars, Paris, 1926, pp. 195208.
 [7]
 A. M. LEGENDRE, Théorie des nombres. Tome I, 3rd ed., Paris, 1830, pp. 334341; Also under the title, Zahlentheorie, translated by H. Maser, Teubner, Leipzig, 1893, pp. 329336.
 [8]
 D. H. LEHMER, "A photo electric number sieve," Amer. Math. Monthly, v. 40, 1933, pp. 401406. MR 1522863
 [9]
 D. H. LEHMER, "Computer technology applied to the theory of numbers," Studies in Number Theory, Math. Assoc. Amer., distributed by PrenticeHall, Englewood Cliffs, N.J., 1969, pp. 117151. MR 40 #84. MR 0246815 (40:84)
 [10]
 D. H. LEHMER, "An announcement concerning the delay line sieve DLS127," Math. Comp., v. 20, 1966, pp. 645646.
 [11]
 D. H. LEHMER & R. E. POWERS, "On factoring large numbers," Bull. Amer. Math. Soc., v. 37, 1931, pp. 770776. MR 1562254
 [12]
 D. N. LEHMER, "Hunting big game in the theory of numbers," Scripta Math., 1933, pp. 229235.
 [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. 543545. 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. 415440. 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, xxixxii.
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
10A25,
1004
Retrieve articles in all journals
with MSC:
10A25,
1004
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718197503718005
PII:
S 00255718(1975)03718005
Keywords:
Factorization of integers,
Fermat numbers,
continued fraction method
Article copyright:
© Copyright 1975
American Mathematical Society
