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

#define DIM 64

int binario(int);
long int esponenziazione(int,int,int);
long int potenza(int, int);

int base, esponente, modulo, n, k, s, a, i, j, l, esito;
int vet[DIM];
long int riduz, p, t, aux;

void main()
{
   srand(time(NULL));
   for(i=0;i<DIM;i++)
   {
      vet[i]=0;
   }
   do
   {
      printf("Introduci due numeri naturali n,k > 1: ");
      scanf("%d %d", &n, &k);
   } while (n<2 || k<2);
   esito=0;
   while (esito==0)
   {
      long int limite = potenza(10,n-1);
      do
      {
         p = limite+rand()%(9*limite);
      } while (p%2 == 0);
      printf("Il test verra' effettuato sul valore %d\n", p);
      s = 0;
      t = p-1;
      while (t%2 == 0)
      {
         t = (t)/2;
         s++;
      }
      printf("T-S = %d-%d\n", t,s);
      l = binario(t);
      i=1;
      while (i<=k && esito==0)
      {
         a = 2+rand()%(p-2);
         aux = esponenziazione(a,t,p);
         printf("Questo e' AUX al primo tentativo: %d\n", aux);
         if ((aux == 1) || (aux == p-1))
         {
            esito=1;
            printf("Esito e' 1 al primo tentativo\n");
         }
         else
         {
            j = 2;
            while ((j<=s) && (esito == 0))
           {
              aux = (potenza(aux,2))%p;
              printf("Questo e' AUX al %d tentativo: %d\n", j, aux);
              if (aux == p-1)
             {
                esito=1;
                printf("Esito e' 1 al %d tentativo\n",j);
             }
             j++;
           }
        }
        if (esito == 0)
        {
           printf("Il valore %d per a=%d e' non primo.\n", p, a);
        }
        else
        {
           printf("Il valore %d per a=%d e' primo.\n", p, a);
        }
        i++;
      }
      getchar();
   }
getchar();
}


int binario(int esponente)
{
   int i=0;
   while(esponente != 0)
   {
      vet[i] = esponente%2;
      esponente=esponente/2;
      i++;
   }
   return (i-1);
}


long int potenza(int b, int e)
{
   long int pot=b;

   if (e == 0)
   {
      pot=1;
   }
   else if (e > 1)
   {
      while (e>1)
     {
        pot = pot*b;
        e--;
     }
   }
   return pot;
}


long int esponenziazione(int base, int esponente, int modulo)
{
   int y=1;
   int i=l;
   while (i>=0)
   {
      y = (potenza(y,2)*potenza(base,vet[i]))%modulo;
      i--;
   }
   return y;
}