Speeding Fermat’s factoring method
HTML articles powered by AMS MathViewer
- by James McKee PDF
- Math. Comp. 68 (1999), 1729-1737 Request permission
Abstract:
A factoring method is presented which, heuristically, splits composite $n$ in $O(n^{1/4+\epsilon })$ steps. There are two ideas: an integer approximation to $\surd (q/p)$ provides an $O(n^{1/2+\epsilon })$ algorithm in which $n$ is represented as the difference of two rational squares; observing that if a prime $m$ divides a square, then $m^2$ divides that square, a heuristic speed-up to $O(n^{1/4+\epsilon })$ 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 $n$ itself.References
- Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
- R. R. Hall, Halving an estimate obtained from Selberg’s upper bound method, Acta Arith. 25 (1973/74), 347–351. MR 340193, DOI 10.4064/aa-25-4-347-351
- D. H. Lehmer and Emma Lehmer, A new factorization technique using quadratic forms, Math. Comp. 28 (1974), 625–635. MR 342458, DOI 10.1090/S0025-5718-1974-0342458-5
- James McKee, Turning Euler’s factoring method into a factoring algorithm, Bull. London Math. Soc. 28 (1996), no. 4, 351–355. MR 1384821, DOI 10.1112/blms/28.4.351
- 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, DOI 10.1007/3-540-61581-4_{5}7
- J.M. Pollard, Personal communication.
Additional Information
- James McKee
- Affiliation: Pembroke College, Oxford, OX1 1DW, UK
- Email: jfm@maths.ox.ac.uk
- Received by editor(s): March 28, 1997
- Published electronically: March 1, 1999
- © Copyright 1999 American Mathematical Society
- 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
- MathSciNet review: 1653962