nombres premiers
Bonjour, je connais ce que c'est un nombre premier, je peux le savoir jusqu'à 30 avec une certaine rapidité.Mais, je voudrais en savoir plus;pour cela comment reconnaitre de façon rapide qu'un nombre à partir de 100.000.000 est premier?Merci::
Salut, il existe pleins d'algorithmes, je pense que les réponses ne vont pas tarder à venir.
Peut-être même que si quelqu'un prononce le mot magique de Mersenne (oups je l'ai fait), nous aurons droit à une longue discussion
bonjour
tu fais Google, puis: testeur de nombre premier
Sur google : miler rabin,ecpp,apr-cl,lucas-lehmer(merci GuYem de m'y avoir fait pensé
Pour les programmes : Primo (qui utilise ecpp),ecpp de François Morain (pas pour Windows).
Si tu veux juste savoir si un nombre est premier et qu'il est plus petit que 10^9, tu peux tester si il est divisible par tous les nombres plus petits que sa racine.
http://www.alpertron.com.ar/ECM.HTM
Pole.
Une précision: il faut tester par tous les nombres premiers inférieurs à la racine du nombre que l'on veut tester, et pour les grands nombres ce n'est pas bien pratique manuellement ^^
Non. Mais en programmant,l'ordi vérifie ça très vite.
Les algorithmes de test de primalité n'essayent pas de diviser le nombre par tout ceux inférieur à sa racine. En effet il est beaucoup plus difficile de trouver un facteur que de montrer la non primalité. Le test de primalité est d'ailleurs un problème de compléxité polynomiale alors que la factorisation est exponentiel
Le plus simple, oui. Et il est suffisant pour les nombres plus petit que 10^10 ce que veut mayedi roland franck.
Pole.
Bonjour, je suis nouveau sur ce forum !
LA PETITE HISTOIRE DE MA VIE
Je m'appele Boris et j'ai 20 ans: je suis en 2eme Bachelier en Informatique !
En fait ca fait 3 semaines que j'arrete pas de redecouvrir tous les theoremes qui apparement sont fort utilisés pour tester la primalité des nombres !
Petit theoreme de fermat (29/10/06), je l'ai decouvert en voulant trouver la regle des mersenne (entre autre 2^11-1) sous la forme: x =( 2^n mod n ) - 2
si x=0 alors n est pseudo-premier !
J'ai trouvé la premiere erreur mentalement 2^2047 mod 2047 - 2 = 0 mais 2047 n'est pas premier ! (multiple de 23 et 89)
Ensuite j'ai testé par ecrit en qqes minutes le nombres : 2^1701411834604692317316873037 15884105727-1 qui aurait pu etre un mersenne ! et qui est bien pseudo-premier : 2^(2^1701411834604692317316873 03715884105727-1)-2 = 0mod (2^170141183460469231731687303 715884105727-1)
Le lendemain (30/10/06) j'ai decouvert que ce test n'avait servit a rien car tout les nombres "pseudo-mersenne" (de la forme 2^premier-1) donnerai un resultats positif a ce test (donc soit premier soit pseudo-premier)
Le lendemain (31/10/06) je cree un petit prog pour tester cet algo ! et je trouve plus d'erreur que je pensais (je pensais que seuls les mersennes posaient probleme) 341,561,643,... et je teste tout les nombres jusqu'a 100.000 et je decouvre qu'il reste toujours tres peu d'erreurs !
Le lendemain (1/11/06) je decouvre chez mon ami google en tapant ma premiere erreur "341" que ce test a deja ete decouvert il y a qqes siecles par notre cher ami fermat ! La je suis degouté et j'abandonne mes recherche pendant qqes semaines (enfin je suis aussi trombé 2 semaines malades !)
Puis hier (24/11/06) pendant un cours ! je ne sais pas pourquoi j'y rereflechi de nouveau et je decouvre en fait que le therome : x = (2^n mod n) - 2 -> donne dans le cas ou x n'est pas egal a 0, les diviseur de n simplement en prennant : t = (n mod x)
Toujours hier ! Dans le meme ordre d'idee je me dit que les pseudo-premier donnent aussi les diviseurs en prenant z fois le nombre n et en lui ajoutant 1 ! : si (2^n mod n) -2 = 0 alors soit n est premier soit z*n+1 divise ce nombre ! Je decouvre vite que c'est faux ! exemple : 561,645,... et correct pour certains nombres : 341,2047, dont pour tous les pseudo-mersennes ! exemple 2^11-1=2047 donc divisible par 11*186+1 (=1*2047) aussi par 2*11+1(=23*89) et le 89 = 8*11+1 donc une fois trouvé le premier diviseur (23) on divise 2047 par 23 = 89 -> 89 qui est forcement divisible par 11*q+1 meme s'il (89) n'est pas premier et dans ce cas ces diviseur seront egalement divisible par un nombre de la forme 11*t+1 et ainsi de suite !
Pour les mersennes je generalise vite (pcq les bases des mersennes sont impaires) : que pour (2^p)-1 il est soit premier soit divisible par un 2*K*P+1 (premier) plus petit que racine_carée((2^p)/2)
Je me dit a nouveau : Genial et puis paf aujourd'hui sur votre forum je decouvre que cette formule la aussi existe deja
http://forums.futura-sciences.com/post325355-9.html
Voila j'ai fini de raconter ma vie faite de decouverte et de deception !
QUESTION ?
J'aimerai juste savoir ce qui a deja été decouvert et ce qui ne l'a pas encore etait (dans le domaine du petit therome de fermat) pour que j'arrete de chercher pour rien (et perdre plein de temp, et meme rater des cours) et chaque fois me faire de faux espoir !
Quels sont actuellement les meilleurs optimisations du theoreme de fermat ?
Le moyens de trouver les diviseurs des nombres ? de tester leurs primalités ? de tester les mersennes ? et de tester les pseudo-premiers ?
Merci de me donner un maximum d'info !
PS: Y aurait-il un endroit ou je pourrait me procurer la totalité des notes de fermat ?
Bonjour booli, et bienvenu sur le forum. Je vais répondre brièvement à tes questions, même si ce n'est pas ce que tu veux :
Fermat est mort il y a trés longtemps, et depuis, des millions de mathématiciens se cassent la tête 23h/24 sur des problèmes de nombres premiers. (la dernière heure de la journée étant consacrée à la dégustation de café).
Bon je vois pas l'option editer mais j'ai oublié de preciser que : 2^1701411834604692317316873037 15884105727-1 = 2^(le_12eme_mersenne)-1 soit 2^(2^127-1)-1
(nombres qu'il n'est pas possible d'ecrire en entier par par un humain vu sa taille n valeur decimal ! un peu pres : 10^500000000000000000000000000 0000 )
Ok mais je pense quand meme que la solution des nombres premiers reside dans le theoreme de fermat (je pense meme qu'il en avait trouvé une grande partie) donc j'aimerai essayer de l'achever et si possible reprendr ses notes s'ils en restent (apres 300ans^^)Envoyé par GuYem
Donc je maintiens ma question : ou puis-je trouver ce qui est deja et ce qui n'est pas encore decouvert !
Ou puis-je trouver les notes de fermat ?
Merci d'avance de vos reponses
bonjour
booli tu oublies quand même qu'il n'avait pas de calculette. donc il n'a pas pu en trouver beaucoup
il = Fermat.
ceci dit il pensez que 2^2^n + 1 était tous premier ce qui indique qu'il n'a pas cheché trés loin.
le petit théorème de Fermat ne permet pas d'aller plus loin dans les nombres premiers, je pense que Fermat l'a découvert en voulant tester les nombre de Mersenne.
et malheureusement il y a des pseudo premier qui parasite ce test.
j'ai même éssayé avec deux jumeaux P(30)
11(30) et 13(30) avec le test de fermat, si les deux nombres en question passent le test il est quasiment sur qu'un des 2 nombres p(30) soit premier car je pense qu'il n'existe pas deux pseudo premier jumeaux avec d=2 de différence!
ce qui permet de savoir qu'un de ces deux est premier..
oui mais lequel, comme il sont trés grand > 10 000 000 de chiffres il faut refaire le test, sur ces deux nombres et garder celui qui satisfait a nouveau le test, voir les deux ou alors utiliser un test probabilité ..?
est ce rapide de faire ces deux tests ?
Ce que je cherche c'est justement une regle ou test qui generalise les parasite pseudo-premier !
Sinon la plupart de mes calcul et redecouverte je les ai fait en classe sans pc et la plupart sans calculatrice !
Comme dit plus haut le test de 2^(2^127-1)-1 je l'ai fait par ecrit en quelques minutes (donc sans calculatrice !) alors que je pense que toute une vie ne suffirait pas a un etre humain pour ecrire ce nombre !
Sinon qu'est-ce donc les P(30) ?
Et sinon pour les jumeaux je suis pas sur d'avoir compris ce que tu as dis mais en base 2 les nombres 4369 et 4371 sont pseudo-premiers !
edit: je sais que normalement le theoreme de fermat ce generalise en n'importe quel base qui doit etre premier avec n !
Mais bon moi je suis fan du binaire (informaticien que je suis -> d'ou mon pseudo ^^) et donc je fais toutes mes recherches et codes tous mes algo en binaire
Les notes de Fermat doivent être inintéressantes.QUESTION ?
J'aimerai juste savoir ce qui a deja été decouvert et ce qui ne l'a pas encore etait (dans le domaine du petit therome de fermat) pour que j'arrete de chercher pour rien (et perdre plein de temp, et meme rater des cours
Quels sont actuellement les meilleurs optimisations du theoreme de fermat ?
Le moyens de trouver les diviseurs des nombres ? de tester leurs primalités ? de tester les mersennes ? et de tester les pseudo-premiers ?
Merci de me donner un maximum d'info !
PS: Y aurait-il un endroit ou je pourrait me procurer la totalité des notes de fermat ?
Les meilleures optimisations du théorème de Fermat : rabin-miller
Les moyens de trouver les diviseurs : http://www.javafr.com/codes/CRIBLE-Q...ION_34256.aspx
ou ECM (regarde le lien que j'ai donné au dessus).
Tester la primalité :http://fr.wikipedia.org/wiki/Test_de...lovay-StrassenSur google : miler rabin,ecpp,apr-cl,lucas-lehmer(merci GuYem de m'y avoir fait pensé
Tester les pseudo-premiers : http://mersennewiki.org/index.php/Mi...primality_test
Quelques sites : http://www.mersenne.org/,http://primes.utm.edu/
Pole.
Merci Pole, je vais prendre le temp de regarder tout ca
booli
Sinon qu'est-ce donc les P(30) ?
Et sinon pour les jumeaux je suis pas sur d'avoir compris ce que tu as dis mais en base 2 les nombres 4369 et 4371 sont pseudo-premiers !
.............................. .............................. ................4371 est multiple de 3
p(30) sont des nombres qui sont soit premier soit divisible par p(30) pour p = 7.11.13.17.19.23 et 31
par exemple 4369 = 19(30) donc dans cet ensemble il n'y a que 26.6666% des entiers naturel pas de multiple de 2, 3 ou 5
donc y'a t'il souvent des pseudo premiers jumeaux = 11 et 13(30)
17 et 19 (30) ou 29 et 31 (30)
tu prends 2 grands nombres jumeaux correspondant à une de ces trois séries et tu aplique le petit théorème de Fermat sur ces deux nombres suppose que le test te dit qu'il sont premiers tu as de forte chance qu'au moins un des deux soit premier et dans ce cas tu refais un test de probabilité sur les deux nombres tu le fais, que si le test est positif pour les deux jumeaux c'est à dire que le test de Fermat t'indique qu'il sont premiers par supposition.
tu prends 11 + k30 et 13 + k30 regarde si le cas se présente souvent 2 premiers = 2 pseudo premiers,
soit deux jumeaux p(30) bien sur.
tu peux faire un programme basé sur ce principe
l'idée de trouver une règle pour les pseudo premier serait bien si il y en avait une. car avant de faire un test de fermat, tu n'utiliserais que ce qui ont satisfais au premier test. cela revient a faire un test qui correspondrait au nombre premiers en un temps trés trés rapide on aurrait déjà trouvé ..peut être.
puis:
17 +k30 et 19+k30 ou 29+k30 et 31 + k30
47 ............49............59 .......... 61
77 ............79............89 ......... 91
107 ..........109..........119.... ...... 121
etc
A+
Merci encore pole pour tous ces liens mais pour trouver les diviseur (factoriser) peut tu me donner la formule utilisé stp !
Dans tes 2 lien l'un donne une page en anglais (aie!) et je ne vois pas de formule sur ce site ! Sur l'autre c'est un prog avec du code (ok je fais des etudes d'informaticien mais je deteste ca
Merci d'avance !
LEG> Pour tes P(30) j'avoue que je n'ai pas pris le temp d'essayer de les comprendre (le raisonnement) mais ca me semble etre qqe chose sans avenir utilisant des multiple de 30 pcq 30 = 2*3*5 (cad les 3 plus petits nombres premiers) ce qui donne logiquement des resultats pour de petits nombres ! (enfin comme je l'ai dit j'ai pas pris le temp d'analyser cela et donc ce n'est que des suppositions mais je prefere continuer dans ma lancé sur fermat
Pour le truc en java,j'ai marqué des liens en bas de la page.
ECM : http://medicis.polytechnique.fr/~ler...p?lng=en&pg=27
Il n'existe pas de formule qui tiennent en quelques lignes pour factoriser rapidement.
Sinon plus simple : pollard rho,pollard p-1.
Pole.
je vais me suicider les gars
pourquoi ces tests ?
mon dernier ds de maths avait pour objet la demo du nomber mersenne premier...
j'ai eu la meilleure note
ne me dites pas que ce que j'ai su demontré est faux
:ry::
je vais me suicider les gars
pourquoi ces tests ?
mon dernier ds de maths avait pour objet la demo du nomber mersenne premier...
j'ai eu la meilleure note
ne me dites pas que ce que j'ai su demontré est faux
oK? Ca c'est vraiment cool, parce que je crois que je suis sur le point de trouver une formule pour factoriser les nombres en qqes operations (meme peut etre les pseudo-premiers [&nombres de carmachin])
Si j'y arrive je vous tiens au courant
PS: Il n'y a pas quelqu'un qui veut bien me donner un nombre de 12 à 15 chiffres composé de 2 facteurs premiers de minnimum 6 chiffres ? (histoire que je test ma formule par ecrit sans connaitre les reponses a l'avance ^^)
Salut,Ca c'est vraiment cool, parce que je crois que je suis sur le point de trouver une formule pour factoriser les nombres en qqes operations
Je ne voudrais pas jouer les rabat-joie, mais c'est là un problème qui a mobilisé (et qui mobilise encore) une mégachié de mathématiciens, et ce depuis un bon bout de temps.
Enfin bon, voila trois nombres à factoriser
121505746631
452379495209539
1216465392912548476903
PS : à noter : la factorisation de ces nombres reste facile avec les algo déja connu.
Les algos ? tu veux dire les progs qui tests tous ses diviseurs ? (avec optimisation evidement^^) ou alors il existe quand meme des formules ?
Sinon, merci je vais tester ca demain par ecrit sans calculateur ni listes de nombres premiers et je verrrai si j'y parviens^^ [pour la difficulté j'espere que tes nombres n'ont pas de diviseur inferieur a 1000^^]
Maintenant je vais dormir (et oui j'ai aussi une vie a coté des maths et de mes loisirs je dois etudier/travailler
en fait j'ai pas pu dormir -> j'ai analysé mon theoreme pour trouver une suite de nombres premiers qu'on pouvait contruire a partir de la et au miracle je trouve (2^2n+1), je teste sur la 4 premiere valeur et oh miracle ca fonctionne !
J'arrive pas a tester sur la n=5 car c'est trop grand mon le "long int" en c++
donc je tape cette formule dans google et ca me dit que cette formule existe deja !
Que elle est fause
ce qui implique que mon theoreme est faux !
Et oh magique ! qui c'est le con qui a inventé cette formule ? fermat
Pouquoi je retrouve ABSOLUMENT tout ce que fermat a trouvé ? et pourquoi j'etais sur a 100% que cette formule et cette sute etaient excat ? et fermat aussi pensait que c'etait exact ? je suis sur a 100% que fermat connaissait ma formule
donc mais formule est correct pour les 100 centaines de chiffres que j'ai testé, pour tous les carmichael que j'ai testé ! mais est fause pour les fermat !
Peut-etre aussi fause pour d'autre nombre ? J'espere que non comme ca ! ca ne fera pas trop d'exception
Je deprime trop ! j'ai cru pendant une demi-heure que j'avais trouvé des nombres premiers !
Je continue a chercher et je vous tiens au courant
BORIS!
AH non rien !
c'etait une erreur mon theoreme n'implique pas les fermat et donc reste potentielement exact
Bonne nuit!
Derniere question apres je ne vous ennui plus : qqn peut me donner un outil (programme) pour tester der grand nombres ? (premier ou non)
Merci beaucoup d'avance !
Tu peux utiliser Maxima : http://wxmaxima.sourceforge.net/wiki....php/Main_Page
Merci et voila mon premier grand nombre premier : 567137278201564105772291012386 28035243 !
en voila 2 autres :
623574031927851911766905528625 61408838653121833643
434786819066587937349595056277 5707707143803
