et essayer de prouver (impossible à calculer avec LLT) que 2(2^127-1)-1 premier ?
des mathématiciens ont-ils essayé de travailler la dessus ?
car ormis mes cours incomplets (trop anciens pour certains) et les banalités trouvées sur internet...
il faudrait regarder des forums en anglais peut-être certains sont-ils bien fournis
Dernière modification par acx01b ; 14/01/2006 à 19h32.
question (Tony):Non. Juste un carré. Le coût de la soustraction est ridicule à côté du carré. Ensuite le modulo est fait par ... 1 addition. En fait, l'algorithme DWT utilisé par prime95 intègre même le modulo dans le carré (si je me souviens bien ...).
Les principaux intérêts de chercher des nombres premiers de Mersenne sont :
- un test TRèS rapide : le LLT
- l'utilisation d'une forme particulière de FFT très efficace pour faire le carré : DWT.
- calculer modulo un nombre de Mersenne ou un nombre de Fermat est TRèS simple.
- les exposants candidats au test LLT pour des nombres de Mersenne sont nombreux, et les nombres de Mersenne premiers apparaissent très régulièrement. Ce qui n'est pas le cas des nombres de Fermat.
Pour calculer modulo de N :
.
Or B représente les q bits de droite de N, et A représente les autres q bits à gauche.
Donc : .
Pour calculer modulo de N :
.
Donc : .
Tony
avec la transformée de fourier, si 2a < n < 2a
+1
alors 22a < n2 < 22a+2 et donc la transformée de n^2 fait a+1 bits à peu près...
donc pour des Mn n=2^28 environ je vais gérer des nombres de 1mégaoctet ?? (c'est énorme!?)
j'ai déja travaillé avec fftw en c++ builder...
est-ce que avec seulement ta formule MERveilleuse
je peux programmer un équivalent (rapiditéà prime95 si j'utilise correctement l'assembleur là ou il le faut ???
Dernière modification par acx01b ; 14/01/2006 à 19h48.
La FFT utilise des double (4 octets).Envoyé par acx01b
2 double (partie réelle et imaginaire)-> 8 octets
2^(2^28)->2^28 bits->2^25 octets->2^22 mots.
(prime95 doit travailler en base 65536)
~=4 000 000 cases
~=8Mo
Seulement, 2^28~=268 000 000
Alors que les plus gros tests sont à 79 000 000.
(2^27)->4Mo
Les test "courants" sont à 35 000 000 (2^26) ->2Mo
Les vérifications sont à 16 000 000 (2^25)->1Mo
Mais 8Mo, quant on en a 256, voir beaucoup plus, c'est rien.
A+.
bonjour
en regardant la liste des nombres de Mersenne sur wikipedia et aussi sur gimps il est donné le 33ème Mersenne, exposant P = 859433; or (2*P)+1 est premier ? il ne diviserait donc pas ce Mn??
autant pour moi P, n'est pas = 4K + 3
Il est intéressant de constater, que la répartition des exposants P, des nombres de Mersenne Mq premiers, se répartit assez bien dans les 8 séries de la famille des nombres premiers P ≡ p (30) .
(« Ceci correspond bien d’ailleurs, à la répartition des ces nombres P par série, leur nombre est ≈ équivalent par série lorsque N tend vers l’infini »)
Voici ce que cela donne : « 1(30) est remplacé par 31(30) »
De M43, à M4
...7(30)……….11(30)…..….13(30)… ….17(30)..……19(30)……..23(30).. ……29(30).…..31(30)
30402457………………………………………………………… ………………………………………………………………..
…………M42..25964951
………………………….…M41..24036583
……………………………………………………………………………… ………..…………………………..M40..20996011
M39..13466917…
……………………………………………………………………………… ……..M38..6972593
…………………………………………….…M37..302137 7
………..M36..2976221
……………………………………………………………………………… ……………………….M35..1398269
M34..1257787
……………………………………………………………………………… ……..M33..859433
……………………………………………………………………………… ………………………..M32..756839
……………………………………………………………………………… ……………………………………..M31..216091
…………………………………………………………………M30.. 132049
……………………………M29..110503
……………………………………………………………………………… …….M28..86243
M27..44497
………………………………………………………………..M26. .23209
………..M25..21701
……….……………………………………..M24..19937
……………………………………………………………………………… …….M23..11213
……..…M22..9941
……………………………………………………………………………… ………………………..M21..9689
………………………….M20..4423
……………………………………………………………………………… …….M19..4253
M18..3217
……………………………………………………………………………… ……………………………………….M17..2281
…………………………M16..2203
………………………………………………………………..M15. .1279
M14..607
……….M13..521
M12..127
…….………………………………………..M11..107
……………………………………………………………………………… ………………………..M10..89
……………………………………………………………………………… ……………………………………….M9..61
……………………………………………………………………………… ……………………………………….M8..31
………………………………………………………………..M7.. 19
……………………………………………….M6..17
…………………………..M5..13
M4..7
pourrait on supposer à juste titre, que le prochain exposant P serait dans la série 19(30)..? l'écart passe trés rarement une absence de 13 nombres par série.??
des idées ....?
on voit que la dernière fois que P =11(30),puis7(30) ensuite 19(30)
deux séries ont eu un écart de 14 nombres, mais la série 23 c'est bien rattrapé ensuite..
A+
Tu devrais apprendre à faire des tableaux avec LaTeX, parce qu'on ne peut pas dire que ce soit très clair ...
heu... je pense qu'il faudrait refaire ce tableau car je ne pense pas forcément qu'il soit inintéressant, mais illisible pour le moment c'est clair !
j'ai refait ton histoire de mod 30...
vous pouvez aller le voir ici: http://www.hacking.free.fr/mersenne%20modulo.htm
la seule chose que je trouve étonnante est que effectivement il y a assez peu de chances pour que si les exposants de mersenne étaient rangés au hasard dans les colonnes du "mod 30" ils soient aussi bien répartis...
sinon, regarder les mersennes mod30 n'a évidement aucun intéret
(essaye de comprendre déja pourquoi quand l'exposant est un nombre de sophie germain il n'est pas 3mod4 !)
Tres interessant je trouve...
Y a t'il une explication sur le fait qu'en Mod(30), tous les mersenne donnent des nombre premier (excepté 1) ?
___ j'ai une question rigolotte: pourquoi presques tous les 2^n-1 sont divisibles par 2*n+1 !
(si 2^n-1 non premier, alors il y a ..... beaucoup de chances pour qu'il soit divisible par 2*n+1!)
oui... elle est toute bête_______________________
un nombre non premier infèrieur à 30 est forcément divisible par 2,3 ou 5
donc si p = a mod 30 et a est non premier c'est que p n'est pas premier non plus !
(quand tu prends le reste de la division de tous les nombres premiers supérieurs à 30, tu obtiens un nombre premier...)
pareil pour tout modulo p#, où p# > q^2 où q est le prochain nombre premier après p!
sauf que 2x3x5x7 = 210 et 11^2 = 121
donc ça ne marche que avec 2, 6 et 30...
(p# = le produit de tous les nombres premiers de 1 à p)
Dernière modification par acx01b ; 15/01/2006 à 18h17.
quand même pas si illisible, à part la série 29 et 31 (30) qui s'est décalé alors qu'en prévisualisation ce n'était pas le cas.
ce que j'ai voulu montrer c'est l'ordre de sortie des Mn
dans cet Ensemble P(30) le lien que tu indiques en fait état dans sa colonne mod 30
j'ai voulu joindre ce fichier Word ,je n'y arrive pas.
pourtant je vais sur gerer les pieces jointes ,parcourir,et ensuite uploader et ça ne marche pas..?
avec n premier ?
non... avec n entier positif > 1
tou nombre premier > 5 est = P(30) pour P premier < 31
mais 1 est remplacer par 31 car il suprimerait dans cet algorithme tous les nombre premiers.
ce qui donne 8 séries P(30)
les Mersennes sont 31(120) ,31(510) 7(120) plus simplement 31 ou 7 (30)ils sont donc dans ces deux séries.
hors sujet.
[" les Fermats sont dans la Série 17(30) soit 17(240)plus précisément de la forme am+1
avec a pair = 16 et m une puissance de 2
la série 23 et 29 donne des nombres premiers =17(240),
a = 22 et a = 28 autrement dit ces deux série rejoigne la série 17(30)
comme le font 3 et 5
en commençant de la façon suivante
Fn = 17 ;(17 – 1)2 + 1 = 257 P , 65537 P , 4294967297 c
Fu = 23 ;(23 – 1)2 + 1 = 485 c , 234257 c =17 (240) > à 65537
Fv = 29 ;(29 – 1)2 + 1 = 785 c , 614657 P =17 (240) > à 65537 .
Fn = 3 ; (3 – 1)2 + 1 = 5 p, 17 p
a chaque fois je réitère (Fn -1)2+1,
je pense que l'on trouvera d'autre Fermat 1er
superieur à 65537.
j'avais posé une fois cette question, mais sans réponse ,pas ici,:
existe t’il un polygone à P côtés égaux, pour : P = 614657 ? ou doit il commencer impérativement avec a = 2 tel que a2 n+1 "]
C'est que pour les images.
Mais pour mettre d'autres fichiers, tu fais ton site chez Wanadoo ou chez free. Normalement tu as droit à
100Mo gratuitement.
@+
chez Wnadoo pole, mais comment joindre un fichier.
(j'espère que tu as bien commencé 2006..)
9.32% sous Prime95 pour mon mersenne de presque 38 millions (mais je pense que je devrais plutot me rejouir quand il atteindra les 80%)
excusez mon emportement...
mais il y a en fait très peu de 2^x-1 où x n'est pas forcément premier qui sont divisibles par 2x+1
en fait il y a tous ceux où un des facteurs premiers p, de x est 3mod4, et 2p+1 premier ?
où il y en a-t-il d'autres ????
cela est tres bien expliqué sur wikipédia...
Oui je l'ai bien commencé.
Pour le site, il faut aller tout à gauche de la page d'acceuil et cliquer sur le lien "pages perso" dans la rubrique "Services". Après, prendre "confimé". Wanadoo envoie ensuite un message.
Pour envoyer un fichier sur internet, il faut aussi prendre Filezilla (il y en a d'autres, mais lui est gratuit).
Normalement, tu as de l'aide pour continuer.
A+
Nombre de Mersenne & cribleurs
R E V E L A T IN
Bon, je vais vous reveler ce que j'ai decouvert sur les cribleurs de mersenne :
Prenez un mersenne a tester. Par exemple M(11)
Vous multipliez 11 par 2 et vous ajoutez 1. Cela donne 23. Si 23 est un nombre voisin de 8X, votre mersenne a pour cribleur la "branche des 2"; sinon, la "branche des 6" (je vais y revenir).
23 est voisin de 3*8=24 donc, les cribleurs de M(11) sont de la branche des 2.
Qu'est ce que ces histoires de branches ?
Les nombres sont a classer dans 4 branches :
8x+2 (conserne 50% des mersenne)
8x+4 (Inutile)
8x+6 (conserne 50% des mersenne)
8x+8 (conserne 100% des mersenne)
Voici les formules qui donnent les cribleurs d'un mersenne :
(8x+2)*np+1 et (8x+8)*np+1 : ces 2 branches concernent tous les mersennes issu de la branche des 2
Sinon :
(8x+6)*np+1 et (8x+8)*np+1 : ces 2 branches concernent tous les mersennes issu de la branche des 6
La valeur 'X' est a faire progresser de 0 a Y (En fait, jusqu'a ce que les 2 branches atteignent la racine carré du mersenne a tester).
Un exemple :
M(11) a pour cribleurs les nombres issu des formules :
(8x+2)*np+1 et (8x+8)*np+1
C'est a dire :
Pour (8x+2)*np+1 : 23; 111; 199; 287;....
Pour (8x+8)*np+1 : 89; 177; 265;.....
Puisqu'il faut aller jusqu'a la racine de M(11), c'est a dire jusqu'a 45. Mais j'ai developper les branches pour vous montrer plusieurs chiffres.
On sait que M(11)=2047 est divisible par 23 et que 2047/23=89.
Il s'avere que pour un chiffre de la branche des 2 et qui est un reel cribleur du mersenne, il correspond obligatoirement a un cribleur reel de la branche des 8.
NP*2+1 voisin de 8X ? Retenez ca. Ca defini où 50% de vos cribleurs sont... (les autres 50% sont TJR dans la branche des 8)
Chaque mersenne a ainsi ses propres cribleurs.
Par exemple, pour tester M(37), on ne teste 'que' 2005 chiffres (en ayant retiré les 20% de nombres finissant par 5). Cela est peu mais ca deviens exponentiel quand on teste un mersenne de quelques millions.
Attention, je ne l'ai pas précisé mais les 2 branches donnant les cribleurs peuvent etre epuré des nombres non premiers qui ne servent a rien. Cela restreint les nombres a tester.
Derniere chose : parmi tous les nombres produits par les 2 branches, seul 10% sont vraiment important. Les trier est complexe et demande plus de temps que les utiliser. Il s'agit de savoir si le cribleur potentiel a un ADN (et oui, on en reviens a ca et j'ai d'ailleur fait une formidable decouverte que je garde pour le moment).
Tenez, regardez ce que donne la branche des 8 pour cribler M(37). Seul sont vraiment utile tous les nombres premiers ayant un ADN (entre []) :
http://xmas.free.fr/np/m(37).txt
Evidement, pour ceux qui ont suivi mes experiences sur l'ADN, en fait, quand on en viens a calculer l'ADN d'un cribleur, il n'y a meme plus a calculer quoi que ce soit. L'ADN dit si il crible le mersenne.
Exemple, la liste de M(11) donne :
23[11]
89[11]
Donc, on peux stopper tout calcul car 23 crible 2047
Dernière modification par SPH ; 16/01/2006 à 19h52.
Leg vous adresse ces 2 fichiers .DOC :
http://xmas.free.fr/np/leg/
Bon, sinon, ce que je vous ai exposé n'a pas l'air de vous inspirer... Why ?!?
J'ai etudié le test de Lucas et je dois dire quelque chose. Faire 30 millions de fois le test de lucas pour atteindre le fameux nombre que l'on essayera de diviser par le mersenne doit prendre beaucoup de temps. Il devrait exister une reference du test a 30 million pile et qui devrait etre telechargeable sur le net. Comme c'est tjr le meme nombre arrivé a 30 million, autant le conserver. Il resterait a completer avec quelques millions pour tester le nombre que l'on a choisi.
A moins que sous prime, les 30 millions de cicles de Lucas soit negligeable... Je ne connais pas la proportion du temps reparti entre les cicles de lucas et la division finale...
lol
disons que S1 = 4
Sn < 42n
par contre Sn > 32n
rien que sachant ça:
S30000 > 3230000
230000 = (un million)1000
heu ça te donne une idée du nombre de méga(mégamégamégamégamégamégam égamégamégamégamégamégamégamég amégamégamégamégamégamégamégam égamégamégamégamégamégamégamég amégamégamégamégamégamégamégam égamégamégamégamégamégaméga) OCTETS qu'il faudrait pour écrire S30 000 000
ce qu'il faut bien comprendre c'est que 2100100 n'est pas égale à 2100
Dernière modification par acx01b ; 17/01/2006 à 18h17.
Ha, et bien je croyais que Prime95 faisait le test de lucas d'un bout a l'autre mais c'est vrai qu'un peu de reflexion permet d'ecarter cette improbabilité.
prime95 FAIT le test de Lucas d'un bout à l'autre.
Je ne vois pas comment on pourrait faire autrement et en plus rapide.
S20 est un grand nombre. Le temps de le télécharger et prime95 a fait 100 fois plus d'itérations.
A+
Comment peut il faire le test ne serait ce jusqu'a S1000000 ??
Car je me rend compte qu'ormi le "-2", ce sont des carré de carré de carré de carré.........
salut SPH et merci.
pour le test de lucas regarde le post de Tony rex un peu plus haut, il explique en gros ce que fait le test de lucas.
mais il fait d'un bout a l'autre les itérations .
et effectivement l'interêt serait de trouver une propriété qui permette de partir par ex; à la moitié,ou dans les trois dérniers carrés.
c'est pour cela que je regardais le nombre pair 2P = 2(2P-1). en relation avec les nombres parfaits pairs;Mais il est tout autant dificile de trouver un couple de diviseur pair ne contenenant pas une puissance de 2, pour ces nombres, puisque cela revient a chercher par exour 2P-1(211-1), 46 au lieu de 23,.
donc en allant directement sur l'avant dernière division de ce n parfait,on obtient le double de ce nombre de mersenne, qui en lui appliquant le teste de lucas ,qui fonctionne sur ce nombre pair, on obtient d'autre valeur et d'autre propriété, qui pour "l'instant" ne me donne pas de solution permettant de racourcir le test de L.Lh; (voir mon erreur remarquée par Tony.)
mais l'espoir fait passer agréablement le temps, je cherche sur les deux pistes, nombre parfait pair et les exposants dans l'ensemble P(30), dans le tableau que tu m'as mis sur le fil. en mettant les exposants sous les deux formes N = 2P +1, et N' = 2P-1 afin d'analyser les diviseurs P(30) de ces nombres N et N', en dehors des multiples de 3 et 5 qui divise fréquament N, ("en espérant en tirer une propriété...").
des que j'ai fini le tableau je te l'envoi.pour le mettre sur le fil, en te remerciant d'avance
A+
