## A new factorization technique using quadratic forms

HTML articles powered by AMS MathViewer

- by D. H. Lehmer and Emma Lehmer PDF
- Math. Comp.
**28**(1974), 625-635 Request permission

## 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

- Michael A. Morrison and John Brillhart,
*The factorization of $F_{7}$*, Bull. Amer. Math. Soc.**77**(1971), 264. MR**268113**, DOI 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 10.1090/S0025-5718-1953-0052876-7 - D. H. Lehmer,
*Computer technology applied to the theory of numbers*, Studies in Number Theory, Math. Assoc. America, Buffalo, N.Y.; 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 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.

## Additional Information

- © Copyright 1974 American Mathematical Society
- 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