a1 Zeeman Building, University of Warwick, Coventry CV4 7AL, UK (email: W.B.Hart@warwick.ac.uk)
We describe a variant of Fermat’s factoring algorithm which is competitive with SQUFOF in practice but has heuristic run time complexity O(n1/3) as a general factoring algorithm. We also describe a sparse class of integers for which the algorithm is particularly effective. We provide speed comparisons between an optimised implementation of the algorithm described and the tuned assortment of factoring algorithms in the Pari/GP computer algebra package.
(Received April 16 2011)
(Accepted February 01 2012)
2010 Mathematics subject classification
Keywords and phrases
Supported by EPSRC grants EP/G004870/1 and EP/D079543/1.
Communicated by I. E. Shparlinski
In memory of my former PhD supervisor Alf van der Poorten