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?