Test de primalité B: Miller-Rabin 32 bits

William VOIROL 211 Messages postés mardi 12 décembre 2006Date d'inscription 24 mai 2018 Dernière intervention - 17 févr. 2017 à 06:10 - Dernière réponse : pgl10 296 Messages postés samedi 18 décembre 2004Date d'inscription 14 avril 2018 Dernière intervention
- 1 juil. 2017 à 16:44
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

http://codes-sources.commentcamarche.net/source/101841-test-de-primalite-b-miller-rabin-32-bits

Afficher la suite 
pgl10 296 Messages postés samedi 18 décembre 2004Date d'inscription 14 avril 2018 Dernière intervention - 11 juin 2017 à 11:09
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.
William VOIROL 211 Messages postés mardi 12 décembre 2006Date d'inscription 24 mai 2018 Dernière intervention - 21 juin 2017 à 08:38
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 …
pgl10 296 Messages postés samedi 18 décembre 2004Date d'inscription 14 avril 2018 Dernière intervention - 26 juin 2017 à 19:34
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.
William VOIROL 211 Messages postés mardi 12 décembre 2006Date d'inscription 24 mai 2018 Dernière intervention > pgl10 296 Messages postés samedi 18 décembre 2004Date d'inscription 14 avril 2018 Dernière intervention - 1 juil. 2017 à 10:42
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 ?
pgl10 296 Messages postés samedi 18 décembre 2004Date d'inscription 14 avril 2018 Dernière intervention > William VOIROL 211 Messages postés mardi 12 décembre 2006Date d'inscription 24 mai 2018 Dernière intervention - 1 juil. 2017 à 16:44
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;
}
Commenter la réponse de William VOIROL

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.