Implementation of Primality Testing based on “Some Primality Tests that Eluded Lucas”
Date
2018-09-24
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
Lucas Sequences, Computer Science, Primality Testing, Prime
Citation
Kelly, G. (2018). Implementation of Primality Testing based on “Some Primality Tests that Eluded Lucas” (Rep.). Calgary, AB: University of Calgary.