When Miller Met Rabin — Magic Happened …
We live in a digitally flaw world. Very little of what we see can be truly trusted. But there are some people who have strived to make our world more trusted, and Michael O. Rabin is one of the most predominant. He was born in 1931 in Germany. In the 1960s he worked in the University of California and MIT, and then moved onto a Professorship at Harvard University. Finally, in 1981, he became a professor at the Hebrew University and has worked there ever since.
Miller-Rabin Test for Primes is one of the most popular methods for testing for prime numbers used in RSA. Given an odd number (n), we will have an odd number of (n−1), of which we can calculate the power of 2 with a value of s so that:
For example, if n is 25, (n−1) will be 24, and which is 2×2×2×3 and which is 2³×3. We then select a random value of a and which is between 1 and (n−1). We may have a prime if one of these is true:
and where r is a value between 0 and s−1. For example, if we take n=61, then (n−1)=60. This can be represented as: 2²×15, thus s=2 and d=15. Let’s select a=5, so we get:
This does not pass the first test, so let’s try:
and which is equal to −1 (mod 61). It may thus be a prime.
Now we will try n=719 and where (n−1)=718. (n−1)=2×359, and thus s=1 and d=359. Let’s…
