## Miller-Rabin Test for Primes[Back] Miller-Rabin Test for Primes is one of the most popular methods for testing for prime numered used in RSA. It find if n is a prime we find the largest power of 2 which divides n-1, and defined by t and d as \((n-1)/(2_{t}\). We can then pick a value of a which is less than n, so that a is relatively prime to n if any of these are true: - \(a^{d}\mod(n)=1\)
- \(a^{2^s\cdot d} \equiv 1 \bmod n\)
Where s will vary between 0 and t-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

## Code

The following is an outline of the code (based on code at https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test):

import random import sys _mrpt_num_trials = 5 # number of bases to test testval=97 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"