Week 3: More Primality Tests and a Lead on How to Exponentiate Large Numbers

Hello everyone, and welcome back to my blog!

This week I learned about some more primality tests that are used in the generation of prime numbers for use in RSA encryption including: the Miller-Rabin test, Baillie-PSW test and Solovay-Strassen test. These tests tend to follow this pattern: start with some proven mathematical theorem about primes that given a prime number p and any number a, some statement must be true. Then to test whether a number n is likely to be prime, a program tests whether the statement hold for n and various values of a. If the program finds a value for a for which the statement doesn’t hold, then n is now known to be composite (and the number a is said to be a “witness” to n’s compositeness). This means that rather than showing that a number is prime, they are only designed to quickly rule out a candidate number as being composite.

Next week I will be retrying an idea I had to make exponentiation of large numbers (as used to decrypt messages ecrypted with RSA) more efficient so that a computer can do so in an acceptably short amount of time, this time with a slight modification to the original idea that I think will make it work. I will also research what challenges to RSA there may be, namely what efficient algorithms have been devised to factorize prime numbers (this may lead to the realm of quantum computing and Shor’s algorithm). I would also like to see how the extended Riemann Hypothesis can improve the Miller-Rabin test, which may connect cybersecurity with the math that was originally the reason behind this project.