- \(a^{d} \pmod{n} \equiv 1\)
- \(a^{2^r \cdot d} \equiv -1 \pmod n\)
and where \(r\) is a value between 0 and \(s-1\). In this case, we will calculate the value of (n-1) and then determine \(2^s d\) for \(s\) and \(d\).
Miller-Rabin Test for Primes
[Primes Home][Home]
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 the following is true:
and where \(r\) is a value between 0 and \(s-1\). In this case, we will calculate the value of (n-1) and then determine \(2^s d\) for \(s\) and \(d\). |
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:
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.
The following is some sample code:
import libnum import sys n=909 if (len(sys.argv)>1): n=int(sys.argv[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 a=7 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")