Test de primalité B: Miller-Rabin 32 bits

Télécharger le projet
Commenter

Description

Bonjour,

Le test de primalité de Miller-Rabin est probabiliste.
Il permet de dire si un entier est composé ou (très) probablement premier.
La probabilité de ne pas être (réellement) premier peut être rendue aussi petite que l'on veut.

En fait, il faudrait plutôt l'appeler test de non-primalité.

Pomerance, Selfridge, Wagstaff et Jaeschke ont vérifié qu'en acceptant l'hypothèse de Riemann généralisée, les tests suivants sont suffisants:

N < 1'373'653: tests avec a = 2,3;
N < 9'080'191: tests avec a = 31,73;
N < 4'759'123'141: tests avec a = 2,7,61;
N < 2'152'302'898'747: tests avec a = 2,3,5,7,11;
N < 3'474'749'660'383: tests avec a = 2,3,5,7,11,13;
N < 341'550'071'728'321: tests avec a = 2,3,5,7,11,13,17;
N < 3'825'123'056'546'413'051: tests avec a = 2,3,5,7,11,13,17,19,23;
N < 318'665'857'834'031'151'167'461: tests avec a = 2,3,5,7,11,13,17,19,23,29,31,37;

Nous allons utiliser ces résultats pour rendre le test de primalité de Miller-Rabin déterministe.

Rappelons que 2¹⁶ = 65'536, 2³² = 4'294'967'296 et 2⁶⁴ = 18'446'744'073'709'551'616.

Et pour le moment, limitons-nous aux entiers sur 32 bits (n < 2³²).

La version allemande WikipediA: Miller-Rabin-Test donne la fonction mrt suivante qui nous permet de traiter des entiers < 2³²: 
bool mrt (const uint32_t n, const uint32_t a) { // n ungerade, 1 < a < n-1
   const uint32_t n1 = n - 1;
   uint32_t d = n1 >> 1;
   int j = 1;
   while ((d & 1) == 0) d >>= 1, ++j;
   uint64_t t = a, p = a;
   while (d >>= 1) { //square and multiply: a^d mod n
      p = p*p % n;
      if (d & 1) t = t*p % n;
   }
   if (t == 1 || t == n1) return true; // n ist wahrscheinlich prim
   for (int k=1 ; k<j ; ++k) {
      t = t*t % n;
      if (t == n1) return true;
      if (t <= 1) break;
   }
   return false; // n ist nicht prim
} // copié de https://de.wikipedia.org/wiki/Miller-Rabin-Test

Pour tester des entiers < 1'373'653 (>2¹⁶), on appellera cet fonction jusqu'à deux fois avec a = 2,3.
Et pour les entiers < 4'759'123'141 (>2³²) jusqu'à trois fois avec a=2,7,61: 
bool isPrimeB1(uint32_t N) { // N < 1'373'653
  if (N<1024) return isPrimeA3(N); //  N <= 1024
  if ((N&1)==0) return false; // N pair
  return mrt(N, 2) ? mrt(N, 3) : false;
}
Le test (N<1024) est assez arbitraire. 

bool isPrimeB2(uint32_t N) { // N sur 32 bits
  if (N<=61) return isPrimeA3(N); //  N <= 61
  if ((N&1)==0) return false; // N pair
  return mrt(N, 2) ? (mrt(N, 7) ? mrt(N, 61) : false) : false;
}

Les résultats ci-dessous montrent que Miller-Rabin est plus lent que isPrimeA3 pour les entiers sur 16 bits.
Adaptons la fonction d'appel: 
bool isPrimeB3(uint32_t N) { // N sur 32 bits
  if (N<=65535) return isPrimeA3(N); // N <= 65'535 (entiers 16 bits)
  if ((N&1)==0) return false; // N pair
  if (N<1373653) return mrt(N, 2) ? mrt(N, 3) : false; // N < 1'373'653
  return mrt(N, 2) ? (mrt(N, 7) ? mrt(N, 61) : false) : false;
}

Résultats obtenus en exécutant PrimeB.cpp:

Tests de primalité Miller-Rabin:

isPrimeA3: (1'000'000 nombres entre 0 et 65535)
  np = 99600; 43 ms.
isPrimeB1: (1'000'000 nombres entre 0 et 65535)
  np = 99600; 117 ms.
isPrimeB2: (1'000'000 nombres entre 0 et 65535)
  np = 99600; 138 ms.
isPrimeB3: (1'000'000 nombres entre 0 et 65535)
  np = 99600; 36 ms.
isPrimeA3: (100'000 nombres entre 0 et 4294967295)
  np = 4739; 102 ms.
isPrimeB2: (100'000 nombres entre 0 et 4294967295)
  np = 4739; 25 ms.
isPrimeB3: (100'000 nombres entre 0 et 4294967295)
  np = 4739; 26 ms.

Nous constatons que isPrimeB3 est rapide pour les deux ensembles d'entiers.

Pour les nombres 32 bits, Miller-Rabin est bien quatre fois plus rapide que la meilleure des méthodes simples.
Le prochain article va-t-il monter que ce rapport va encore s'accentuer avec des entiers plus grands ?


Remarque sur l'hypothèse de Riemann généralisée.
C'est une des plus importantes conjectures des mathématiques !
Supposons cette hypothèse vraie et considérons les affirmations de Pomerance, Selfridge, Wagstaff et Jaeschke ci-dessus vérifiées.
D'après la démonstration par l'absurde, si quelqu'un trouve un contre-exemple (nombre prétendu premier qui ne l'est pas), on aurait démontré que l'hypothèse en question est fausse !
C'est un "risque" que je prends volontiers.
Qu'en pensent les mathématiciens spécialistes du domaine ?


Quelques liens:
WikipediA: Miller-Rabin-Test.
WikipediA: Miller–Rabin primality test.
WikipédiA: Test de primalité de Miller-Rabin.
CodeS-SourceS: Test de primalité A: Méthodes simples.
CodeS-SourceS: Premiers.
CodeS-SourceS: Test de primalité de Miller-Rabin.
CodeS-SourceS: factorisation et test de primalité 32 bits ultra optimisé.
CodeS-SourceS: Teste si un tres grand nombre (plusieurs milliers de chiffres) est premier avec ntl et miller-rabin.
CodeS-SourceS: Test de primalité optimisé.
C++ Program to Implement Miller Rabin Primality Test
Bibm@th.net: Nombres premiers


Bonne lecture ...
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (William VOIROL)