# Probablistic primality test (Miller-Rabin)

Page 1 of 1

## 3 Replies - 1975 Views - Last Post: 22 December 2011 - 12:37 PM

### #1 Karel-Lodewijk Reputation: 454
• Posts: 864
• Joined: 17-March 11

# Probablistic primality test (Miller-Rabin)

Posted 14 December 2011 - 05:05 AM

Description: This is an implementation of the Miller-Rabin probabilistic primality test (http://en.wikipedia.org/wiki/Miller-Rabin_primality_test). If the algorithm says a number is not prime, then it is definitely not prime. If the algorithm however says a number is prime, then it is prime with probability 1-(0.25^k). With K=20 as declared on top, this probability is 99.99999999990905%. Probablistic primality tests are used to find very large primes such as primes that are used in public key asymmetric cryptography. This is a straight translation of the pseudo code on wikipedia.
```K = 20

def is_probably_prime?(n)
#fast calculation of base^exponent % modulus
def modular_pow(base, exponent, modulus)
result = 1
while exponent > 0 do
if (exponent & 1) == 1 then
result = (result * base) % modulus
end
exponent = exponent >> 1
base = (base * base) % modulus
end
return result
end

if n < 5 then
if n == 2 || n == 3 then
return true
else
return false
end
end

#writing n-1 as 2^s * d (d odd)
s = 0
d = n - 1
while (d%2 == 0) do
d=d/2
s=s+1
end

K.times do
a = Random.rand(n-4) + 2 #random number on (2,n-2)
x = modular_pow(a,d,n)
if (x==1 || x==n-1) then
next
end
for r in 1 .. s-1 do
x = modular_pow(x,2,n)
if x == 1 then
return false
end
if x == n-1 then
stop = true
break;
end
end
if (stop) then
next;
end
return false
end
return true;
end
```

Is This A Good Question/Topic? 0

## Replies To: Probablistic primality test (Miller-Rabin)

### #2 Karel-Lodewijk Reputation: 454
• Posts: 864
• Joined: 17-March 11

## Re: Probablistic primality test (Miller-Rabin)

Posted 22 December 2011 - 12:10 PM

Note that there is also a probabilistic version of this algorithm. Instead of random bases a as in this snippet, use 2, 3, 5, 7, 11, 13, and 17. It is proven that for these bases the test works for all numbers n < 341,550,071,728,321, resulting in a very fast deterministic test in the [0 341,550,071,728,321) range.

### #3 Karel-Lodewijk Reputation: 454
• Posts: 864
• Joined: 17-March 11

## Re: Probablistic primality test (Miller-Rabin)

Posted 22 December 2011 - 12:11 PM

I meant to say deterministic version in the last comment of course.

### #4 Karel-Lodewijk Reputation: 454
• Posts: 864
• Joined: 17-March 11

## Re: Probablistic primality test (Miller-Rabin)

Posted 22 December 2011 - 12:37 PM

It can also be used as a true deterministic primality test if you check for all bases a in the range [2, min(n-1, (2*log(n))**2).floor]. This result does depend on the yet unproven generalized Riemann hypothesis, wikipedia has the details.

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }