Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-16T20:55:05.088Z Has data issue: false hasContentIssue false

A ONE LINE FACTORING ALGORITHM

Published online by Cambridge University Press:  15 June 2012

WILLIAM B. HART*
Affiliation:
Zeeman Building, University of Warwick, Coventry CV4 7AL, UK (email: W.B.Hart@warwick.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

MSC classification

Information

Type
Research Article
Copyright
Copyright © Australian Mathematical Publishing Association Inc. 2012