MTech VTU Advanced Algorithm Lab (2nd sem)
Design, develop, and write a program to
implement a Monte Carlo algorithm to
test the primality of a given
integer and determine its performance.
#include<stdio.h>
#include<stdlib.h>
int Modular_Exponentiation(int, int, int);
void Binary(int, int *, int *);
int main()
{
int n, res;
printf("\n Enter a
no n:");
scanf("%d", &n);
if(n <= 0)
{
printf("\n
Please enter a +ve number!!!");
exit(0);
}
res = Modular_Exponentiation(2,n-1,n);
if(n == 1)
printf("\n
%d is prime!!!", n);
else if((res % n) == 1)
printf("\n
%d is prime!!!", n);
else
printf("\n
%d is not prime!!!", n);
return 0;
}
int Modular_Exponentiation(int a, int b, int n)
{
int c, d, bin[20] = {0},
k, i;
c=0, d=1;
Binary(b, bin, &k);
for(i = k; i >= 0; i--)
{
c = 2*c;
d = (d*d) % n;
if(bin[i] ==
1)
{
c++;
d
= (d*a) % n;
}
printf("\n
i=%d, bi=%d, c=%d, d=%d", i, bin[i], c, d);
}
return d;
}
void Binary(int b, int *bin, int *k)
{
int i = 0, n = b;
*k = 0;
*bin = 0;
while(b != 0)
{
bin[i] = b %
2;
*k = *k+1;
b /= 2;
i++;
}
*k = *k-1;
printf("\n Binary
equivalent of %d is:", n);
for(i = *k; i >= 0; printf("%5d",
bin[i--]) );
}
Output:
Case 1:
Enter a no n: 5
Binary equivalent of 4 is: 1
0 0
i=2, bi=1, c=1, d=2
i=1, bi=0, c=2, d=4
i=0, bi=0, c=4, d=1
5 is prime!!!
Case 2:
Enter a no n:9
Binary equivalent of 8 is: 1
0 0 0
i=3, bi=1, c=1, d=2
i=2, bi=0, c=2, d=4
i=1, bi=0, c=4, d=7
i=0, bi=0, c=8, d=4
9 is not prime!!!
