Speeding Fermat's factoring method

Author:
James McKee

Journal:
Math. Comp. **68** (1999), 1729-1737

MSC (1991):
Primary 11Y05; Secondary 11Y16, 68Q25

Published electronically:
March 1, 1999

MathSciNet review:
1653962

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A factoring method is presented which, heuristically, splits composite in steps. There are two ideas: an integer approximation to provides an algorithm in which is represented as the difference of two rational squares; observing that if a prime divides a square, then divides that square, a heuristic speed-up to steps is achieved. The method is well-suited for use with small computers: the storage required is negligible, and one never needs to work with numbers larger than itself.

**1.**Henri Cohen,*A course in computational algebraic number theory*, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR**1228206****2.**R. R. Hall,*Halving an estimate obtained from Selberg’s upper bound method*, Acta Arith.**25**(1973/74), 347–351. MR**0340193****3.**D. H. Lehmer and Emma Lehmer,*A new factorization technique using quadratic forms*, Math. Comp.**28**(1974), 625–635. MR**0342458**, 10.1090/S0025-5718-1974-0342458-5**4.**James McKee,*Turning Euler’s factoring method into a factoring algorithm*, Bull. London Math. Soc.**28**(1996), no. 4, 351–355. MR**1384821**, 10.1112/blms/28.4.351**5.**James McKee and Richard Pinch,*Old and new deterministic factoring algorithms*, Algorithmic number theory (Talence, 1996) Lecture Notes in Comput. Sci., vol. 1122, Springer, Berlin, 1996, pp. 217–224. MR**1446514**, 10.1007/3-540-61581-4_57**6.**J.M. Pollard, Personal communication.

Retrieve articles in *Mathematics of Computation of the American Mathematical Society*
with MSC (1991):
11Y05,
11Y16,
68Q25

Retrieve articles in all journals with MSC (1991): 11Y05, 11Y16, 68Q25

Additional Information

**James McKee**

Affiliation:
Pembroke College, Oxford, OX1 1DW, UK

Email:
jfm@maths.ox.ac.uk

DOI:
http://dx.doi.org/10.1090/S0025-5718-99-01133-3

Received by editor(s):
March 28, 1997

Published electronically:
March 1, 1999

Article copyright:
© Copyright 1999
American Mathematical Society