Journal of the Australian Mathematical Society

Table of Contents - February 2012 - Volume 92, Issue 01  

Research Article

A ONE LINE FACTORING ALGORITHM

WILLIAM B. HARTa1

a1 Zeeman Building, University of Warwick, Coventry CV4 7AL, UK (email: W.B.Hart@warwick.ac.uk)

Abstract

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

  • primary 11A51

Keywords and phrases

  • integer factorisation;
  • Lehman’s algorithm;
  • Fermat’s algorithm

Footnotes

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