- \(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\).
Miller-Rabin Test for Primes in C#
[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 have a prime if:
and where \(r\) is a value between 0 and \(s-1\). |
We live in a digitally flawed 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 at 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.
One of his classic papers [1] built on the work of Gary Miller [2]. The paper has since provided the core method of generating prime numbers for the RSA method. Typically we generate an odd random number with a given number of bits and then test if it is a prime number. If not, we can keep adding two to the value until we reach a prime number.
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^Sd\)
For example, if \(n\) is 25, (\(n−1\)) will be 24, and which is 2×2×2×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} = 60 \pmod {61} \)
This does not pass the first test, so let’s try:
\( 5^{ {2^1} \times 15} = 60 \pmod {61} \)
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:
\( 7^{359} = 1 \pmod {791} \)
This has worked, so it is a possible prime. Let’s not try a=9:
\( 9^{359} = 1 \pmod {791} \)
and so we have more proof of it being a prime number.
In the Miller-Rabin test, we perform k trials. If any of these trails returns a false, the value is not a prime number (and is a composite. If it returns a true, it is probably prime. First, we have a number to test (n) and produce a random number (a) and then compute d to solve (and where r is a value greater than 1):
\(=2^d \times r + 1\)
We then compute:
\( x= a^d \pmod n\)
If this is 1 or -1, we return a true value for a prime number. This is coded as:
while (true) { var quotient = BigInteger.Divide(d,new BigInteger(2)); var remainder=d % 2; if (remainder == BigInteger.One) { break; } s += 1; d = quotient; } var prime=false; if (BigInteger.ModPow(a,d,n)==1) { Console.WriteLine ("\nTest 1. It may be prime (a^d (mod n) = 1)"); prime=true; }
Next we keep squaring the value of \(x \pmod n\) while the value of d is less than (\(n−1\)) — and where we double \(d\) in each test. The code is:
var a=getRandom(n); var r=s-1; if (BigInteger.ModPow(a,BigInteger.Pow(2,r)*d,n)==(n-1)) { Console.WriteLine ("\nTest 2. It may be prime (a^{2^r d} (mod n) == n-1)"); prime =true; }
The code is then:
namespace dotnet_rabin { using System.Numerics; using System.Reflection.Metadata; class Program { public static BigInteger getRandom(BigInteger n){ var length=n.GetBitLength()/8+1; Random random = new Random(); byte[] data = new byte[length]; random.NextBytes(data); var r=new BigInteger(data)%n; if (r.Sign==-1) r=-r; if (r==0) r=2; return r; } static void Main(string[] args) { var nval="997"; if (args.Length >0) nval=args[0]; var n= BigInteger.Parse(nval); if (n == 2) { Console.WriteLine ("2"); return; } if ((n % 2) == BigInteger.Zero) { Console.WriteLine ("{0} is not prime",n); return; } var s = 0; var d = n-1; while (true) { var quotient = BigInteger.Divide(d,new BigInteger(2)); var remainder=d % 2; if (remainder == BigInteger.One) { break; } s += 1; d = quotient; } var a=getRandom(n); var r=s-1; Console.WriteLine ("(n-1)=({0}-1) = 2^{1} x {2}",n,s,d); Console.WriteLine ("s={0}, d={1}",s,d); Console.WriteLine ("a={0}, r={1}",a,r); var prime=false; if (BigInteger.ModPow(a,d,n)==1) { Console.WriteLine ("\nTest 1. It may be prime (a^d (mod n) = 1)"); prime=true; } if (BigInteger.ModPow(a,BigInteger.Pow(2,r)*d,n)==(n-1)) { Console.WriteLine ("\nTest 2. It may be prime (a^{2^r d} (mod n) == n-1)"); prime =true; } if (prime==false) Console.WriteLine ("{0} is not a prime",n); else Console.WriteLine ("{0} is a prime",n); } } }
A sample run is:
(n-1)=(19-1) = 2^1 x 9 s=1, d=9 a=7, r=0 Test 1. It may be prime (a^d (mod n) = 1) 19 is a prime
[1] Rabin, M. O. (1980). Probabilistic algorithm for testing primality. Journal of number theory, 12(1), 128–138.
[2] Miller, G. L. (1976). Riemann’s hypothesis and tests for primality. Journal of computer and system sciences, 13(3), 300–31.