Browsing by Author "Kelly, Graham"
Now showing 1 - 1 of 1
Results Per Page
Sort Options
- ItemOpen AccessImplementation of Primality Testing based on “Some Primality Tests that Eluded Lucas”(University of Calgary, 2018-09-24) Kelly, GrahamAn 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.