Speeding Fermat's factoring method

Author:
James McKee

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

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

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

Published electronically:
March 1, 1999

MathSciNet review:
1653962

Full-text PDF

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.**H. Cohen,*A course in computational algebraic number theory*, Graduate Texts in Mathematics 138, Springer, 1993. MR**94i:11105****2.**R.S. Lehman, Factoring large integers,*Math. Comp.*,**2**8 (1974), 637-646. MR**49:4949****3.**D.H. Lehmer and Emma Lehmer, A new factorization technique using quadratic forms,*Math. Comp.*,**2**8 (1974), 625-635. MR**49:7204****4.**J.F. McKee, Turning Euler's factoring method into a factoring algorithm,*Bull. London Math. Soc.*,**2**8 (1996), 351-355. MR**97f:11010****5.**J.F. McKee and R.G.E. Pinch, Old and new deterministic factoring algorithms, in*Algorithmic Number Theory, Proceedings of the Second International Symposium, ANTS-II*(H. Cohen, ed.), Lecture Notes in Computer Science 1122, Springer, 1996, pp. 217-224. MR**98a:11183****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:
https://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