Je crois que j'ai fais une tres grosse trouvaille mathematique :
Je sais tester un nombre pour voir s'il est premier sans me soucier des NP precedents !
Cela existe t'il deja ?
Les calculs sont tres rapides (peut etre 1000 fois plus rapide que ceux actuels). DITES MOI TOUT.
Merci
Cela n'existe pas à ma connaissance.
Tu comprendras cependant mon scepticisme sachant que des millions de mathématiciens se cassent la tête depuis des lustres à essayer de décoincer ce problème des nombres premiers.
Cependant aprés tout si tu as bien trouvé une idée originale alors grosse félicitations à toi!
Comment crois-tu que les grand nombre premiers sont prouvés. La connaissance des nombres premiers précédants n'est pas indispensable, on s'en serre que pour réduire le nombre de candidats.SPH:
Je sais tester un nombre pour voir s'il est premier sans me soucier des NP precedents !
Cela existe t'il deja ?
Bon, guyem et daniel ne sont pas daccord; ca commence bien. Mais je pense que c'est guyem qui a raison.
Martini bird ??
Attention je suis une quiche en arith!
Je pense plutôt que c'est Daniel qui a raison.
Bien sûr que ça existe. Il suffit de tester la divisibilité de n'importe quel nombre impair n, par 3, puis par pas de 6 par p, jusqu'a racine(n)+1, par les valeurs 6p+1, et 6p+5.Envoyé par SPH
Je crois que j'ai fais une tres grosse trouvaille mathematique :
Je sais tester un nombre pour voir s'il est premier sans me soucier des NP precedents !
Cela existe t'il deja ?
Les calculs sont tres rapides (peut etre 1000 fois plus rapide que ceux actuels). DITES MOI TOUT.
Merci
Par contre, je ne suis pas certain que ça soit le plus rapide. Mais si tu ne précises pas ton algo, on ne pourra pas vraiment avoir un esprit critique dessus
Mon algo est en cours d"étude. J'ai encore quelques trouvailles a pauffiner...Bien sûr que ça existe. Il suffit de tester la divisibilité de n'importe quel nombre impair n, par 3, puis par pas de 6 par p, jusqu'a racine(n)+1, par les valeurs 6p+1, et 6p+5.
Par contre, je ne suis pas certain que ça soit le plus rapide. Mais si tu ne précises pas ton algo, on ne pourra pas vraiment avoir un esprit critique dessus
PS : je pense que mon algo réduit le nombre d'opération de 90% !
Il existe de nombreux tests de primalité de tous types (déterministes ou probabilistes).
Aucun ne requiert de connaître les nombres premiers inférieurs.
Jete un oeil à ceci :
http://mathworld.wolfram.com/PrimalityTest.html
Il réduit le nombre d'opération de 90% par rapport à quelle technique?
par rapport au criblage de mersenne
Tu peux dire ton algo sans les améliorations. Dis aussi le plus grand P que tu as trouvé.
Il va sûrement pas dévoiler son algo sur un forum, il faut faire une annonce officielle, pour ne pas que quelqu'un lui pique son idée.
Après, direction un des amphis du MIT où une centaine de chercheurs, parmi les plus reconnus du monde, l'attendront comme le messie, et où il révélera sa trouvaille. J'ai tout juste SPH?
ouiIl va sûrement pas dévoiler son algo sur un forum, il faut faire une annonce officielle, pour ne pas que quelqu'un lui pique son idée.
Après, direction un des amphis du MIT où une centaine de chercheurs, parmi les plus reconnus du monde, l'attendront comme le messie, et où il révélera sa trouvaille. J'ai tout juste SPH?
mais ca ne m'empechera pas de mettre un programme a votre disposition.
ps : pour l'instant, ma routine est limité a 2 milliard car c'est tjr pareil en informatique. Mais ca peux s'ettendre a bocou plus.
Ha oui, j'allais oublier : ma routine trie les NP qui n'ont aucune incidence pour un crible de mersenne, et les NP qui ont une influence en crible.
ex:
40009 : Premier et Cribleur de Mersenne 'strange'
40013 : Premier
40031 : Premier et Cribleur de Mersenne
40037 : Premier
40039 : Premier et Cribleur de Mersenne
40063 : Premier et Cribleur de Mersenne
40087 : Premier et Cribleur de Mersenne
40093 : Premier
40099 : Premier
40111 : Premier et Cribleur de Mersenne
40123 : Premier
40127 : Premier et Cribleur de Mersenne
40129 : Premier
40151 : Premier et Cribleur de Mersenne 'strange'
40153 : Premier et Cribleur de Mersenne 'strange'
40163 : Premier
40169 : Premier et Cribleur de Mersenne 'strange'
40177 : Premier
40189 : Premier
40193 : Premier
40213 : Premier
40231 : Premier et Cribleur de Mersenne
40237 : Premier
40241 : Premier et Cribleur de Mersenne 'strange'
40253 : Premier
40277 : Premier
40283 : Premier
40289 : Premier
40343 : Premier et Cribleur de Mersenne
40351 : Premier et Cribleur de Mersenne 'strange'
40357 : Premier
40361 : Premier et Cribleur de Mersenne 'strange'
40387 : Premier
40423 : Premier et Cribleur de Mersenne
40427 : Premier
40429 : Premier
40433 : Premier et Cribleur de Mersenne 'strange'
40459 : Premier
40471 : Premier et Cribleur de Mersenne 'strange'
40483 : Premier
40487 : Premier et Cribleur de Mersenne
40493 : Premier
40499 : Premier
40507 : Premier
40519 : Premier et Cribleur de Mersenne
40529 : Premier
40531 : Premier
40543 : Premier et Cribleur de Mersenne
40559 : Premier et Cribleur de Mersenne
40577 : Premier
40583 : Premier et Cribleur de Mersenne
40591 : Premier et Cribleur de Mersenne 'strange'
Dernière modification par SPH ; 08/09/2005 à 20h04.
Vous vous rendez compte ! On est peut-être en train de discuter avec un futur Médaille Field ...Il va sûrement pas dévoiler son algo sur un forum, il faut faire une annonce officielle, pour ne pas que quelqu'un lui pique son idée.
Après, direction un des amphis du MIT où une centaine de chercheurs, parmi les plus reconnus du monde, l'attendront comme le messie, et où il révélera sa trouvaille. J'ai tout juste SPH?
Salut,
êtes-vous aller jeter un oeil au lien proposé ? Les méthodes qui ne s'occupent que du nmbre à tester sont légions, et pas toutes déterministes. Voire par exemple la page de François Morain pour un test efficace qui prouve la primalité de nombres ayant environ 300 chiffres (pour les nmbres quelconque, mais certains nmobres ayant une forme particulière et possédant un bon millier de chiffre ont été prouvé premier par ce test) : http://www.lix.polytechnique.fr/Labo/Francois.Morain/
Pour être franc (et après avoir lu plusieurs discussions sur ce même forum), je suis un peu sceptique... M'enfin, je peux me tromper évidement
Amicalement
Moma
bonjours tous,
sph ,
pour les nombres de Mersenne on utilise le test de Lucas-Lehmer pour determiner si ils sont premiers ou pas .C'est tres rapide.
je serais curieux de savoir ce que vous avez trouvé ...
Regarde au "nombre de Mersenne" et "Sécurité de l'état..etc"(assez loin).
Mes methodes determinent avec une certitude totale si un nomnre est premier. Actuellement, comme tjr en informatique, je me creuse la cervelle pour contourner cette fichue limite 32 bits. C'est ca le plus dur.
Moi, j'affirme que ce n'est pas la peine de tester tous les nombres premiers pour savoir si un nombre de mersenne est premier. Il n'y a que 40% des NP qui ont une incidence dans le criblage d'un nombre de mersenne. Tiens, par exemple, j'AFFIRME que les np 3; 5 et 11 pour ne citer qu'eux ne pourront JAMAIS cribler un mersenne. Et c'est comme ca pour 60% des NP
Salut,
même si tu élimine 60% des nombres, un crible restera trop lent. Tu devra quand même testé un nombre de nombre premier de l'ordre de, ce qui n'est pas du tout polynomial en
Amicalement
Moma
cela veux tous implement dire, que peut être ta méthode passant par l'utilisation de nombre premier pour tester un Mersenne sera inutilisable car trop lente ou alors l'obilgation de créer une banque de donnée qui dépasse les capacités d'un pc,
Même un programe qui ne ferait pas appel a des Premier, il ferra appel à une méthode similaire ou les nombre sont remplacé par des . ou des , ou des 0 ou encore des signes, mais il t'en faudras une telle quantité pour atteindre ta cible, que le résultat revien au même. ce que je ne comprend pas cest pourquoi tu ne teste pas un nombre de 33 chiffre qui rentre dans n'importe quel programme et tu nous donne le résultat ou une comparaison avec un autre test...
A+
SPH, j'AFFIRME que les np 3; 5 et 11 pour ne citer qu'eux ne pourront JAMAIS cribler un mersenne. Et c'est comme ca pour 60% des NP : faux,
ce n'est pas par ce que 3 ne divise pas directement Mersenne qu'il ne le crible pas d'une autre manière,de plus 3 divise tous les mersennes sous cette forme: (Mq - 1)/2. ce qui donne des idées
__________________
11*2+1, crible 2^11-1;
23*2 + 1crible 2^23 -1
(3+113)*2 +1 crible 2^29 -1
(37*3)*2 +1 crible 2^37 - 1
(Mq - 1)/ 2 a des facteur P qui permettent de retrouver le plus petit facteur P divisant Mq tel que ce facteur p est la différence entre A - B de sorte que A² - B² = Mq composé! est: le grand facteur P ou composé / 2 est un nombre N ,qui se situe entre A et B, donnant par exemple A - N = (petit facteur P) /2; qui se trouve grace aux facteurs Premiers de (Mq - 1)/ 2. alors, tu vac me demander pourquoi?
pour l'instant je te dirai : parce que N, divise aussi (Mq - 1)/ 2 et le quotien = (petit facteur P) /2...... curieusement pour l'instant on utilise 3 et l'exposant ou un des petits facteurs P, obtenus par les carrés de (Mq - 1)/ 2. ex pour 2^29 -1 = (U² -V²)/2
V est toujours = 2
U=32768 V=2, u'=16385, et v'=16383,
16383/5/29/113
16383/3/43/127
113 = a et (43*127) = b qui me permettent de remonter et trouver A et B tel que A² - B² = 2^29 -1.
Leg, tu te bases sur des calculs qui ne sont pas a toi. Quand a moi, j'affirme que "3" ne peux pas cribler un potentiel mersenne.
Prend cette liste et continue la si ca te dit d'essayer de prouver ce que tu dis et tu verras :
Nombre de mersenne premier ou non (4x+3) :
7
31
127
511
2047
8191
32767
131071
524287
2097151
8388607
33554431
134217727
Le np 3 et son crible (9; 15; 21; 27,...) ne condamneront jamais un mersenne
bonjour,
sph,
3 ne crible effectivement pas les nombres de mersenne a exposant premier
3 divise 2²-1, donc il divise tous les 2^2a-1 c'est a dire les exposants pairs , il en est de meme pour la liste de nombres premiers que vous avez fournie sur un autre fil.
la remarque precedente sur la rapidité d''un tel crible est exacte sph .
bon courage jeune homme
Je dirais plutot que je devrais tester seulement 40% deSalut,
même si tu élimine 60% des nombres, un crible restera trop lent. Tu devra quand même testé un nombre de nombre premier de l'ordre de
non
Pour que ça soit polynomial, il faut que la complexité soit du type a^b avec a qui change (et qui est égal au nombres de chiffres de ton nombre) et b constant.
Et toi (pour x), c'est 2/5*sqrt(x) et pour le nombre de chiffres (en base 10): 2/5*sqrt(10^x)=2/5*10^(x/2)~=10^(x/2). Comme x (en exposant) varie, ton algo n'est pas polynomial.
sph il ne faut pas être aussi tétu,
l'exemple que je t'ai donné ce sont bien mes calcul tu n'a qu'a relire le fil mersenne en plus c'est une question que tu m'as posé .
ceci dit, tu ne fais pas attention a ce que l'on te dis ...
un nombre de mersenne est congrue 1 ou 7 modulo 30 donc il ne peut être multiple de 3 , j'ai mis les modulo en fonction de l'exposant mais tu regardes la ou bon te semble
regarde ce que 3 divise c'est un nombre de Mersenne - 1 et divisé par 2..
ce que j'ai mis pour les exposant 11,23,29,37, c'est une constatation si tu regarde le facteur P = 164511353 qui divise Mq exposant 41,ce qui te donne 13367
(Mq - 1)/2 que divise a nouveau P tu obtiens 6683.5 .
en connaissant les facteurs P de (Mq - 1)/2 j'essais de remonter afin de trouver deux carrés A et B ou de retrouver une approche de 6683,5 .
A question claire, réponse claire
Pourtant, ma question est VRAI et ta reponse est FAUSSE
PS : je tiens compte de ce qu'on me dit mais pas de ce que tu dis car je ne comprend jamais rien a ce que tu racontes. J'ai beau lire et relire tes posts, j'ai toujours l'impression que tu sautes du coq a l'ane a chaque instant. Par contre, je fais confiance a pole et a martini par exemple... Et pour moi, c'est pole qui a 57 ans, et toi, tu dois en avoir 12... (vous voyez, on reste dans les nombres !!)
Salutations,
J'avoue que je comprends pas tout de que vous dizez (SPH particulierement, mais leg toi aussi parfois.........).
Mais pour reprendre ta question, et pour préciser ma pensée sur les algorithme polynomiaux, je vais définir et expliuer calmement.
Un algorithme "arithmétique" est dit polynomial si sa complexité (en gros le temps qu'il met à donner la réponse par rapport à la taille des données) est un polynome en
Comme l'a très bien rxlpiqué Pole, un algorithme en
C'est une des raisons qui font que les criles ne sont pas utilisés saèf pour les "petits" nombres. Les recherches dans ce sens sont presques inutiles, vu qu'un "bon" progres ne serait utile que pour des nombres plutôt raisonnables. L'augmentation de la taille serait fatale.
Garde ben en mémoire que l'unité de masure est le nombre de chiffres (proportionnel à
En espérant t'avoir éclairé etmis sur la bonne voie
Amicalement,
Moma
leg : (Mq-1)/2=Mq-1
