Implementation of Primality Testing based on “Some Primality Tests that Eluded Lucas”

Simple item page
dc.contributor.authorKelly, Graham
dc.date.accessioned2018-10-10T15:34:31Z
dc.date.available2018-10-10T15:34:31Z
dc.date.issued2018-09-24
dc.description.abstractAn implementation of two primality tests in Guy, Roettger and Williams' 2015 paper 'Some Primality Tests that Eluded Lucas' was created using the GNU GMP integer package in C. These tests enable the determination of primality for numbers of the form N = Ar^n+γ or N = Ar^n+η(γ_n(r)) for small primes r coprime to A, γ^2 = 1, η^2 = 1 and n is a positive integer where (γ_n(r)) is the square root of -1 mod r^n. The runtime of the algorithms was determined to be O((log N)M(log N)) for the case of N = Ar^n+γ and O(M(log N)(loglog N)(log N))$ for the N = Ar^n+η(γ_n(r)) case. This presents a significant improvement for the determination of primality of numbers of both forms over general primality proving algorithms.en_US
dc.identifier.citationKelly, G. (2018). Implementation of Primality Testing based on “Some Primality Tests that Eluded Lucas” (Rep.). Calgary, AB: University of Calgary.en_US
dc.identifier.doihttp://dx.doi.org/10.11575/PRISM/33188
dc.identifier.urihttp://hdl.handle.net/1880/108848
dc.language.isoenen_US
dc.publisherUniversity of Calgaryen_US
dc.publisher.departmentComputer Scienceen_US
dc.publisher.facultyScienceen_US
dc.publisher.institutionUniversity of Calgaryen_US
dc.rightsUnless otherwise indicated, this material is protected by copyright and has been made available with authorization from the copyright owner. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission.en_US
dc.rights.urihttps://creativecommons.org/licenses/by/4.0en_US
dc.subjectLucas Sequencesen_US
dc.subjectComputer Scienceen_US
dc.subjectPrimality Testingen_US
dc.subjectPrimeen_US
dc.titleImplementation of Primality Testing based on “Some Primality Tests that Eluded Lucas”en_US
dc.title.alternativeLucas Based Primality Testing PURE Reporten_US
dc.typeunknown
Files
Original bundle
Now showing 1 - 2 of 2
Thumbnail Image
Name:
ucalgary_2018_kelly_graham.pdf
Size:
258.5 KB
Format:
Adobe Portable Document Format
Description:
PURE Project Report
Download
Thumbnail Image
Name:
ucalgary_2018_kelly_graham.zip
Size:
2.38 MB
Format:
Zip files based on Chrome
Description:
Primality Determining Program Source Code
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.92 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
PURE Research Report
Undergraduate Research & Publications