/*--------------------------------------------------------------
               Test di primalita' di Miller

           (implementato da Francesco Turchini)
 ---------------------------------------------------------------

 Attenzione: in questo programma usiamo i soli tipi predefinti del
	     C. Per x del tipo long, il prodotto x*x mod n e'
	     corretto solo per

                x < 46.340 = sqrt(2.147.483.647 = maxLongint).

             Non e' tuttavia difficile modificare l'algoritmo
             includendo la definizione di tipi numerici di
             dimensioni maggiori di longint, usando ad esempio
             record o array. 
*/


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define DIM 16
#define NT 10


long n;
long n2[DIM];
long b;
int sw;
int i;

int miller;

void crean2(long a)
{
 int c;
 for (c=0;c<DIM;c++)
 {
  n2[c]= a % 2;
  a=a / 2;
 }
}



void test(long a,long m)
{
 long x;
 long d;
 int c;

 miller=0;

 d=1;
 c=DIM;

 while(c>=0)
 {
  x=d;
  d=(d*d)%m;
  if ((d==1)&&(x!=1)&&(x!=m-1)) miller=1;
  if (n2[c]==1) d=(d*b)%m;
  c--;
 }

 if (d!=1) miller=1;
}



main()
{
 int numeri=0;
 int primi=0;


 n=1;

 printf("TEST DI PRIMALITA' DI MILLER-RABIN VERSIONE C \n");
 printf("     (realizzato con Microsoft Quick C) \n");
 printf("\n");
 printf("Digitare 0 per uscire.");
 printf("\n");

 while(n!=0)
 {
  numeri++;
  srand((unsigned)time( NULL ) );

  printf("Inserisci il numero da testare: ");
  scanf("%d",&n);
  if(n!=0)
  {
   crean2(n-1);
   sw=0;
   i=0;
   b=0;
   while((i<NT)&&(sw==0))
   {
    while(b==0)
    {
     b=((rand() * n) / RAND_MAX);
    }
    test(b,n);
    if ((sw==0)&&(miller==1)) sw=1;
     else if ((sw==0)&&(miller==0)) sw=0;
      else if ((sw==1)&&(miller==0)) sw=1;
       else sw=1;
    i++;
   }
   if (sw==0) 
   { 
	printf("Primo con margine di errore inferiore a 2^-%d \n", NT);
	primi++;
   }
   else printf("Composto \n");
  }
 }
 printf("Numeri testati: %d \n",numeri-1);
 printf("Numeri primi: %d \n",primi);
 scanf("%d");
}