Test de primalité B: Miller-Rabin 32 bits
William VOIROL
Messages postés
261
Date d'inscription
mardi 12 décembre 2006
Statut
Membre
Dernière intervention
10 juin 2019
-
17 févr. 2017 à 06:10
pgl10 Messages postés 380 Date d'inscription samedi 18 décembre 2004 Statut Membre Dernière intervention 29 octobre 2023 - 1 juil. 2017 à 16:44
pgl10 Messages postés 380 Date d'inscription samedi 18 décembre 2004 Statut Membre Dernière intervention 29 octobre 2023 - 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.
https://codes-sources.commentcamarche.net/source/101841-test-de-primalite-b-miller-rabin-32-bits
https://codes-sources.commentcamarche.net/source/101841-test-de-primalite-b-miller-rabin-32-bits
Modifié le 26 juin 2017 à 19:39
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.
1 juil. 2017 à 10:42
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 ?
Modifié le 1 juil. 2017 à 16:48
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; }21 juin 2017 à 08:38
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 …
11 juin 2017 à 11:09
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.
10 juin 2017 à 17:07
Le test de primalité de Miller & Rabin est habituellement présenté en tant que test probabiliste : s'il contrôle un entier en tant que nombre composé, ce nombre est certainement un nombre composé, et par contre, s'il contrôle un entier en tant que nombre premier, ce nombre est très probablement un nombre premier et ceci avec une probabilité que l'on peut maîtriser à l'avance : si on veut diminuer la probabilité éventuelle d'un diagnostic erroné, il suffit de faire dans la suite effectuée un plus grand nombre de tests unitaires. Si on a effectué 25 tests unitaires dont aucun n'a détecté un nombre composé on peut être pratiquement sûr que le nombre examiné est bien un nombre premier.
Mais il y a mieux. Les auteurs : Pomerance, Selfridge, Wagstaff et Jaeschke ont démontré qu'il est impossible d'avoir un diagnostic erroné pour tous les nombres entiers jusqu'à une certaine limite selon le nombre et la valeur des nombres auxiliaires utilisés dans la suite des tests unitaires. Si, par exemple, on utilise seulement les nombres auxiliaires : 2, 7 et 61 il n'y aura aucun diagnostic erroné pour tous les entiers jusqu'à 4759123141. Ceci a deux avantages : le test est plus rapide quand le nombre essayé est plus petit que la limite concernée et d'autre part le test est déterministe : le diagnostic erroné éventuel pour un nombre premier de cette taille n'est plus possible.
Voir : https://en.wikipedia.org/wiki/Miller-Rabin_primality_test pour les diverses limites connues selon le nombre de tests unitaires effectués.
M. William Voirol a publié ci-joint un programme de primalité Miller & Rabin qui est déterministe pour des entiers codés sur 32 bits. Ce programme nécessite l'emploi momentané de calculs avec des entiers codés sur 64 bits.
Le programme ici présenté est une variante du programme précédent qui permet de faire le test déterministe de Miller & Rabin pour des entiers codés sur 64 bits. Mais celui-ci n'a pas besoin d'utiliser des calculs intermédiaires avec des entiers codés sur plus que 64 bits. Il permet donc de faire le test de primalité jusqu'à (2^64)-1 et il permet aussi de montrer comment construire un test déterministe de Miller & Rabin jusqu'à (2^128)-1 en travaillant avec des entiers codés sur 128 bits. Bien entendu, le test habituel probabiliste de Miller & Rabin est aussi une très bonne solution du même problème, mais comme il est raisonnablement un peu moins rapide pour des entiers codés sur 64 bits, le programme ici présent semble préférable.
Le crible d'Ératosthène a l'avantage de fournir pour chaque entier examiné un indicateur : premier ou composé. Toutefois, il est totalement impossible d'exécuter un crible d'Ératosthène jusqu'à (2^64)-1 en raison de la mémoire et du temps de traitement qui seraient nécessaires. Si le test ici présent est plus long à traiter un entier donné que la simple consultation d'un indicateur, on pourra noter qu'il fournit sa réponse très rapidement.
Source :
/**************************************************** * Programme isPrime - @author pgl10 * * Test de primalité de Miller & Rabin déterministe * * pour des entiers codés sur 64 bits * ****************************************************/ #include <iostream> #include <cstdint> #include <sstream> #include <string> // Test de primalité de n pour n < 1373653 bool isSmallPrime(uint64_t n) { if(n < 2 || n >= 1373653) return false; uint32_t primTab[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187 }; uint32_t i = 0, p = primTab[0]; while(n >= p*p) { if(n % p == 0) return false; p = primTab[i++]; } return true; } // multiplication modulaire : mulmod(a, b, m) = (a * b) mod(m) uint64_t mulmod(uint64_t a, uint64_t b, uint64_t m) { if(b < a) { uint64_t t = a; a = b; b = t; } if (b >= m) { if (m > UINT64_MAX / 2u) b -= m; else b %= m; } uint64_t tmp, res = 0; while (a != 0) { if (a & 1) { if (b >= m - res) res -= m; res += b; } a >>= 1; tmp = b; if (b >= m - b) tmp -= m; b += tmp; } return res; } // test unitaire de Miller & Rabin // il faut : n impair et 1 < a < n bool mrt (const uint64_t n, const uint64_t a) { const uint64_t n1 = n - 1; uint64_t d = n1 >> 1; int j = 1; while((d & 1) == 0) d >>= 1, ++j; uint64_t t = a, p = a; // calcul de t = a^d mod n while(d >>= 1) { p = mulmod(p, p, n); if (d & 1) t = mulmod(t, p, n); } if(t == 1 || t == n1) return true; for(int k=1 ; k<j ; ++k) { t = mulmod(t, t, n); if(t == n1) return true; if(t <= 1) break; } return false; } bool isPrime(uint64_t n) { if(n < 2) return false; if(n == 2) return true; if(n % 2 == 0) return false; // Pour traiter plus vite le 1-er intervalle if(n < 1373653) return isSmallPrime(n); // On va effectuer les tests unitaires de Miller et Rabin // qui sont nécessaires pour avoir un contrôle déterministe. if(n < 4759123141) { if(!mrt(n, 2)) return false; if(!mrt(n, 7)) return false; if(!mrt(n, 61)) return false; return true; } if(!mrt(n, 2)) return false; if(!mrt(n, 3)) return false; if(!mrt(n, 5)) return false; if(!mrt(n, 7)) return false; if(!mrt(n, 11)) return false; if(!mrt(n, 13)) return false; if(!mrt(n, 17)) return false; if(!mrt(n, 19)) return false; if(!mrt(n, 23)) return false; if(!mrt(n, 29)) return false; if(!mrt(n, 31)) return false; if(!mrt(n, 37)) return false; return true; } // pour convertir une std::string en un uint64_t bool str2uint64(std::string str, uint64_t &n) { std::string chiffres("0123456789"); for(unsigned int i=0; i<str.length(); i++) { std::size_t found = chiffres.find(str[i]); if(found == std::string::npos) return false; } std::stringstream ss; ss << str; if(ss >> n) return true; return false; } int main() { uint64_t n; n = 9223372036854775808; // Ici n = 2^63 while(!isPrime(n)) --n; std::cout << std::endl << "Le plus grand premier plus petit que 2^63 est : " << n << std::endl; n = 9223372036854775808; while(!isPrime(n)) ++n; std::cout << std::endl << "Le plus petit premier plus grand que 2^63 est : " << n << std::endl; for(;;) { std::string str; do { std::cout << std::endl << "Entrez n : "; std::cin >> str; }while(!str2uint64(str, n)); if(isPrime(n)) std::cout << n << " est premier" << std::endl; else std::cout << n << " n'est pas premier" << std::endl; if(n==0) break; } return 0; }Conclusion :
Merci pour vos commentaires éventuels.18 févr. 2017 à 09:22
Bravo pour les diverses informations ici présentes relatives au test de Miller et Rabin.