Week 2: RSA in Practice

Hello everyone and welcome back to my blog! As I discussed last time, my research this week has been devoted to seeing how issues in the use of RSA have been addressed making the encryption method useful in practice.

This week I learned about several “primality tests”, methods used to test whether a number is likely a prime, or rather to quickly rule out that a number is not a prime. Tests like the Fermat primality test can make no guarantee that a number you are testing is in fact prime, but if the number is composite, it is likely that the test will quickly rule out that it is prime (though it might not). There may still be some problems involving the implementation of RSA that I faced that I may want to do further research on overcoming (namely how exponentiation for large numbers is done quickly).

On a slightly unrelated note, but one which I think will be useful in explaining why these tests for prime candidates are necessary during my final presentation is some information I found about the largest known primes, Mersenne Primes and Bertrand’s Postulate. Fascinatingly, despite Bertrand’s Postulate (which is in fact now a proven theorem, but still called a postulate (part of my research involved reviewing the proof of this theorem)) guaranteeing that for any n there is a prime number between n and 2n, the gaps between the largest known primes are massive, differing by millions of digits (cf: https://en.wikipedia.org/wiki/Largest_known_prime_number#Current_record) Additionally, most of these numbers are in fact Mersenne Primes (primes of the form 2^a-1). This sort of reveals something about the way in which these primes were discovered. They were not discovered by simply testing large numbers and seeing whether or not they are prime, but rather by testing numbers (of the form 2^a-1) that were good candidates for maybe being prime, and in fact there is an especially efficient way to test numbers specifically of this form (called the Lucas-Lehmer test) that was used.

Also, I found this cool quote by Paul Erdos: “God may not play dice with the universe, but something strange is going on with the prime numbers.”