/*--------------------------------------------------------------
 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");
   }

Per scaricare il sorgente C fare clic qui col destro e scegliere "Salva oggetto con nome".