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 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]**Michael A. Morrison and John Brillhart,*The factorization of 𝐹₇*, Bull. Amer. Math. Soc.**77**(1971), 264. MR**0268113**, 10.1090/S0002-9904-1971-12711-8**[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]**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****[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**7**(1953), 6–14. MR**0052876**, 10.1090/S0025-5718-1953-0052876-7**[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****[8]**G. B. Mathews,*Theory of numbers*, 2nd ed, Chelsea Publishing Co., New York, 1961. MR**0126402****[9]**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****[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 Angew. Math.**268/269**(1974), 294–301. Collection of articles dedicated to Helmut Hasse on his seventy-fifth birthday, II. MR**0345933**

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:
https://doi.org/10.1090/S0025-5718-1974-0342458-5

Keywords:
Factorization,
primality,
binary quadratic forms,
representation

Article copyright:
© Copyright 1974
American Mathematical Society