Implementation of Primality Testing based on “Some Primality Tests that Eluded Lucas”
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of Calgary
Abstract
An 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.
Description
Keywords
Citation
Kelly, G. (2018). Implementation of Primality Testing based on “Some Primality Tests that Eluded Lucas” (Rep.). Calgary, AB: University of Calgary.
Endorsement
Review
Supplemented By
Referenced By
Creative Commons license
Except where otherwised noted, this item's license is described as Unless 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.
