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

DOI:
https://doi.org/10.1090/S0025-5718-1974-0342458-5

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.

- Michael A. Morrison and John Brillhart,
*The factorization of $F_{7}$*, Bull. Amer. Math. Soc.**77**(1971), 264. MR**268113**, DOI https://doi.org/10.1090/S0002-9904-1971-12711-8
P. L. Chebyshev, "Sur les formes quadratiques," - Richard K. Guy and J. L. Selfridge,
*Interim report on aliquot series*, Proceedings of the Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1971) Dept. Comput. Sci., Univ. Manitoba, Winnipeg, Man., 1971, pp. 557โ580. MR**0335412**
D. H. Lehmer, "An announcement concerning the Delay Line Sieve DLS127," - D. H. Lehmer,
*The sieve problem for all-purpose computers*, Math. Tables Aids Comput.**7**(1953), 6โ14. MR**52876**, DOI https://doi.org/10.1090/S0025-5718-1953-0052876-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**0246815** - G. B. Mathews,
*Theory of numbers*, Chelsea Publishing Co., New York, 1961. 2nd ed. MR**0126402** - 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**
J. A. Todd, "A combinatorial problem," - Emma Lehmer,
*On the quartic character of quadratic units*, J. Reine Angew. Math.**268(269)**(1974), 294โ301. MR**345933**, DOI https://doi.org/10.1515/crll.1974.268-269.294

*J. Math.*(1), v. 16, 1851, pp. 257-282. L. E. Dickson,

*History of the Theory of Numbers*. Vol. 1, Washington, 1919, Chap. 14.

*Math. Comp.*, v. 20, 1966, pp. 645-646.

*J. Mathematical Phys.*, v. 11, 1932, pp. 321-333.

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

Keywords:
Factorization,
primality,
binary quadratic forms,
representation

Article copyright:
© Copyright 1974
American Mathematical Society