My name is Rose Rothschild, and I am a senior at Pine Crest School. This research was conducted at Florida Atlantic University.

Prime Time - Primality Testing With Proof of Correctness: Maurer’s Algorithm vs. Miller-Rabin

Prime numbers are vital to the field of cryptography and are necessary to secure data transmission using the RSA algorithm. In order for cryptography to be secure, it is important that prime numbers generated by mathematical computations be distributed uniformly. This means that the likelihood of an algorithm picking a specific prime number should be the same for all prime numbers of the given size. In my previous work, the Miller-Rabin algorithm was compared to Maurer's Algorithm to determine the relative speeds to find prime numbers. According to the observed data, the Miller-Rabin primality test was faster than Maurer’s method, although only by a small difference in the leading coefficient of the best-fit polynomials.

This study focuses on Maurer's Algorithm and its distribution to determine if this primality test could realistically be used. A method was coded using Python to compare all possible prime numbers 15-bits long to a list of random prime numbers found by Maurer's Algorithm or a random number function. Then, the difference between all possible 15-bit prime numbers and the ones found by each function for a varying number of iterations were determined. According to the data obtained, there was no difference between the random number function and Maurer's Algorithm. This shows that at least for numbers 15-bits long, Maurer's Algorithm has uniform distribution. More research must be done to determine if the even distribution will scale up to higher bit lengths, which are practical for cryptography, but this shows promising evidence that distribution is uniform.