nombre de Mersenne

[inviteb0cf188d]

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é.........

Le LLT consiste effectivement à mettre au carré des nombres de plus en plus grand. En fait très rapidement gigantesques. Dès le début, Edouard Lucas a bien vu la possibilité de simplifier les calculs et de profiter de la forme particulière des nombres de Mersenne. Comme le test dit que Mp est premier ssi S(p-1) est divisible par Mp, alors il suffit de faire chaque calcul modulo MP (C'est évident pour moi maintenant, mais cela peut vous demander de réviser les propriétés du modulo). Les carrés s'effectuent donc sur des nombres ayant p bits : la taille est fixe à chaque itération. Par contre, les calculs de LLT faits modulo un certain p ne peuvent pas être réutilisables pour une autre valeur de p.
Tony
-----

[invite3d7be5ae]

Maintenantque j'ai regardé le test pour 2^P-1*(2^P-1), je vois que c'est plus rapide.

Complexité pour le LLT : P carrés et P additions (Je ne compte pas le -2) : O(2*L*ln(L)+L) (L taille du nb)
Test du nb parfait (pair) :
soit n=2^P-1*(2^P-1)
On doit calculer :
(1+n)+(2+n/2)+(4+n/4)+(8+n/8)....(2^(P-1)+2^P-1)
Or 1+2+4+8+16+...2^(P-1)=2^P-1

algorithme pour le test :
n=2^P-1*(2^P-1);
nDeb=n;
somme=2^P-1;
faire P fois
somme=somme+n;
n=n/2;
(diviser par 2 revient à décaler de 1 en base 2)
fin
renvoi n==nDeb

Complexité : P*O(L)*2 (une addition+un décalage)
pour une taille de L

Voilà.

[acx01b]

je n'ai pas du tout compris à quel niveau il s'agit d'un "test"

que testes-tu ?
si 2^(p-1)(2^p-1) est parfait ?

à quel moment testes tu si c'est un nombre parfait ?
car à priori la seule chose que tu connais sur ce nombre (peut - être parfait ) c'est qu'il est le produit de 2^(p-1)
et de (2^p-1), mais malheureusement tu ne connais pas du tout les diviseurs de 2^p-1 !!!

[invite3d7be5ae]

Exact, je me suis complètement trompé.
Mais il n'y a pas que moi :

parfait pair = Z
Z que je divise par 2, j'additionne le diviseur et le quotien ,je réitère avec 4 ,puis avec 8,... jusqu'à P-1 et si ma somme = Z -1 alors 2^p -1 est premier.... non ?
puisque Z serait parfait.
dans le cas contraire la somme de ces diviseur et uniquement ces derniers ne devrait pas
me donner Z-1, du fait qu'il manquerait des diviseur et leurs quotients dans la somme.

(C'est dans le vieux fil : Est-ce une conjecture?)
Ce "test" donne donc toujours vrai et est donc inintéressant.
A+.

[SPH]

je suis actuellement en train de verifier la primalité d'un mersenne avec prime95. J'en suis a 44%
La répartition des non premiers est elle partout la meme quelque soit le pourcentage de prime ou bien les X premier % contiennent + de non premier que les Y% restant ?
evidement, je pense que c'est helas reparti d'une facon homogene mais je demande au cas ou je me trompe...

[leg]

salut sph.
si j'ai bien compris ta question, et lorsque l'on regarde dans le tableau P(30), les nombres de Mersenne prime par série P(30) donc dans l'ensemble des entiers P(30), ils sont tres bien réparti par série , mais il en est de même pour les entiers premiers, il y en a autant par série P(30).
Or M43, à comme exposant 30 402 457
avec l'algo que tu as, regarde combien il y a de nombres premiers jusqu'a cette limite par série P(30)
dans la série7(30) il y a 8 Mersennes et 5 dans les 7autres séries.
mais tu remarques que l'écart entre deux mersennes consécutif est tres variable et surtout tout autant variable par série,
par exemple M42 =11(30) et M36 =11(30),
la différence D entre ces deux exposants, et de 23000000 environ,
alors q'entre M43=7(30) et M39=7(30) , D = 17000000environ.
ce qui est interressant d'analyser c'est la nature de l'exposant P, soit 2P+1, et 2P-1.
si P=7(30), alors 2P-1= 13(30), et jusqu'à M43, 2P -1 était premier pour M39,34,27,14

2P+1, est multiple de 5 et de 3, puis d'un produit de deux facteurs premiers, dont l'un de ces facteur et toujours congrue soit 17(30) ou 11(30)

exemple pour M43;2P+1= 5*3*1(30)
où le produit 1(30) = 17(30) * 23(30); soit 257*15773

chaque série P(30), représente 3.3333..% des entiers >0

le seul constat que l'on peut faire, c'est que deux Mersennes ne sont jamais égale à P(30) de la même série, à l'exeption de M8 et M9
bon courrage.A+

[invite986312212]

à vous les spécialistes des nombres de Mersenne, pourquoi cherche-t-on des grands nombres premiers de la forme 2^p-1, et pas 3^p-2 par exemple, voire d'autres formes de ce style?

[SPH]

à vous les spécialistes des nombres de Mersenne, pourquoi cherche-t-on des grands nombres premiers de la forme 2^p-1, et pas 3^p-2 par exemple, voire d'autres formes de ce style?

Parce qu'il y a longtemps, quelqu'un s'est interessé à la forme 2^p-1. De la, une "competition" est née. Mais rien ne t'empeche de chercher a ta guise des premiers de forme x^y-z...

[invitebdaccd77]

à vous les spécialistes des nombres de Mersenne, pourquoi cherche-t-on des grands nombres premiers de la forme 2^p-1, et pas 3^p-2 par exemple, voire d'autres formes de ce style?

D'abord il est très difficile de prouver la primalité d'un nombre N si on ne sait pas factoriser pour au moins 33% N-1 ou N+1. Ca explique le -1 et non -2.

Ensuite un nombre de la forme a^n-1 ne peut être premier que si a=2 et n est premier. Ce sont les nombres de Mersenne.

Pour les nombres d la forme a^n+1 il faut que n soit une puissance de 2. Ce sont les nombres de Fermat généralisé.

Il y a beaucoup d'autres formes recherchées mais les algorithmes les plus rapides concernent les forme k*2^n+-1 avec k pas trop grand (quelques centaines). Les plus simples de ces nombres sont les nombres de Mersenne...

Tu peux voir les 5000 plus grands nombres premiers connus sur:

http://primes.utm.edu/primes/home.php

Va voir le top 20, tu verras un bon panel de forme de nombres premiers recherchés.

[leg]

à vous les spécialistes des nombres de Mersenne, pourquoi cherche-t-on des grands nombres premiers de la forme 2^p-1, et pas 3^p-2 par exemple, voire d'autres formes de ce style?

je pense que c'est a cause de la méthode pour prouver qu'un grand nombre est premier, que l'on cherche dans les nombres de Mersenne le test est "relativement" rapide

fait la même chose avec 3^30402457 - 2, suppose que ce nombre ne soit pas multiple de 5, ("c'est a dire que l'exposant = 7(60)") mais =1(30) si l'exposant = 37(60)qu'elle test rapide existe t'il ?

[leg]

sph
dans qu'elle série tu a choisis ton exposant?
pour le Mersenne que tu test actuellement

voila ce que cela donne depuis 2^7 - 1
les 8 séries numérotés de 1 à 8 , 1 = S1, 2 = S7....8 = S29

la sortie des Mersennes Premiers dans les Série P(30):
2.4.5.6.1.1.8.5.2.3.2.6.4.1.2. 7.4.8.3.7.5.3.6.2.7.4.6.1.8.7. 2.8.3.5.7.2.1.4.3.2
la seule série qui ne soit sortie aprés la série 2 c'est la série 5 = 17(30) , Mais la série 6=19(30) est sortie une fois, de suite après la 2ème série =7(30) de plus cette série 19(30) est trés en retard.
("il doit peut être, être possible de calculer une probabilité.")

[SPH]

sph
dans qu'elle série tu a choisis ton exposant?

J'ai pris au plus grand des hazards un nombre qui m'avait "intrigué" visuellement. Rien de bien concret quoi...
Je ne sais pas de quelle serie il est mais je ferais signe ici quand prime aboutira...

[Snake's Radio OFF]

[acx01b]

mais ça sert à rien votre histoire de série p(30) !

[leg]

mais ça sert à rien votre histoire de série p(30) !

pourquoi? si tu as une bonne raison alors peut être...

pour l'instant il est plus ou moins facile de travailler que sur 3.33333% des entiers naturels ..

[invite3d7be5ae]

je suis actuellement en train de verifier la primalité d'un mersenne avec prime95. J'en suis a 44%
La répartition des non premiers est elle partout la meme quelque soit le pourcentage de prime ou bien les X premier % contiennent + de non premier que les Y% restant ?
evidement, je pense que c'est helas reparti d'une facon homogene mais je demande au cas ou je me trompe...

Le pourcentage de prime95 est le pourcentage du calcul. Tu as fait 44% du calcul pour ce nb de Mersenne.
Pole.

[SPH]

Le pourcentage de prime95 est le pourcentage du calcul. Tu as fait 44% du calcul pour ce nb de Mersenne.
Pole.

now : 60.67%
Ce que je me demandais, c'est si le test de lucas est une technique dans laquelle les nombres premiers sont aussi uniformement réparti que pour la suite 1 a X.
J'esperais que les X premiers pourcentages de lucas elimine + de non premier que les derniers pourcentages mais bon, je posais cette question en me disant quand meme qu'il ne fallait pas que je reve.

[inviteb0cf188d]

Je ne suis pas sûr que tu comprennes bien le LLT.
Tu est à 60.67% du test de l'exposant P que tu as donné à prime95.
Tu testes donc la primalité d'un UNIQUE nombre (de Mersenne).
Quand prime95 aura fait toutes les itérations, tu sauras uniquement si ce nombre 2^P-1 est premier ou pas.

A moins que je ne comprenne pas ce que tu veux dire ...

[acx01b]

salut Trex,
as-tu d'autres démonstrations (liens?) sous la main du LLT, enfin de la 2ième partie (si 2^n-1 un diviseur de S[n-2] alors 2^n-1 premier) que celle donnée sur mersennewiki.org ? merci d'avance !

[SPH]

Je ne suis pas sûr que tu comprennes bien le LLT.
Tu est à 60.67% du test de l'exposant P que tu as donné à prime95.
Tu testes donc la primalité d'un UNIQUE nombre (de Mersenne).
Quand prime95 aura fait toutes les itérations, tu sauras uniquement si ce nombre 2^P-1 est premier ou pas.

A moins que je ne comprenne pas ce que tu veux dire ...

si si, tu as tout compris.
Je teste bien un seul nombre de mersenne et j'en suis a 61% maintenant. S'il est premier, je le saurais en atteignant 100%.

[invite3d7be5ae]

salut Trex,
as-tu d'autres démonstrations (liens?) sous la main du LLT, enfin de la 2ième partie (si 2^n-1 un diviseur de S[n-2] alors 2^n-1 premier) que celle donnée sur mersennewiki.org ? merci d'avance !

J'ai déjà vu la démo sur internet en français (dans un site de cryptographie).
En fait, la deuxième partie est juste une vérification que le nb final est égal à 0.

Pole.

[inviteb0cf188d]

salut Trex,
as-tu d'autres démonstrations (liens?) sous la main du LLT, enfin de la 2ième partie (si 2^n-1 un diviseur de S[n-2] alors 2^n-1 premier) que celle donnée sur mersennewiki.org ? merci d'avance !

Le chapitre du livre de P. Ribenboim qui parle de la preuve du LLT est disponible à Springer.
C'est une version totalement différente et plus longue, basée sur les suites de Lucas. Mais elle est intéressante et très instructive. Elle permet d'apprendre pas mal de choses. Elle est proche de ce que Lucas et Lehmer ont fait, mais quand même différente. Mais avec une grosse erreur (ou limitation non justifiée) en page 63 et suivantes : les théorèmes données sont dits ne s'appliquer qu'aux nombres N dont on connaît la factorisation complète de N+1, comme les nombres de Mersenne. En fait toute cette partie est aussi valable pour les nombres N dont on connaît la factorisation complète de N-1, comme les nombres de Fermat.
Voir pages 44 et suivantes, et pages 77-78 pour la preuve pour les nombres de Mersenne.
Pour une preuve du LLT à la mode Lehmer pour les Nombres de Fermat, voir : LLT for Fermat Numbers. J'y explique plusieurs détails évidents pour les forts en Maths, mais plus délicats pour les amateurs comme moi ... (Je ne suis pas Mathématicien ...)
Je vous recommande l'achat de ce formidable livre: The Little Bool of Bigger Primes. en attendant la sortie de la version française du livre de Hardy chez Springer (dans moins d'un an j'espère).
Tony

[SPH]

Je crois ne pas me tromper si je dis qu'il est assez facile de trouver la factorisation complete de N de l'expression 2^n-1; meme si N>30000000
Donc si le test pour prouver la primalité du mersenne(N) est simple et "rapide", alors oui, cela semble interessant...

[invite3d7be5ae]

Je crois ne pas me tromper si je dis qu'il est assez facile de trouver la factorisation complete de N de l'expression 2^n-1; meme si N>30000000
Donc si le test pour prouver la primalité du mersenne(N) est simple et "rapide", alors oui, cela semble interessant...

Tu vois bien que le LLT est simple et rapide comparé aux autres tests.
Pour les courbes elliptiques : 15000 chiffres.
Et effectivement, c'est intéressant.

Pole.

[acx01b]

merci T.rex ! oui la version française ça serait plus sympas quand même !

SPH: je te rappelle que il s'agit de nombres à plus de 10 millions de chiffres décimaux dont on parle, donc à moins d'avoir une anomalie génétique congénitale et de la chance, je crois vraiment qu'il est très difficile de trouver la factorisation d'un tel nombre !

[invite3d7be5ae]

SPH: je te rappelle que il s'agit de nombres à plus de 10 millions de chiffres décimaux dont on parle, donc à moins d'avoir une anomalie génétique congénitale et de la chance, je crois vraiment qu'il est très difficile de trouver la factorisation d'un tel nombre !

Je pense que SPH voulait dire N+1 ce qui change vraiment tout.
(N+1 car le LLT a un rapport avec les suite de Lucas qui permettent de prouver la primalité d'un nombre en factorisant N+1 (et d'autres trucs, bien sûr))

Pole.

[SPH]

Je pense que SPH voulait dire N+1 ce qui change vraiment tout.
(N+1 car le LLT a un rapport avec les suite de Lucas qui permettent de prouver la primalité d'un nombre en factorisant N+1 (et d'autres trucs, bien sûr))

Pole.

oui, je parlais de ca et pas du resultat du mersenne !

Bon, autre chose, on va voir si vous raisonnez comme moi. Je dis que finalement, hormis le "0%" du debut, on a autant de pourcentage de chance de trouver un mersenne premier (avec prime95) qu'il y a de pourcentage de calcul effectué.
Exemple, là, j'en suis a 62.42% sous prime. Je peux donc dire que le nombre que je teste a 62.42% de chance d'etre premier !
Et oui, puisque 62.42% des calculs ont ete fait !!!!

[invite3d7be5ae]

Non, tu n'as vraiment pas compris.

La chance de tomber sur un nb de Mersenne premier est donné en cliquant sur status.

Avec le LLT, on est obligé de faire tous les calculs, et regarder à la fin si ton nombre est premier ou pas. On ne peut pas, en cours de route, savoir si le nb est premier ou pas.(sauf cas particuliers : -1,2,0,-2)
Je te conseille de revoir la définition du LLT.

Pole.

[SPH]

Non, tu n'as vraiment pas compris.

La chance de tomber sur un nb de Mersenne premier est donné en cliquant sur status.

Avec le LLT, on est obligé de faire tous les calculs, et regarder à la fin si ton nombre est premier ou pas. On ne peut pas, en cours de route, savoir si le nb est premier ou pas.(sauf cas particuliers : -1,2,0,-2)
Je te conseille de revoir la définition du LLT.

Pole.

...........
Prime95 peux s'arreter a x% pour dire que le mersenne testé n'est pas premier, n'est ce pas ???? (en tout cas, j'ai tjr compris ca moi !!!!!!!!)

[invite3d7be5ae]

...........
Prime95 peux s'arreter a x% pour dire que le mersenne testé n'est pas premier, n'est ce pas ???? (en tout cas, j'ai tjr compris ca moi !!!!!!!!)

C'est bien cela le problème. Il faut faire tout les calculs.
S₀=4 S_n=S_n-1^2-2
Et M(p) est premier ssi S_p-2=0 mod M(p).
Prime95 est entrain de calculer les différents S. Il te dit qu'il a calculé 60% de tout les S. Après, il regardera si le dernier nb obtenu est égal à 0. Si oui, le nb est premier. Si non, le nb est composé.

Pole.

[SPH]

Après, il regardera si le dernier nb obtenu est égal à 0. Si oui, le nb est premier. Si non, le nb est composé.
Pole.

AIE AIE AIE
Je croyais que si le "0" ne sortait pas avant la derniere operation, il ne pouvait etre que le resultat de la toute derniere !!!!!