

 This page uses content from Wikipedia. The original article was at Miller–Rabin primality test. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)



The Miller–Rabin primality test or Rabin–Miller primality test is a primality test: an algorithm which determines whether a given number is prime or not.

The algorithm, as modified by Michael O. Rabin to avoid the generalized Riemann hypothesis, is a probabilistic algorithm.

The pseudocode, from Wikipedia is:

Input: n > 2, an odd integer to be tested for primality;
       k, a parameter that determines the accuracy of the test
Output: composite if n is composite, otherwise probably prime
write n − 1 as 2s·d with d odd by factoring powers of 2 from n − 1
LOOP: repeat k times:
   pick a randomly in the range [2, n − 1]
   x ← ad mod n
   if x = 1 or x = n − 1 then do next LOOP
   repeat s − 1 times:
      x ← x2 mod n
      if x = 1 then return composite
      if x = n − 1 then do next LOOP
   return composite
return probably prime

 The nature of the test involves big numbers, so the use of "big numbers" libraries (or similar features of the language of your choice) are suggested, but not mandatory.
 Deterministic variants of the test exist and can be implemented as extra (not mandatory to complete the task)


 
 
 
int pow_mod(int m, int i,int mod){
	int x=1,y=m%mod;
	while(i){
		if(i&1) x = x*y%mod;
		y =  y*y%mod;
		i>>=1;
	}
	return x;
}
bool mr_pass(int a, int s, int d, int n){
    int a_to_power = pow_mod(a, d, n);
    if(a_to_power == 1)
        return true;
    for(int i = 0; i< s - 1; i++){
        if(a_to_power == n - 1)
            return true;
        a_to_power = (a_to_power * a_to_power) % n;
    }
    return a_to_power == n - 1;
}
 
int is_prime(int n){
	array(int) prime ;
	prime = ({2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 47, 53, 59, 61, 67, 71, 79, 83, 89, 97, 101, 103, 107, 109, 113});
    int idx =  search( prime, n);
    if( n < 113 && n == prime[idx] ){
        return 1;
    }
    if(n < 2047) prime = ({2, 3});
    if(n < 1373653)prime = ({2, 3});
    if(n < 9080191)prime = ({31, 73});
    if(n < 25326001)prime = ({2, 3, 5});
    if(n < 3215031751)prime = ({2, 3, 5, 7});
    if(n < 4759123141)prime = ({2, 7, 61});
    if(n < 1122004669633)prime = ({2, 13, 23, 1662803});
    if(n < 2152302898747)prime = ({2, 3, 5, 7, 11});
    if(n < 3474749660383)prime = ({2, 3, 5, 7, 11, 13});
    if(n < 341550071728321)prime = ({2, 3, 5, 7, 11, 13, 17});
    if(n < 3825123056546413051)prime = ({2, 3, 5, 7, 11, 13, 17, 19, 23});
    if(n < 18446744073709551616)prime = ({2, 3, 5, 7, 11, 13, 17, 19, 23, 29});
    if(n < 318665857834031151167461)prime = ({2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31});
    if(n < 3317044064679887385961981)prime = ({2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37});
    else prime = ({2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 47, 53, 59, 61, 67, 71});
    int d = n - 1;
    int s = 0;
    while(d % 2 == 0){
    	d >>= 1;
    	s += 1;
    }
    for (int repeat=0 ; repeat < sizeof(prime); repeat++){
        int a = prime[repeat];
        if(!mr_pass(a, s, d, n)){
            return 0;
        }
    }
    return 1;
}
int main() {
	array(int) lists;
	lists =({35201546659608842026088328007565866231962578784643756647773109869245232364730066609837018108561065242031153677,
10513733234846849736873637829838635104309714688896631127438692162131857778044158273164093838937083421380041997,
24684249032065892333066123534168930441269525239006410135714283699648991959894332868446109170827166448301044689,
76921421106760125285550929240903354966370431827792714920086011488103952094969175731459908117375995349245839343,
32998886283809577512914881459957314326750856532546837122557861905096711274255431870995137546575954361422085081,
30925729459015376480470394633122420870296099995740154747268426836472045107181955644451858184784072167623952123,
14083359469338511572632447718747493405040362318205860500297736061630222431052998057250747900577940212317413063,
10422980533212493227764163121880874101060283221003967986026457372472702684601194916229693974417851408689550781,
36261430139487433507414165833468680972181038593593271409697364115931523786727274410257181186996611100786935727,
15579763548573297857414066649875054392128789371879472432457450095645164702139048181789700140949438093329334293});
	for(int i=0;i<sizeof(lists);i++){
		int n = lists[i];
		int chk = is_prime(n);
		if(chk == 1) write(sprintf("%d %s\n",n,"PRIME"));
		else write(sprintf("%d %s\n",n,"COMPOSIT"));
	}
}
 
TEST
 
35201546659608842026088328007565866231962578784643756647773109869245232364730066609837018108561065242031153677 PRIME
10513733234846849736873637829838635104309714688896631127438692162131857778044158273164093838937083421380041997 PRIME
24684249032065892333066123534168930441269525239006410135714283699648991959894332868446109170827166448301044689 PRIME
76921421106760125285550929240903354966370431827792714920086011488103952094969175731459908117375995349245839343 PRIME
32998886283809577512914881459957314326750856532546837122557861905096711274255431870995137546575954361422085081 PRIME
30925729459015376480470394633122420870296099995740154747268426836472045107181955644451858184784072167623952123 PRIME
14083359469338511572632447718747493405040362318205860500297736061630222431052998057250747900577940212317413063 PRIME
10422980533212493227764163121880874101060283221003967986026457372472702684601194916229693974417851408689550781 PRIME
36261430139487433507414165833468680972181038593593271409697364115931523786727274410257181186996611100786935727 PRIME
15579763548573297857414066649875054392128789371879472432457450095645164702139048181789700140949438093329334293 PRIME
 