Répondre à la discussion
Page 1 sur 3 12 DernièreDernière
Affichage des résultats 1 à 30 sur 67

nombres premiers



  1. #1
    mayedi roland franck

    Talking 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 ::

    -----


  2. Publicité
  3. #2
    GuYem

    Re : nombres premiers

    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
    Bravo jolie Ln, tu as trouvé : l'armée de l'air c'est là où on peut te tenir par la main.

  4. #3
    leg

    Re : nombres premiers

    bonjour
    tu fais Google, puis: testeur de nombre premier

  5. #4
    Pole

    Re : nombres premiers

    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.
    Pour comprendre la récursivité croisée, il faut comprendre les arbres d'appels. Et vice versa.

  6. #5
    hekla

    Re : nombres premiers

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

  7. A voir en vidéo sur Futura
  8. #6
    Pole

    Re : nombres premiers

    Non. Mais en programmant,l'ordi vérifie ça très vite.
    Pour comprendre la récursivité croisée, il faut comprendre les arbres d'appels. Et vice versa.

  9. Publicité
  10. #7
    unepierre

    Re : nombres premiers

    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

  11. #8
    Pole

    Re : nombres premiers

    Le plus simple, oui. Et il est suffisant pour les nombres plus petit que 10^10 ce que veut mayedi roland franck.

    Pole.
    Pour comprendre la récursivité croisée, il faut comprendre les arbres d'appels. Et vice versa.

  12. #9
    booli

    Re : nombres premiers

    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 ?

  13. #10
    GuYem

    Re : nombres premiers

    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é).
    Bravo jolie Ln, tu as trouvé : l'armée de l'air c'est là où on peut te tenir par la main.

  14. #11
    booli

    Re : nombres premiers

    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 )

  15. #12
    booli

    Re : nombres premiers

    Citation Envoyé par GuYem Voir le message
    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é).
    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^^)
    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

  16. Publicité
  17. #13
    leg

    Re : nombres premiers

    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 ?

  18. #14
    booli

    Re : nombres premiers

    Citation Envoyé par leg Voir le message
    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

  19. #15
    Pole

    Re : nombres premiers

    Citation Envoyé par booli Voir le message
    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 ?
    Les notes de Fermat doivent être inintéressantes.
    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é :
    Citation Envoyé par pole
    Sur google : miler rabin,ecpp,apr-cl,lucas-lehmer(merci GuYem de m'y avoir fait pensé).
    http://fr.wikipedia.org/wiki/Test_de...lovay-Strassen
    Tester les pseudo-premiers : http://mersennewiki.org/index.php/Mi...primality_test
    Quelques sites : http://www.mersenne.org/,http://primes.utm.edu/

    Pole.
    Pour comprendre la récursivité croisée, il faut comprendre les arbres d'appels. Et vice versa.

  20. #16
    booli

    Re : nombres premiers

    Merci Pole, je vais prendre le temp de regarder tout ca

  21. #17
    leg

    Re : nombres premiers

    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+

  22. #18
    booli

    Re : nombres premiers

    Citation Envoyé par Pole Voir le message
    Les notes de Fermat doivent être inintéressantes.
    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-Strassen
    Tester les pseudo-premiers : http://mersennewiki.org/index.php/Mi...primality_test
    Quelques sites : http://www.mersenne.org/,http://primes.utm.edu/

    Pole.
    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 ) et serieux 400 lignes de codes c'est lourd : Personne aurait la formule (utilisé pour factoriser) mathematique en qqes lignes ?

    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 )

  23. Publicité
  24. #19
    Pole

    Re : nombres premiers

    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.
    Pour comprendre la récursivité croisée, il faut comprendre les arbres d'appels. Et vice versa.

  25. #20
    the strange

    Re : nombres premiers

    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::
    Dernière modification par the strange ; 26/11/2006 à 18h54.
    "En mathématique on ne comprend pas les choses ... on s'y habitue"

  26. #21
    the strange

    Re : nombres premiers

    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
    "En mathématique on ne comprend pas les choses ... on s'y habitue"

  27. #22
    booli

    Re : nombres premiers

    Citation Envoyé par Pole Voir le message
    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.
    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 ^^)
    Veuillez excuser mon orthographe !

  28. #23
    erik

    Re : nombres premiers

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

  29. #24
    booli

    Re : nombres premiers

    Citation Envoyé par erik Voir le message
    Salut,
    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 )
    Veuillez excuser mon orthographe !

  30. Publicité
  31. #25
    booli

    Re : nombres premiers

    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 ! (les nombres de fermat)






    Je continue a chercher et je vous tiens au courant





    BORIS!
    Veuillez excuser mon orthographe !

  32. #26
    booli

    Re : nombres premiers

    AH non rien !
    c'etait une erreur mon theoreme n'implique pas les fermat et donc reste potentielement exact



    Bonne nuit!
    Veuillez excuser mon orthographe !

  33. #27
    booli

    Re : nombres premiers

    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 !
    Veuillez excuser mon orthographe !

  34. #28
    erik

    Re : nombres premiers


  35. #29
    booli

    Re : nombres premiers

    Merci et voila mon premier grand nombre premier : 567137278201564105772291012386 28035243 !
    Veuillez excuser mon orthographe !

  36. #30
    booli

    Re : nombres premiers

    en voila 2 autres :
    623574031927851911766905528625 61408838653121833643

    434786819066587937349595056277 5707707143803
    Veuillez excuser mon orthographe !

Page 1 sur 3 12 DernièreDernière

Discussions similaires

  1. Nombres premiers, y aurait-il des nombres premiers jumeaux
    Par RSSBot dans le forum Commentez les actus, dossiers et définitions
    Réponses: 2
    Dernier message: 19/04/2007, 08h45
  2. nombres premiers
    Par christophe_de_Berlin dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 14/01/2006, 09h27
  3. Nombres Premiers
    Par enimax dans le forum Mathématiques du supérieur
    Réponses: 31
    Dernier message: 02/08/2005, 16h01
  4. Nombres Premiers
    Par N°1 et l'Astronomie dans le forum Mathématiques du supérieur
    Réponses: 25
    Dernier message: 22/10/2004, 21h18