Skip navigation
Skip navigation

Vector and parallel algorithms for integer factorisation

Brent, Richard P

Description

The problem of finding the prime factors of large composite numbers is of practical importance since the advent of public key cryptosystems whose security depends on the presumed difficulty of this problem. In recent years the best known integer factorisation algorithms have improved greatly. It is now routine to factor 60-decimal digit numbers, and possible to factor numbers of more than 110 decimal digits. We describe several integer factorisation algorithms, and consider their suitability...[Show more]

dc.contributor.authorBrent, Richard P
dc.date.accessioned2003-07-11
dc.date.accessioned2004-05-19T12:57:52Z
dc.date.accessioned2011-01-05T08:44:02Z
dc.date.available2004-05-19T12:57:52Z
dc.date.available2011-01-05T08:44:02Z
dc.date.created1990
dc.identifier.urihttp://hdl.handle.net/1885/40808
dc.identifier.urihttp://digitalcollections.anu.edu.au/handle/1885/40808
dc.description.abstractThe problem of finding the prime factors of large composite numbers is of practical importance since the advent of public key cryptosystems whose security depends on the presumed difficulty of this problem. In recent years the best known integer factorisation algorithms have improved greatly. It is now routine to factor 60-decimal digit numbers, and possible to factor numbers of more than 110 decimal digits. We describe several integer factorisation algorithms, and consider their suitability for implementation on vector processors and parallel machines.
dc.format.extent186237 bytes
dc.format.extent356 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypeapplication/octet-stream
dc.language.isoen_AU
dc.subjectinteger factorisation algorithms
dc.subjectvector processors
dc.subjectparallel machines
dc.subjectmultiple-precision arithmetic
dc.subjectPollard's "rho" algorithm
dc.subjectPollard's p-1 algorithm
dc.subjectelliptic curve algorithm
dc.subjectquadratic sieve algorithms
dc.subjectnumber field sieve
dc.titleVector and parallel algorithms for integer factorisation
dc.typeWorking/Technical Paper
local.description.refereedno
local.identifier.citationmonthoct
local.identifier.citationyear1990
local.identifier.eprintid1665
local.rights.ispublishedyes
dc.date.issued1990
local.contributor.affiliationANU
local.contributor.affiliationDepartment of Computer Science, FEIT
local.citationTR-CS-90-05
CollectionsANU Research Publications

Download

File Description SizeFormat Image
TR-CS-90-05.pdf181.87 kBAdobe PDFThumbnail


Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator