[C] Implementare il test di Rabin-Miller

Il test di Miller-Rabin è un test che verifica se un numero è primo.Ecco il codice:

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
long long int pot(long long int b, unsigned long long int e,long long int mod)
{
    long long int ris = 1;     
    b=b%mod;
    while(e> 0)
    {
        if (e & 1){
        	ris = (ris*b)%mod;
        }
        e=e>>1;
        b=(b*b)%mod;  
    }
    return ris;
}
int rabin(long long int num,int it){
	long long int d=num-1,x,a;
	int r,i=0,flag=0;
	if(!(num & 1)){
		return 0;
	}
	while(!(d & 1)){
		r++;
		d=d>>1;
	}
	srand((unsigned)time(NULL));
	while(it!=0){
		a=rand()%(num-2)+2;
		x=pot(a,d,num);
		if(!(x==1 || x==num-1)){
			flag=0;
			for(i=0;i<r-1 && flag==0;i++){
				x=(x%num)*(x%num)%num;
				if(x==1){
					return 0;
				}
				if(x==num-1){
					flag++;
				}
			}
			if(flag!=1){
				return 0;
			}
		}
		it--;
	}
	return 1;
} 
int main()
{
   long long int n;
   int k=5;
   do{
   	   printf("Inserisci numero:");
	   scanf("%lld",&n);	
   }while(n<=3);
   if(rabin(n,k)){
   	   printf("\nIl numero e\' primo");
   }
   else{
   	   printf("\nIl numero non e\' primo");
   }
   return 0;
}

k è il numero di passaggi che l'algoritmo esegue.Aumentando k si avrà una maggiore sicurezza, infatti il test ha una probabilità di 1/(4^k) di restituire in output un risultato positivo anche se in realtà il numero non è primo. Pot() è una funzione che calcola velocemente(base^esponente)modulo x. Scrivere x=x>>1 è uguale a scrivere x=x/2 oppure scrivere x & 1 è uguale a scrivere x%2==1.


Fino a quale numero riuscite ad arrivare?