Miller-Rabin Test for PrimesMiller-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 \(n-1 = 2^s d\). For example, if \(n\) is 25, \((n-1)\) will be 24, and which is \(2 \times 2 \times 2 \times 3\) and which is \(2^3 \times 3\). We then select a random value of \(a\) and which is between 1 and \((n-1)\). We have a prime if:
and where \(r\) is a value between 0 and \(s-1\). |
Examples
The following are some examples:
- 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...,6,769,180,017,646,161,851,573,147,596,390,153 prime (210 digits)?. Try
- Is 643808006...,6,769,180,017,646,161,851,573,147,596,390,152 prime (210 digits)?. Try
- Is 4494179990..9,144,354,948,751,003,607,115,263,071,543,163 prime (210 digits)?. Try
- Is 4494179990..9,144,354,948,751,003,607,115,263,071,543,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
Method
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 \(n-1 = 2^s d\). For example, if \(n\) is 25, \((n-1)\) will be 24, and which is \(2 \times 2 \times 2 \times 3\) and which is \(2^3 \times 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:
- \(a^{d} \equiv 1 \pmod{n}\)
- \(a^{2^r \cdot d} \equiv -1 \pmod n\)
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^2 \times 15\)
thus \(s=2\) and \(d=15\). Let's select \(a=5\), so we get:
\(5^{15} \pmod {61} = 60\)
This does not pass the first test, so let's try:
\(5^{2^1 \times 15} \pmod {61} = 60\)
and which is equal to \(-1 \pmod {61}\). It may thus be a prime number.
Now we will try \(n=719\) and where \(n-1=718\). \((n-1)=2 \times 359\), and thus \(s=1\) and \(d=359\). Let's select \(a=7\), and so the first test is:
\(7^{359} \pmod {791} = 1\)
This has worked, so it is a possible prime. Let's not try \(a=9\):
\(9^{359} \pmod {791} = 1\)
and so we have more proof of it being a prime number.
Code
The following is an outline of the code (based on code at https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test):
# https://asecuritysite.com/encryption/rabin import random import sys _mrpt_num_trials = 5 # number of bases to test testval=97 if (len(sys.argv)>1): testval=int(sys.argv[1]) def is_probable_prime(n): assert n >= 2 # special case 2 if n == 2: return True # ensure n is odd if n % 2 == 0: return False # write n-1 as 2**s * d # repeatedly try to divide n-1 by 2 s = 0 d = n-1 while True: quotient, remainder = divmod(d, 2) if remainder == 1: break s += 1 d = quotient assert(2**s * d == n-1) # test the base a to see whether it is a witness for the compositeness of n def try_composite(a): if pow(a, d, n) == 1: return False for i in range(s): if pow(a, 2**i * d, n) == n-1: return False return True # n is definitely composite for i in range(_mrpt_num_trials): a = random.randrange(2, n) if try_composite(a): return False return True rtn=is_probable_prime(testval) if (rtn==True): print (str(testval) + " is a prime") else: print (str(testval) + " is not a prime")