Test de primarité

temoinFermat.c

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

#define NB_TEMOINS_FERMAT 5

/***********************************************/

long pgcd(long a, long b)
{
  if (b == 0)
    return a;
  else
    return pgcd(b, a%b);
}

/***********************************************/

int divides(long a, long b)
{
  return !(b%a);
}

/***********************************************/

long modExp(long base, long exp, long mod)
{
  base %= mod;
  if (exp == 0)
    return 1;
  if (divides(2, exp))
    return modExp(base*base%mod, exp/2, mod) % mod;
  else
    return modExp(base, exp - 1, mod) % mod * base % mod;
}

/***********************************************/

int testFermat(long n)
{
  int i, a;
  for(i = 1 ; i <= NB_TEMOINS_FERMAT ; i++)
    {
      a = rand();
      if (pgcd(a, n) == 1)
	{
	  if (modExp(a, n-1, n) != 1)	    
	    return 0;
	}
      else
	{
	  if (!divides(n, a))
	    return 0;
	}
    }
  return 1;
}

/***********************************************/

long findPrime()
{
  long n;
  do
    {
      n = rand();
    }
  while(!testFermat(n));
  return n;
}

/***********************************************/

long isPrime(long n)
{
  long i = 2;
  while(i*i <= n)
    {
      if (divides(i, n))
	return 0;
      i++;
    }
  return 1;
}

/***********************************************/

int main()
{
  long n;
  srand(time(NULL));
  while(1)
    {
      n  = findPrime();
      printf("%ld ", n);
      if (isPrime(n))
	printf("(premier)\n");
      else
	printf("(PAS PREMIER)\n");
}
  return 0;
}