The Library
A one line factoring algorithm
Tools
Hart, William B. (2012) A one line factoring algorithm. Journal of the Australian Mathematical Society, Volume 92 (Number 1). pp. 61-69. doi:10.1017/S1446788712000146 ISSN 1446-7887.
|
Text
WRAP_Hart_S1446788712000146a.pdf - Published Version Download (317Kb) | Preview |
|
Text
WRAP_Hart_Preprint_0584144-ma-270913-onelinefactor.pdf - Submitted Version Embargoed item. Restricted access to Repository staff only Download (250Kb) |
Official URL: http://dx.doi.org/10.1017/S1446788712000146
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.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Library of Congress Subject Headings (LCSH): | Algorithms | ||||
Journal or Publication Title: | Journal of the Australian Mathematical Society | ||||
Publisher: | Cambridge University Press | ||||
ISSN: | 1446-7887 | ||||
Official Date: | 2012 | ||||
Dates: |
|
||||
Volume: | Volume 92 | ||||
Number: | Number 1 | ||||
Page Range: | pp. 61-69 | ||||
DOI: | 10.1017/S1446788712000146 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Date of first compliant deposit: | 24 December 2015 | ||||
Date of first compliant Open Access: | 24 December 2015 | ||||
Funder: | Engineering and Physical Sciences Research Council (EPSRC) | ||||
Grant number: | EP/G004870/1, EP/D079543/1 (EPSRC) |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year