Rechercher un outil (en entrant un mot clé):
Test nombre premier > 12 chiffres
Tester si un grand nombre est premier et le factoriser s'il n'est pas premier
Le test de primalité (savoir si un nombre est un nombre premier) de cette page est adapté aux nombres composés de plusieurs dizaines de chiffres. La décomposition en produit de facteurs premiers peut être très longue, voire parfois impossible, même pour nos ordinateurs modernes, et encore davantage pour un outil de calcul en ligne d'un site web. Nous avons limité l'entrée aux nombres composés au maximum de 200 chiffres pour le test et de 22 chiffres pour la factorisation en produit de facteurs premiers.
Vous pouvez obtenir par exemple les décompositions :
- de M(59), égal à 576460752303423487, qui est un nombre de Mersenne composé de 18 chiffres
- de M(67), un nombre de Mersenne composé de 21 chiffres (voir plus bas). Il faut alors plusieurs secondes, nous sommes à la limite du temps alloué par notre petit serveur.
Exemple : 147573952589676412927 est-il premier ?
L'algorithme de factorisation (Brent Pollard) utilisé par cet outil permet de décomposer ce nombre 147573952589676412927 en facteurs premiers en quelques secondes. Le test de sa primalité est effectué par le test de Miller Rabin. Ce nombre de 21 chiffres est un nombre de Mersenne (M67) et il n'est pas premier. Cela fut démontré en 1903 par le mathématicien Frank Nelson Cole, qui passa plus de 3 ans, tous ses dimanches, à le "casser". Lors d'une réunion de mathématiciens américains, on dit qu'il écrivit simplement sur un tableau sa décomposition :
267 − 1 = 147573952589676412927 = 193707721 × 761838257287,
ce qui eut pour effet de bluffer toute l'assistance.
618970019642690137449562111 est-il premier ? Cette fois, nous pouvons seulement tester si ce nombre est premier, il est composé de 27 chiffres et il est premier. L'algorithme du test de primalité est celui de Miller Rabin qui permet de tester sans effectuer la décomposition des nombres de plusieurs centaines de chiffres. 618970019642690137449562111 est lui aussi un nombre de Mersenne (M89).
Limite en ligne de la factorisation en nombres premiers :
21 chiffres semble être la limite afin d'obtenir la factorisation en ligne, par exemple :
215525392304898663817(21) = 697499261(9) × 308997305597(12) en 5 secondes
325812389847171218723(21) = 985717937(9) × 330533084179(12) en 8 secondes
911257405449760897039(21) = 5649231271(10) × 161306443609(12) en 8 secondes
Quelques nombres "cassés" avec ce script sur un serveur (core duo 2ghz) hors ligne :
262158157939114458143411(24) = 534377194849(12) × 490586350739(12)
647566049626292397956681(24) = 80262788779(11) × 8068073131739(13)
2440496884869731873565719(25) = 761838257287(12) × 3203431780337(13)
21917518892308073668859263(26) = 288142510391(12) × 76064857151993(14)
5429025772880707392557242027(27) = 8284874025851(13) × 655293702226577(15)
4402839946368730042729805927(28) = 9096582498011(13) × 484010335456357(15)
47537782609103580051013918973(29) = 9166735005257(13) × 5185901259482389(16)
157127558679069541525864491061(30) = 28552680542909(14) × 5503075567386329(16)
649825047254615206673880715789(30) = 85452603461273(14) × 7604508475263893(16)
1571275586790695415258644910617(31) = 4261 × 223224703987(12) × 1651956369903431(16)
32729618763243458927731615853893(32) = 530667019817041(15) × 61676376222753973(17)
2168−1 = 374144419156711147060143317175368453031918731001855(51)
= 15×29×43×113×127×147×221×241×337×1429×3361×5419×14449×15790321×88959882481 = 32× 5 × 72 × 13 × 17 × 29 × 43 × 113 × 127 × 241 × 337 × 1429 × 3361 × 5419 × 14449 × 15790321 × 88959882481
2169−1 = 748288838313422294120286634350736906063837462003711(51)
= 4057×8191×6740339310641×3340762283952395329506327023033
Les 2 derniers exemples illustrent bien la difficulté de factoriser des grands nombres. Le temps ne dépend pas du nombre de chiffres du nombre à factoriser mais du nombre de chiffres de ses facteurs premiers.
Remarque : l'algorithme de factorisation (Brent Pollard) de cette page est adapté aux nombres "quasi premiers" c'est-à-dire composés de 2 facteurs premiers qui sont aussi des grands nombres. Il peut dans certains cas (comme pour 2168−1) ne pas donner la décomposition exacte en facteurs premiers et laisser des petits facteurs non décomposés.
Après une amélioration du programme toujours hors ligne :
F400=176023680645013966468226945392411250770384383304492191886725992896575345044216019675(84) = 3 × 52 × 7 × 11 × 41 × 47 × 101 × 151 × 401 × 1601 × 2161 × 3001 × 3041 × 124001 × 570601 × 6996001 × 9125201 × 5738108801 × 3160438834174817356001
Les commentaires :
Merci, pour cette page, cela fonctionne très bien ! Pas toujours pour le nombre 147573952589676412927 dés fois la page n'abouti pas ! Sans doute pour un temps trop long !
Pierre, le 26/06/12.
Bonjour, j'ai testé les outils de factorisation d'un nombre disponible sur le net (les premiers proposés) avec 147573952589676412927. Il y en a beaucoup qui ne peuvent même pas factoriser ce nombre qui trop grand, un autre ou il fallait installer un plugin (j'ai abandonné après l'avoir par deux fois installé, ça ne fonctionnait pas), reste votre page qui réussit à sa décomposition en facteur premier !
JP, le 23/06/13.
Réponse : Merci beaucoup pour vos encouragements, mais je pense pas que ce soit la seule page.
Bonjour, je m'amuse à calculer les nombres premiers sur pc. Mais je suis surpris, que les logiciels de calcul formel, ne sois pas aussi performent que les pc actuel. C'est à dire, que Mathématica est le seul à calculer rapidement. Je n'arrive pas à trouver un gratuit aussi performant que ce logiciel. Exemple : avec mathématica 9, 2^44497-1 en moins de deux minutes !! Trouver en 1979 sur Cray !! Avec Maple, j'ai perdu patience et avec Xcas idem. Je me pose alors la question, la NASA utilise quoi comme logiciel de math ? Merci de votre avis et réponse.
Le 16-08-2013
Réponse Bonjour, je pense qu'ils utilisent Mathématica ! On fait difficilement mieux à moins de développer un logiciel spécifique. La difficulté n'est pas de trouver les facteurs premiers lorsqu'ils sont nombreux et petits, mais bien de factoriser des nombres quasi premiers (produit de deux grands nombres premiers) où le plus petit des facteurs est lui aussi un très grand nombre.
