Test de primalité B: Miller-Rabin 32 bits

Soyez le premier à donner votre avis sur cette source.

Vue 5 287 fois - Téléchargée 351 fois

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 ...

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Messages postés
313
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
26 mai 2020
2
Bonjour,
L'adresse : https://miller-rabin.appspot.com/ a publié un liste de seulement 7 bases : 2, 325, 9375, 28178, 450775, 9780504, 1795265022 qui suffisent pour assurer le caractère déterministe du test de Miller & Rabin jusqu'à 2^64. Ceci peut donc remplacer avantageusement les 12 bases : 2, 3, ... , 31, 37 qui sont utilisées ci-dessus, particulièrement si on souhaite traiter tous les entiers codés sur 64 bits de la même façon.
Messages postés
261
Date d'inscription
mardi 12 décembre 2006
Statut
Membre
Dernière intervention
10 juin 2019
>
Messages postés
313
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
26 mai 2020

Bonjour,

Un grand merci pour le lien Jim Sinclair.
Je vais bien sûr en tenir compte dans mes prochains articles.

Entre temps, j'ai découvert le livre Matters Computational de Jörg Arndt.
Le chapitre 39: Modular arithmetic and some number theory (page 764) semble intéressant pour le domaine qui nous préoccupe.

Le connaissez-vous ?
Messages postés
313
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
26 mai 2020
2 >
Messages postés
261
Date d'inscription
mardi 12 décembre 2006
Statut
Membre
Dernière intervention
10 juin 2019

Bonjour William Voirol,

Oui j'ai déjà vu ce livre, mais je ne l'ai pas étudié attentivement. Merci beaucoup d'avoir signalé ce paragraphe qui concerne le développement concerné ici.

Je souhaite préciser ici un petit complément d'information au sujet de l'implémentation de la liste des 7 bases de Jim Sinclair pour effectuer un test déterministe de Miller & Rabin pour les entiers codés sur 64 bits. En effet il convient de faire attention. Si le test de Miller & Rabin détecte un nombre composé, c'est mathématiquement exact. Mais c'est vrai seulement si le test est utilisé correctement. En particulier, le test unitaire : bool mrt (const uint64_t n, const uint64_t a) {} exige que le nombre a soit compris entre 1 et n-1. Mais, si on emploie ce test de manière erronée avec a égal à n ou un multiple de n, alors mulmod(a, p, n) sera nul et n sera toujours diagnostiqué en nombre composite même si n est premier ! Il est donc impératif d'avoir n > a à chaque appel de la fonction mrt() et pour cela il convient d'appeler les 7 bases de Jim Sinclair seulement après avoir fait les vérifications préliminaires nécessaires. Si les deux phases préliminaires nécessaires qui sont implémentées ci-après n'étaient pas effectuées, alors le nombre premier 299210837 qui est un diviseur de 1795265022 serait détecté en tant que nombre composé, ce qui est faux. Il est donc indispensable de faire ces deux phases préliminaires.

     
// Test de primalité de n pour n < 121
bool isSmallPrime(uint64_t n) {
    if(n < 2 || n >= 121) return false;
    uint32_t primes[] = {2, 3, 5, 7, 11, 13};
    uint32_t i = 0, p = primes[0];
    while(n >= p*p) {
        if(n % p == 0) return false;
        p = primes[i++];
    }
    return true;
}
            
// Test de primalité pour un entier codé sur 64 bits.
bool isPrime(uint64_t n) {
        
    if(n < 2) return false;
        
    if(n < 121) return isSmallPrime(n);
         
    if(n < 4759123141) {
        if(!mrt(n,  2)) return false;
        if(!mrt(n,  7)) return false;
        if(!mrt(n, 61)) return false;
        return true;
    }
           
    // Bases de Jim Sinclair pour le test Miller-Rabin jusqu'à 2^64
    if(!mrt(n, 2)) return false;
    if(!mrt(n, 325)) return false;
    if(!mrt(n, 9375)) return false;
    if(!mrt(n, 28178)) return false;
    if(!mrt(n, 450775)) return false;
    if(!mrt(n, 9780504)) return false;
    if(!mrt(n, 1795265022)) return false;
          
    // Maintenant : n est un nombre premier
    return true;
}
Messages postés
261
Date d'inscription
mardi 12 décembre 2006
Statut
Membre
Dernière intervention
10 juin 2019

Bonjour pgl10,

Un grand merci pour vos messages particulièrement intéressants !
J'espère bientôt pouvoir vous répondre plus attentivement.

Avant de "passer" à isPrime64, je pense d'abord approfondir la fonction mulmod64.

A bientôt …
Messages postés
313
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
26 mai 2020
2
Bonjour,

Dans le programme ci-dessus si on effectue :

    if(n < 1373653) {
        if(!mrt(n, 2)) return false;
        if(!mrt(n, 3)) return false;
        return true;
    }

au lieu de : if(n < 1373653) return isSmallPrime(n);
les performances que j'ai mesurées sont nettement moins bonnes.
Mais, en plus, on peut envisager quelques petites améliorations, par exemple inclure l'instruction : if(n < 341550071728321) return true; après le test unitaire effectué avec 17 pour accélérer le diagnostic des entiers premiers plus petits que cette limite intermédiaire. On pourrait aussi éviter de faire la décomposition (n-1)=(2^j)*d autant de fois que de tests unitaires pour la même valeur de n. En fait, ces modifications n'ont qu'une influence marginale, on peut s'en passer.
Afficher les 7 commentaires

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.