A Bit of Miller and Rabin

A Bit of Miller and Rabin

Before 1976, we struggled to quickly and effectively test if a number was a prime number. Up to that point, we used Euler and Solovay-Strassen tests, and which struggled to effectively find some prime numbers. For example, both Euler and Solovay-Strassen often identify Carmichael numbers as prime numbers [here]. An example of a Carmichael number is 561, and it will pass the Euler and Solovay-Strassen tests, and be identified as a prime number (even though it is a compositive number, and made up of three factors).

Within a year, Rivest, Shamir and Adleman came up with a new way of using prime numbers to protect data — the RSA method. The method they used to find prime numbers was the Miller-Rabin method.

Michael O. Rabin was born in 1931 in Germany. In the 1960s he worked in the University of California and MIT, and then moved on to a Professorship at Harvard University. Finally, in 1981, he became a professor at the Hebrew University and has worked there ever since. Garry L Millier is a professor at Carnegie Mellon University. In 1976 he came up with a new method of determining primality [1]. It was based on the extended Riemann hypothesis [here]:

Then, in 1980, Rabin modified it with an unconditional probabilistic algorithm [2][here]:

Combined they produced the Miller-Rabin test. It is now 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 ²³×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 select a=7, and so the first test is:

This has worked, so it is a possible prime. Let’s not try a=9:

and so we have more proof of it being a prime number. The code is [here]:

import random
import sys
import libnum

n=97

if (len(sys.argv)>1):
	n=int(sys.argv[1])

a=random.randint(0,n)

res=libnum.factorize(n-1)

if n == 2: 
  print ("2")
  sys.exit()

if n % 2 == 0: 
  print ("Not prime")
  sys.exit()

print (f"n={n}\n")

s = 0
d = n-1
while True:
  quotient, remainder = divmod(d, 2)
  if remainder == 1:
    break
  s += 1
  d = quotient

r=s-1

print (f"(n-1)={n-1} = 2^{s} x {d}")

print (f"s={s}, d={d}")
print (f"a={a}, r={r}")

prime=False

if (pow(a,d,n)==1):
  print ("\nTest 1. It may be prime (a^d (mod n) = 1)")
  prime=True

if (pow(a,2**r*d,n)==(n-1)):
  print ("\nTest 2. It may be prime (a^{2^r d} (mod n) == n-1)")
  prime =True

if (prime==False): print("Not a prime")

A sample run with an unsafe value is [here]:

n=31

(n-1)=30 = 2^1 x 15
s=1, d=15
a=3, r=0

Test 2. It may be prime (a^{2^r d} (mod n) == n-1)

Here are some tests using the M-R primality test:

• Is 5 prime?. Try
• Is 7919 prime?. Try
• Is 858,599,509 prime?. Try
• Is 982,451,653 prime?. Try
• Is 982,451,652 prime?. Try
• Is 643808006…,153 prime (210 digits)?. Try
• Is 643808006…,152 prime (210 digits)?. Try
• Is 4494179990..,163 prime (210 digits)?. Try
• Is 4494179990..,162 prime (210 digits)?. Try
• Is 23097…426570593 prime (210 digits)?. Try
• Is 23097…426570595 prime (210 digits)?. Try
• Is 5521712….5385789993 prime (220 digits)?. Try
• Is 56125680…531131327771 prime (230 digits)?. Try

Conclusions

[1] Miller, G. L. (1976). Riemann’s hypothesis and tests for primality. Journal of computer and system sciences, 13(3), 300–317.

[2] Rabin, M. O. (1980). Probabilistic algorithm for testing primality. Journal of number theory, 12(1), 128–138.