Code:

#include <stdio.h>
#include <math.h>
int primetest(int n){
int temp = n,i;
for(i = sqrt(n);i>=2;i--){
if(!(temp%i))
return 1;
}
return 0;
}
int MOD(int x,int y,int n){
unsigned long i,j;
if(x>=1000){
i=x/1000;
j=x%1000;
return (((i*y)%n)*1000+(j*y))%n;
}
else if(y>=1000){
i=y/1000;
j=y%1000;
return (((i*x)%n)*1000+(j*x))%n;
}
else{
return (x*y)%n;
}
}
int Fermat_test(int N,int a){
int i,temp,bit=0,binary[20],n,mod;
unsigned long pm[20];
if(primetest(N)){
n=N;
N=N-1;
while (N!=0){
bit++;
i=N%2;
binary[bit]=i;
N=N/2;
}
pm[0]=a%n;
mod=pow(a,binary[1]);
for(i=1;i<=bit-1;i++){
pm[i]=MOD(pm[i-1],pm[i-1],n);
if(binary[i+1]!=0){
mod=MOD(mod,pm[i],n);
}
}
if(mod==1){
return 1;
}
else{
return 0;
}
}
}
main()
{
int a,N,i;
FILE * fp;
fp=fopen("c:\\output.txt","w+");
printf("Enter the value of a: <=13 ");
fflush(stdout);
scanf("%d",&a);
for(i=a+1;i<=1000000;i++){
if(Fermat_test(i,a)==1){
fprintf(fp,"%d\n",i);
}
}
return 0;
}

we only consider this part of our program:

Code:

if(primetest(N)){
n=N;
N=N-1;
while (N!=0){
bit++;
i=N%2;
binary[bit]=i;
N=N/2;
}
pm[0]=a%n;
mod=pow(a,binary[1]);
for(i=1;i<=bit-1;i++){
pm[i]=MOD(pm[i-1],pm[i-1],n);
if(binary[i+1]!=0){
mod=MOD(mod,pm[i],n);
}
}
}

what is the time complexity of this part? They asked about a function O(f(N))= g(N) and discuss the ratio g(N)/f(N) as N goes to infinity.