Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

A new factorization technique using quadratic forms


Authors: D. H. Lehmer and Emma Lehmer
Journal: Math. Comp. 28 (1974), 625-635
MSC: Primary 10A25; Secondary 10-04, 10B05
MathSciNet review: 0342458
Full-text 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 $ \lambda N$ by one of at most three quadratic forms: $ \lambda N = {x^2} - D{y^2},\lambda = 1, - 1,2,D = - 1, \pm 2, \pm 3, \pm 6$. 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.


References [Enhancements On Off] (What's this?)

  • [1] J. D. Brillhart & M. A. Morrison, "The factorization of $ {F_7}$," 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. 257-282.
  • [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. 557-580. MR 0335412 (49:194)
  • [5] D. H. Lehmer, "An announcement concerning the Delay Line Sieve DLS127," Math. Comp., v. 20, 1966, pp. 645-646.
  • [6] D. H. Lehmer, "The sieve problem for all-purpose computers," Math. Tables and Other Aids to Computation, v. 7, 1953, pp. 6-14. 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 Prentice-Hall, Englewood Cliffs, N.J.), 1969, pp. 117-151. MR 40 #84. MR 0246815 (40:84)
  • [8] G. B. Mathews, Theory of Numbers, Cambridge, 1892; reprint, New York, 1961, pp. 261-270. 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. 415-440. MR 0316385 (47:4932)
  • [10] J. A. Todd, "A combinatorial problem," J. Mathematical Phys., v. 11, 1932, pp. 321-333.
  • [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, 10-04, 10B05

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


Additional Information

DOI: http://dx.doi.org/10.1090/S0025-5718-1974-0342458-5
PII: S 0025-5718(1974)0342458-5
Keywords: Factorization, primality, binary quadratic forms, representation
Article copyright: © Copyright 1974 American Mathematical Society