witness.c

Denna kod är public domain. Om ni hittar fel eller vill ändra något i koden blir jag jätteglad om ni skickar dessa ändringar till jesper [at] fantasi [punkt] se.


/*
 * Witness r en algoritm som kontrollerar om ett tal inte kan vara
 * ett primtal. Om algoritmen svarar 'sant' r talet garanterat inte
 * ett primtal, om resultatet r 'falskt' kan det vara ett primtal.
 *
 * Algoritmen anropas med tv tal, slump och prima. prima r talet vi
 * vill testa om det kan vara ett primtal och slump r ett slumptal
 * som r lgre n prima. Eftersom slump ska vara lgre n prima och
 * det inte fungerar s bra med 0 och 1 s funkar denna implementation
 * av algoritmen inte jttebra p de lgsta talen (1 kommer att
 * klassas som "inte primtal").
 *
 * Sannorlikheten fr att witness ska svara fel r mindre n 0,5.
 * Detta innebr att om algoritmen anropas ett antal gnger i rad med
 * olika slumptal och den svarar falskt varje gng s kan man till
 * slut vara ganska sker p att det r ett primtal.  Om algoritmen
 * anropas n gnger r sannorlikheten fr att prima r ett slumptal
 * 1-2^(-n).
 *
 * Teorin bakom algoritmen hrstammar frn G. Miller (1975) och
 * M. Rabin (1980) och finns med strsta sannorlikhet att lsa i
 * nrmaste bok om kryptologi.
 */

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

static int witness(unsigned int slump, unsigned int prima)
{
   unsigned int bits = prima - 1;
   unsigned int d = 1;
   int i;

   for (i = 31; i >= 0; i--)
   {
      unsigned int x = d;
      d = (d * d) % prima;
      if (d == 1 && x != 1 && x != prima - 1)
         return 1;
      if ((bits >> i) % 2 == 1)
         d = (d * slump) % prima;
   }

   if (d != 1)
      return 1;

   return 0;
}

int main(int argc, char *argv[])
{
   unsigned int slump;
   unsigned int prima;

   if (argc != 2) 
   {
      fprintf(stderr, "Anropa programmet med det tal som ska testas.\n");
      exit(EXIT_FAILURE);
   }

   prima = (unsigned int)atoi(argv[1]);
   srand((unsigned int)time(NULL));
   slump = (unsigned int)((rand() / (double)RAND_MAX) * (prima - 3)) + 2;

   if (witness(slump,prima) == 0)
      printf("%u r troligen ett primtal\n", prima);
   else
      printf("%u r garanterat inte ett primtal\n", prima);

   return EXIT_SUCCESS;
}