DATAC: Miller Rabin

{ DATAC: desperate attempt to add content } 

This and perhaps many of my next few posts will be my desperate attempts to put up some content on the blog. This time I am putting up a code for Miller Rabin, a probabilistic algorithm to check whether a number is prime. It's a complete implementation and would run if the code is directly copy pasted.

#include <cstdio>
#include <cstdlib>
#include <iostream>

using namespace std;

/*Auxiliary function to compute gcd of two numbers */
long long gcd(long long a, long long b){
        return b==0?a:gcd(b, a%b);
}

/*Auxiliary function to compute (a^b)%mod */
long long power(long long a, long long b, long long mod){
        if(b==0)
                return 1;
        long long x = power(a, b/2, mod);
        x = (x*x)%mod;
        if(b%2==1)
                x=(x*a)%mod;
        return x;
}

/*Function to check primality of num against seed*/
bool checkprime(long long num, long long seed){
        if(num%2==0)
                return false;
        long long gc = gcd(num, seed);
        if(gc>1)
                return false;
        int s;
        long long t;
        s=0; t=num-1;
        while(t%2==0){
                s++;
                t/=2;
        }
        long long a0 = power(seed, t, num);
        if(a0==1 || a0==num-1){
                return true;
        }
        while(s-1>0){
                s--;
                a0 = power(a0,2, num);
                if(a0==num-1){
                        return true;
                }
        }
        return false;
}

bool isprime(long long num){
        srand( time(NULL));
        if(num<=1)
                return false;
        if(num == 2)
                return true;
/* 50 in below line defines the accuracy, which means the algorithm will declare
a composite number to be prime with a probability of (1/(2^50)), which is quite low.
A paranoid fellow can increase it to higher value, for some more satisfaction. */
        for(int i=0;i<50; i++){
                int random = rand()%num;
                while(random<2)
                        random = rand()%num;
                bool val = checkprime(num, random);
                if(!val){
                        return false;
                }
        }
        return true;
}

int main(){
        long long num = 31815;
        int cnt=0;
        cin >> num ;
        if(isprime(num)){
               cout << num << endl;
        }
        return 0;
}

But to quote my professor Dr. Kannan Srinathan, the probability of the above code to fail is less than the probability that you hit a wall of bricks and safely go through it (without breaking the wall :P).

Selecting the code and then copy-pasting can lead to addition of stray characters in the code. To remove them, run the command:
tr -cd '\0-\176' < input > output.cpp

The program is ready to run.