Prime Checking Exposed-MiIler Rabin Algorithm

Miller Rabin Primality Test


Miller Rabin Primality Test is a probabilistic test to check whether a number is a prime or not. It relies on an equality or set of equalities that hold true for prime values, then checks whether or not they hold for a number that we want to test for primality.

Theory

1> Fermat’s little theorem states that if p is a prime and 1 ≤ a < p then
2> If p is a prime and or then or
3> If n is an odd prime then n-1 is an even number and can be written as . By Fermat’s Little Theorem either or for some 1 ≤ r ≤  s-1.
4> The Miller–Rabin primality test is based on the contrapositive of the above claim. That is, if we can find an a such that and for all 1 ≤ r ≤  s-1 then a is witness of compositeness of n and we can say n is not a prime. Otherwise, n may be a prime.
5> We test our number N for some random a and either declare that N is definitely a composite or probably a prime. The probably that a composite number is returned as prime after k itereations is

Algorithm

Input :A number N to be tested and a variable iteration-the number
of 'a' for which algorithm will test N.
Output :0 if N is definitely a composite and 1 if N is probably a prime.

Write N as
For each iteration
Pick a random a in [1,N-1]
x = mod n
if x =1 or x = n-1
Next iteration
for r = 1 to s-1
x = mod n
if x = 1
return false
if x = N-1
Next iteration

return true

public static class RabinMiller
{
public static bool isPrime(int p)
{
if(p<2)
{
return false;
}
if(p!=2 && p%2==0)
{
return false;
}
int s=p-1;
while(s%2==0)
{
s>>=1;
}
for (int i = 1; i < 11;i++)
{
Random r = new Random();
double a = r.Next((int)p - 1) + 1;
int temp = s;
int mod = (int)Math.Pow(a, (double)temp) % p;
while(temp!=p-1 && mod!=1 && mod!=p-1)
{
mod=(mod*mod)%p;
temp=temp*2;
}
if(mod!=p-1 && temp%2==0)
{
return false;
}
}
return true;
}
}