A new factorization technique using quadratic forms
Authors:
D. H. Lehmer and Emma Lehmer
Journal:
Math. Comp. 28 (1974), 625635
MSC:
Primary 10A25; Secondary 1004, 10B05
MathSciNet review:
0342458
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: The paper presents a practical method for factoring an arbitrary N by representing N or by one of at most three quadratic forms: . These three forms appropriate to N, together with inequalities for y, are given for all N prime to 6. Presently available sieving facilities make the method quite effective and economical for numbers N having 20 to 25 digits. Four examples arising from aliquot series are discussed in detail.
 [1]
J. D. Brillhart & M. A. Morrison, "The factorization of ," Bull. Amer. Math. Soc., v. 77, 1971, p. 264. MR 42 #3012. MR 0268113 (42:3012)
 [2]
P. L. Chebyshev, "Sur les formes quadratiques," J. Math. (1), v. 16, 1851, pp. 257282.
 [3]
L. E. Dickson, History of the Theory of Numbers. Vol. 1, Washington, 1919, Chap. 14.
 [4]
R. K. Guy & J. L. Selfridge, "Interim report on aliquot series, Conf. Numerical Mathematics, Winnipeg 1971, pp. 557580. MR 0335412 (49:194)
 [5]
D. H. Lehmer, "An announcement concerning the Delay Line Sieve DLS127," Math. Comp., v. 20, 1966, pp. 645646.
 [6]
D. H. Lehmer, "The sieve problem for allpurpose computers," Math. Tables and Other Aids to Computation, v. 7, 1953, pp. 614. MR 14, 691. MR 0052876 (14:691e)
 [7]
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)
 [8]
G. B. Mathews, Theory of Numbers, Cambridge, 1892; reprint, New York, 1961, pp. 261270. MR 0126402 (23:A3698)
 [9]
D. Shanks, Class Number, A Theory of Factorization and Genera, Proc. Sympos. Pure Math., vol. 20, Amer. Math. Soc., Providence, R.I., 1970, pp. 415440. MR 0316385 (47:4932)
 [10]
J. A. Todd, "A combinatorial problem," J. Mathematical Phys., v. 11, 1932, pp. 321333.
 [11]
Emma Lehmer, "On the quartic character of quadratic units," J. Reine Agnew. Math. (To appear.) MR 0345933 (49:10662)
 [1]
 J. D. Brillhart & M. A. Morrison, "The factorization of ," Bull. Amer. Math. Soc., v. 77, 1971, p. 264. MR 42 #3012. MR 0268113 (42:3012)
 [2]
 P. L. Chebyshev, "Sur les formes quadratiques," J. Math. (1), v. 16, 1851, pp. 257282.
 [3]
 L. E. Dickson, History of the Theory of Numbers. Vol. 1, Washington, 1919, Chap. 14.
 [4]
 R. K. Guy & J. L. Selfridge, "Interim report on aliquot series, Conf. Numerical Mathematics, Winnipeg 1971, pp. 557580. MR 0335412 (49:194)
 [5]
 D. H. Lehmer, "An announcement concerning the Delay Line Sieve DLS127," Math. Comp., v. 20, 1966, pp. 645646.
 [6]
 D. H. Lehmer, "The sieve problem for allpurpose computers," Math. Tables and Other Aids to Computation, v. 7, 1953, pp. 614. MR 14, 691. MR 0052876 (14:691e)
 [7]
 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)
 [8]
 G. B. Mathews, Theory of Numbers, Cambridge, 1892; reprint, New York, 1961, pp. 261270. MR 0126402 (23:A3698)
 [9]
 D. Shanks, Class Number, A Theory of Factorization and Genera, Proc. Sympos. Pure Math., vol. 20, Amer. Math. Soc., Providence, R.I., 1970, pp. 415440. MR 0316385 (47:4932)
 [10]
 J. A. Todd, "A combinatorial problem," J. Mathematical Phys., v. 11, 1932, pp. 321333.
 [11]
 Emma Lehmer, "On the quartic character of quadratic units," J. Reine Agnew. Math. (To appear.) MR 0345933 (49:10662)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
10A25,
1004,
10B05
Retrieve articles in all journals
with MSC:
10A25,
1004,
10B05
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718197403424585
PII:
S 00255718(1974)03424585
Keywords:
Factorization,
primality,
binary quadratic forms,
representation
Article copyright:
© Copyright 1974
American Mathematical Society
