After reading several different sources of math history, I was attracted by Fermat’s history and his theorems about prime numbers. I realized that I am kind of interested in these numbers and anything related to these numbers after digging into the computer science major for few years. Why? I think the primary reason is because prime numbers are widely used in computer science for security. For example, the RSA algorithm, which is a public-key crypto system, uses prime numbers to generate public keys. If you are not familiar with the RSA algorithm, I will explain a little bit more here. Basically, the RSA algorithm generates a public key based on two large prime numbers. The prime numbers are secret. Anybody is able to use the public key to encrypt a message. When I first learned this RSA algorithm in my algorithm class, I felt like it was magic! After taking computer networking, the computer networking class, I realized that prime numbers were everywhere in my life. For example, you go to amazon.com to buy some stuff, you need to login to your account and pay the bill online. Behind the scenes, there are prime numbers securing your account and transactions. This interest brought a new question to me, which was how to generate a big prime number? Another way to think about this question is how to determine whether a number is a prime?
FLT and modern computer science. Image by the author.
Because of my curiosity about prime numbers, I enjoyed reading and thinking about FLT. In class, FLT means Fermat’s Last Theorem, but in this blog post, it means Fermat’s Little Theorem. Basically, FLT says if p is a prime number, then for any integer a, a^p – p is a multiple of p. If a is not divisible by p, then a^(p-1) – 1 is an integer which is multiple of p (Wikipedia). How can this math theorem help a computer science student? I solved some programming questions related to prime numbers. For example, generate all prime numbers less than n. If n is 10, my program should return 2, 3, 5, 7 as a result. The other programming question was to write a program that runs a primality test, which is used to see whether a number is prime. For example, if the input number is 10, my program should return true if 10 is a prime number and false if 10 is not a prime number. I was able to solve such questions by using an inefficient algorithm. If a number was very big, it took more than an hour to get the final result. Obviously, I did not expect such a slow algorithm. By combining FLT into programming, I can write an efficiency algorithm to solve those questions.
Computer science majors might be wondering how a Fermat primality test works. First of all, we have an integer n and we need to choose some integers co-prime to n. Then we need to calculate a^(n-1) mod n. Let’s say the result is different from 1, then n is composite. If the result is 1, then we can say n may or may not be a prime number. For example, let’s use p = 341 and a = 2, then we have 2^340 = 1 (mod 341). Obviously, 341 is not a prime number because 341 = 11 * 31. So we call 341 a pseudoprime base 2. Such a pseudoprime number is also called a Carmichael number. This is a primary reason why we cannot directly use the FLT for a primality test: it will be fooled by some Carmichael numbers. That means we have to do something else to get it work on solving programming questions! There are only 21853 pseudoprimes base 2 for n from 1 to 25 * 10^9. How does this data help us? If 2^n – 1 mod n = 1, then n is a prime number, or n is one of those 21853 pseudoprimes. I think we can build a list of pseudoprimes before running our program for primality test. When we need to check if a number is a prime number, we can check if this number is a pseudoprimes in the list. If it is not one of the pseudoprimes, we can start running the program for primality test. The FLT was like the roots of a binary tree. People used this root to branch out its left children and right children. In our case, one of the children referred to is the Fermat primality test. At this moment, I cannot stop digging deeper in this tree. I want to traverse the whole tree just like running a breadth-first search in my brain.
Number theory is a mystery! After reading the articles, I asked myself a question “How many unknown theorems still exist?” It might be like the universe – people have only explored a tiny part of it. It may hide more secrets behind the scenes – people need time to reveal those secrets. Probably after a few years, scientists will discover many more theorems, just like FLT.
3010tangents 