nombre de Mersenne

[SPH]

Encore pardon :

Pour M(29), je ne teste que 158 nombres.
Et pour M(23), je n'en teste que 22.

(oui, je ne dois pas me precipiter car j'ai decouvert queklques elements tres interessants)
-----

[inviteb0cf188d]

bonjour, je me suis amusé en modifiant WorkToDo.ini à lui faire essayer 2^6972593-1 (qui est premier découvert en 1990...)
Il me dit au bout d'une heure que il a: "factoring M6972593 to 2^61 is 21.21% complete Time: 235sec"
Qu'est-ce que veut dire le 2^61 ??
qu'il a fait 2^61 opérations ???
combien doit-il en réaliser EN TOUT ????
salut merci d'avance

J'ai l'impression que les posts suivants n'ont pas vraiment répondu à ta question.
Les nombres de Mersenne sont de la forme : où q est premier.

On sait que certains q premiers ne marchent pas. Si je me souviens bien : si est premier alors p divise Mq. Exemple : 2*11+1=23 et 23 divise bien M11=2047=23*89 . Donc ces exposants sont à éviter ... Peut-être même que prime95 les détecte ...

Phase 1
Les diviseurs de Mq sont de la forme : .
Donc, prime95 commence par essayer tous les nombres premiers de cette forme jusqu'à un maximum, 2^68 je crois, peut-être moins. Donc, prime95 t'informe qu'il a fait 21 % des nombres premiers candidats diviseurs de ton nombre de Mersenne, qui sont plus petits que 2^61. Après, il passera à 2^62 ....

Phase 2
Ensuite, prime95 cherche encore des diviseurs de Mq, mais selon une méthode différente et trouvant des diviseurs plus gros.

Phase 3
Enfin, il se dit qu'il y en a marre, et qu'il faut passer aux choses sérieuses : passer le test LLT, qui nécessite q-2 itérations.

Alors, pourquoi faire les phase 1 et 2 ?
- Pour trouver un facteur de Mq, qui agrandira la connaissance des nombres de Mersenne.
- Probablement parce que la probabilité de trouver un diviseur compense le temps perdu avant de commencer le LLT. Mais vu le peu de facteurs que j'ai trouvés (2 je crois), pour une 40aine d'exposants, je ne sais pas si c'est rentable.

Lorsque l'on dit à prime95 de se connecter à PrimeNet, cela signifie que le serveur attribue des exposants - soit pour faire la factorisation (si le PC est peu puissant), - soit pour faire le LLT.
C'est principalement en allant demander des exposants à tester "manuellement" sur le site de Prime95 qu'on obtient des exposants grands qui n'ont pas encore passé les phases 1 et 2.

On peut aussi utiliser prime95 pour chercher des facteurs des nombres de Fermat.

Il existe aussi une variante de prime95 pour les nombres du type : , avec une version particulière du LLT, partant d'un nombre différent de 4.
Voir LLR, à utiliser après NewPGen.
Mais c'est une autre histoire.

Tony

[leg]

bonjour a tous ,merci tony pour ces explications.

pole tu es sur que (2 (2³¹ -1)) +1 est premier.

question a tony : c'est normal que le test de lucas.lh fonction pour le nombre pair :2 (2³¹ -1);
à la fin du test, P -1, les valeurs prisent sont le double ,par ex pour 127 on obtient (111² - 2)/127 = 97 et pour 254, (x² -2)/254 = 223 soit, (111*2) +1...?
qui curieusement divise 2³⁷-1..

[invite3d7be5ae]

...
pole tu es sur que (2 (2³¹ -1)) +1 est premier.
...

Je n'ai pas dit ça.
J'ai dit que M(M(21)) (=2^231-1-1)
n'est pas premier.

Pour M(29), je ne teste que 158 nombres.
Et pour M(23), je n'en teste que 22.

(oui, je ne dois pas me precipiter car j'ai decouvert queklques elements tres interessants)

Tu peux les écrire?

[acx01b]

si je comprends bien , les phases 1 et 2 sont TRES intéressantes pour un Mersenne avec un exposant "petit" (infèrieur à 1 000 000 par exemple)

mais vu que tous les mersennes ont été essayés jusqu'à
2^6 972 593-1... il vaut mieux abandonner les phases 1 et 2 !!!!

[inviteb0cf188d]

si je comprends bien , les phases 1 et 2 sont TRES intéressantes pour un Mersenne avec un exposant "petit" (infèrieur à 1 000 000 par exemple).
mais vu que tous les mersennes ont été essayés jusqu'à
2^6 972 593-1... il vaut mieux abandonner les phases 1 et 2 !!!!

Non. Je ne vois pas ce qui t'amène à penser que ces phases ne sont utiles que pour des exposants petits de nombres de Mersenne.
Dans la formule : d=1+2qk , le k peut aller de 1 à 2^12 environ pour avoir d plus petit que 2^67. Donc cela un fait un paquet de nombres premiers candidats à essayer. Effectivement, comme les exposants croissent (doucement) régulièrement, la probabilité de trouver un diviseur de Mq dans cette plage doit diminuer aussi. Mais je pense que si George Woltman a laissé ces phases, c'est qu'elles sont utiles. Il connaît son affaire !
Tony

[SPH]

Tu peux les écrire?

Je pourrais, mais je suis en train de finir de mediter sur ma derniere trouvaille.
Pour l'instant, je ne dirais que ca :

Tous les cribleurs de Mersenne sont issu d'une branche commune dont j'ai tiré la formule.
Une 2eme branche s'adresse a 50% des mersenne tandis qu'une 3eme s'adresse a l'autre 50%.

Egalement :
Il n'existe AUCUN cribleur potentiel pour M(2); M(3); M(5) et M(7); donc, il ne pouvaient etre que premier ! Pour M(11), 2 des quelques cribleurs ont fait mouche : le 23 et le 89.

Enfin, je conjecture que les cribleurs (qui reussissent a cribler un mersenne) sont toujours en nombre pair et que jamais un nombre premier mis au carré ne criblera un mersenne.

[leg]

. Mais je pense que si George Woltman a laissé ces phases, c'est qu'elles sont utiles. Il connaît son affaire !
Tony

d'autant plus qu'il existera toujours des P=2q+1, premiers , divisant Mq, sinon on pourrait supposer que les Mq premier vont finir par augmenter..

[inviteb0cf188d]

jamais un nombre premier mis au carré ne criblera un mersenne.

C'est effectivement une conjecture connue sur les nombres de Mersenne composites !
Tony

[acx01b]

Citation:
Posté par acx01b
si je comprends bien , les phases 1 et 2 sont TRES intéressantes pour un Mersenne avec un exposant "petit" (infèrieur à 1 000 000 par exemple).
mais vu que tous les mersennes ont été essayés jusqu'à
2^6 972 593-1... il vaut mieux abandonner les phases 1 et 2 !!!!

Non. Je ne vois pas ce qui t'amène à penser que ces phases ne sont utiles que pour des exposants petits de nombres de Mersenne.
Dans la formule : d=1+2qk , le k peut aller de 1 à 2^12 environ pour avoir d plus petit que 2^67. Donc cela un fait un paquet de nombres premiers candidats à essayer. Effectivement, comme les exposants croissent (doucement) régulièrement, la probabilité de trouver un diviseur de Mq dans cette plage doit diminuer aussi. Mais je pense que si George Woltman a laissé ces phases, c'est qu'elles sont utiles. Il connaît son affaire !
Tony

oui sauf que peut-être cheche-t-il aussi en plus de trouver des mersennes premiers à trouver des mersennes divisibles par des petits nombres !!!!

enfin pour les petits mersennes la méthode 2kp+1 est évidement la plus rapide, et je te rappelle qu'il a également cherché (et réussi) à tester tous les mersenne jusqu'à 6millions !

donc je me pose la question: les phases 1 et 2 sont-elles presques inutiles...

[SPH]

Mon Mersenne que je teste et qui est tres proche de 38 million a 6.77% d'etre premier !

Sinon, qui est daccord avec Leg pour dire qu'il y a un ou des criteres particuliers pour choisir un bon nombre premier afin de le tester en tant que mersenne ??
(j'ai relu plusieurs articles et quelqu'un a dit qu'a ce niveau (un M(qque million)) les chiffres ne veulent plus rien dire)
Qui dis quoi ?

[inviteb0cf188d]

On sait que certains q premiers ne marchent pas. Si je me souviens bien : si est premier alors p divise Mq. Exemple : 2*11+1=23 et 23 divise bien M11=2047=23*89 . Donc ces exposants sont à éviter ... Peut-être même que prime95 les détecte ...

Personne n'a vu la bourde !!!!????
C'est bien sûr faux pour q=5 : 2*5+1=11 et 11 ne divise pas 31 qui est premier !
En fait, il faut aussi :

et !!!

(Dixit "The Little Book of Bigger Primes" !)
Tony

[leg]

puisque dans l'ensemble P(30) les multiples de 3 et 5 n'y figure pas il ne peut y avoir q =3 ou 5...
donc la "bourde" n'est pas méchante..Mn > 31 = 1 ou 7(30), ou: 31 ou 7(120) "et certain 31(510) "

[leg]

donc je me pose la question: les phases 1 et 2 sont-elles presques inutiles...

pour quelle raison? il est utile déjà de controler Mp en le divisant par 2p +1
ex: Mp =2²³-1; p=23 et (23*2)+1 divise Mp
il y aurra à mon avis toujours des exposant de ce type
et cela ne prend que trés peu de temps pour faire cette phase comme l'a expliqué T.rex.
je ne vois vraiment pas ce qui gène d'éffectuer cette phase, avant de passer au test complet de L.L

[leg]

Mon Mersenne que je teste et qui est tres proche de 38 million a 6.77% d'etre premier !

Sinon, qui est daccord avec Leg pour dire qu'il y a un ou des criteres particuliers pour choisir un bon nombre premier afin de le tester en tant que mersenne ??
(j'ai relu plusieurs articles et quelqu'un a dit qu'a ce niveau (un M(qque million)) les chiffres ne veulent plus rien dire)
Qui dis quoi ?

SPH on peu dire que si, avec ton algo ontrouve plus rapidement un nombre parfait pair , alors c'est un bon critere pour trouver un Mn quelque soit le nombre de chiffre..
mais déjà T.rex a répondu et indiqué des critères dans son post plus haut.

par ex aussi: le test de lucas fonctionne pour Mp premier et leur double ce que je ne savais pas. On pourrait dire que c'est normal puisque c'est un multple de Mp; or celà ne fonctionne pas en multipliant par 4..
par ce moyen ,il y a peut être une piste pour raccourcir le tes de lucas ou trouver d'autre propriété..
comme par ex , a la fin du test executé sur (127*2) = 254 , la dernière valeur est 238 ,(238² - 2)/254 = 223
pour 127 la dernière valeur est 111, (111*2)+1...
le prochain mersenne dans la série 7(30) se trouve être 37 , et comme par hasard 2³⁷- 1, est divisible par 223 , ce n'est peut être qu'une coincidence parmis tant d'autre. mais cela me fait chercher.... comme toi d'ailleur....

[inviteb0cf188d]

puisque dans l'ensemble P(30) les multiples de 3 et 5 n'y figure pas il ne peut y avoir que q =3 ou 5...

?? Pas vraiment.

q premier et donnent : 3, 7, 11, 19, 23, 31, 43 ...

Les exposants q qui donnent des Mq premiers se partagent assez bien entre : et .
Donc, ma mauvaise définition auraient mis hors jeu la moitié des exposants qui ont généré des Mq premier: 19, 31, 107, 127 ...

Tony

[inviteb0cf188d]

(j'ai relu plusieurs articles et quelqu'un a dit qu'a ce niveau (un M(qque million)) les chiffres ne veulent plus rien dire)
Qui dis quoi ?

Je n'ai pas bien compris ce que tu fais (je n'ai pas relu tous les Posts précédents ...). Mais il y a une loi connue en Mathématiques : à partir d'exemples, on peut construire des conjectures. Le problème est que si l'on prend des petits nombres, la probabilité de "voir" des relations intéressantes est plus forte que si l'on prend de grands nombres.
Donc, c'est une très bonne idée d'explorer des idées avec des petits nombres (c'est plus facile !), mais ensuite il faut trouver des exemples portant sur des grands nombres, et puis il faut trouver le domaine exacte des nombres où s'applique la loi (par exemple, vrai pour , et enfin il faut fournir une preuve.
Pour les nombres de Mersenne (q premier donc), le problème est que les 2 premiers Mersenne composites apparaissent pour q=11 et 23, qui obéissent à la règle 2q+1 dont j'ai parlé plus haut.
Donc, le vrai premier Mersenne composite quelconque apparaît pour q=29 : 223*1103*2089 . Cela commence à être gros.
Pour q=11 et q=23, je me souviens avoir trouvé des propriétés intéressantes, mais limitées à ces nombres ...
Tony

[leg]

a) trés juste pour ton explication, tony.

b)la question qui reste concernant le test de lucas.Lh.
tu es d'accord qu'il faut aller a la dernière itération = p -1, pour connaitre le résultat si Mq est premier.

or si on regarde cette dernière valeur qui doit être mise au carré ensuite je retranche 2 , et je divise par Mq..etc
comment se fait'il :
par ex 2³¹-1 je veux connaître cette valeur qui correspond à p -1, afin de la mettre au carré..etc

j'execute 2³³que je divise par 4, à ce quotient je retranche 65536,
("explication: pour 2¹⁹1, j'ai utilisé 2²¹ auquel j'ai retranché 1024 ,puis 1 donc pour aller jusqu'a l'exposant 33, il me faut retirer 65536 je multipli par 2 achaque fois)

donc je reprend (((2³³)/4) - 65536)-1 = la valeur de P -1 à mettre au carré d'où:
([(((2³³)/4) -65536)-1)]² - 2 )/ 2³¹-1 = quotient entier alors M31 est prime .....§

est ce le raccourci du test de lucas LH.????? sans faire toutes ces itérations?
je l'ai fait avec 13.17.19.31 pour 23 et 29 pas de quotient entier donc il ne sont pas premier.

[SPH]

Pour M(29), je ne teste que 158 nombres. Est-ce que je bas le test de Lucas ?

[leg]

Pour M(29), je ne teste que 158 nombres. Est-ce que je bas le test de Lucas ?

le test de lucas ne fait que 28 opérations et le tien 158 ..?
et en exempl moi pour 2²⁹-1, je ne fait qu'ne itération du test de lucas..

prend 2⁶¹-1 et aussi 2⁸⁹-1 et compare avec prime 95 puisque tu l'as charger.

ensuite tu peux toujours essayer avec 2⁶³-1
et faire les trois test, le tien, lucas et l'exemple que j'ai montré a mon dernier post..
2⁶³)/4)-2³¹)-1, le tout au carré, puis -2 et divise le résultat par 2⁶¹-1..
si le quotient est entier, M61 est prime
(on sait qu'il est premier).

[SPH]

le test de lucas ne fait que 28 opérations et le tien 158 ..?

Zut, j'aurais dû prendre en exemple M(31) car je ne sais pas si tu parles de 28 operation qui l'amene a certifier que M(29) n'est pas premier ou 28 operation au total.
Donc, je recommence :

Je ne fais que 300 operations pour M(31)
ps: 300 operations qui certifient a 100% que M(31) est premier.

[inviteb0cf188d]

... est ce le raccourci du test de lucas LH.????? sans faire toutes ces itérations?

Sincérement, je ne pense pas qu'il y ait de raccourçi au test LLT. Effectuer les q-1 étapes du test, c'est faire une longue balade au moyen du carré modulo le nombre. Faire une série d'opérations plus courte ne peut pas permettre de garantir la primalité du nombre de Mersenne testé. Par contre, il est possible qu'une série d'opérations plus courtes permette de déterminer un sous-ensemble de candidats ayant une probabilité plus forte d'être premiers.
Par exemple, le test LLT (en partant de 5) peut être utilisé pour prouver la primalité des nombres de Fermat (2^(2^n)+1). Dans ses papiers, Edouard Lucas pense qu'il pourrait suffire de faire les 3/4 des itérations pour avoir un test de primalité pour les nombres de Fermat. C'est vrai pour les n=2, 3 et 4. Mais il ne donne pas de preuve !

Dans ton exemple, il me semble que tu fais l'opération :
A = ( (2^n - 2^((n-1)/2) - 1)^2 - 2) / (2^n - 1)
Pour n=29, qui ne donne pas un nombre de Mersenne premier, A vaut 536805377 . Alors que tu dis trouver une fraction non entière.
Donc, cela contredit ton hypothèse, il me semble.

Utilises-tu Pari/gp ?

Tony

[leg]

M31, le test de lucas en partant de la Suite S₀ = 4, S₁= 4² -2..etc
il fait une opération qu'il réitère 29 fois ("la formule") ce qui donne 30 opérations pour confirmer si M31 est premier ou composé
(ceci dit, se ne sont que des tous petits petits nombres)

"à chaque itération, il y a un carré,une soustraction, une division, une multiplication est encore une soustraction jusqu'à l'exposant P-1"

[SPH]

M31, le test de lucas en partant de la Suite S₀ = 4, S₁= 4² -2..etc
il fait une opération qu'il réitère 29 fois ("la formule") ce qui donne 30 opérations pour confirmer si M31 est premier ou composé
(ceci dit, se ne sont que des tous petits petits nombres)

"à chaque itération, il y a un carré,une soustraction, une division, une multiplication est encore une soustraction jusqu'à l'exposant P-1"

C'est le test de Lucas qu'utilise Prime95 ?
Dans ce cas, pourquoi Prime est si long pour faire 30 milions d'operations pour des M(30 milions) ??

[inviteb0cf188d]

Je ne fais que 300 operations pour M(31)
ps: 300 operations qui certifient a 100% que M(31) est premier.

Le LLT ne fait que 30 opérations (élévation au carré). Ce qui est moins que 300.
Tes opérations portent-elles sur des nombres de la taille de Mq ?
As-tu une formule donnant le nombre d'opérations en fonction de q ?
Tony

[SPH]

Le LLT ne fait que 30 opérations (élévation au carr&#233. Ce qui est moins que 300.
Tes opérations portent-elles sur des nombres de la taille de Mq ?

Des nombres legerement moins gros

As-tu une formule donnant le nombre d'opérations en fonction de q ?
Tony

Pas PRECISEMENT (mais je crains que ce soit exponentiel)

[invite3d7be5ae]

Pas PRECISEMENT (mais je crains que ce soit exponentiel)

Prime95 à une complexité polynomiale : q opérations sur q bits : O(q^2) (pour tester Mq).

Mais si tu nous dis tes critères, on pourra évaluer la complexité.

[inviteb0cf188d]

"formule donnant le nombre d'opérations en fonction de q"
Pas PRECISEMENT (mais je crains que ce soit exponentiel)

Si ton algorithme porte sur des nombres plus petits mais avec un nombre exponentiel d'opérations, il peut être plus rapide sur des q petits ; mais il peut être plus lent, voire même beaucoup plus lent sur des q grands.
D'autre part, je parle d'"opérations". C'est sous-entendu : multiplication. Les additions ou soustractions coûtent presque rien à côté, et la division coûte plus cher (si je me souviens bien ...).
Tony

[inviteb0cf188d]

"à chaque itération, il y a un carré, une soustraction, une division, une multiplication et encore une soustraction jusqu'à l'exposant P-1"

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

[leg]

Dans ton exemple, il me semble que tu fais l'opération :
A = ( (2^n - 2^((n-1)/2) - 1)^2 - 2) / (2^n - 1)
Pour n=29, qui ne donne pas un nombre de Mersenne premier, A vaut 536805377 . Alors que tu dis trouver une fraction non entière.
Donc, cela contredit ton hypothèse, il me semble.

Utilises-tu Pari/gp ?

Tony

exact je vien de refaire le calcul, et A vaut bien 536805377 ce qui contredit mon idée , dommage; et merci de ton concour.
je n'utilise pas Pari/gp ?

je pars d'une idée avec de petits nombres que je décortique, afin de regarder les valeurs prisent en compte et de faire des test, ou trouver une propriété ou encore un point commun.. .
c'est pour cela que j'ai essayé le test de lucas sur 2(2^p)-1) et que je ne comprend pas pourquoi il fonctionne par ex 254,2*8191,etc., d'autant plus que ces nombres ne divise pas la suite de perrin..?

je ne connais pas Pari/gp ?

mais sur les Fn (nombres de Fermat) j'avais fait une recherche ,mais lorsque j'essais de joindre le fichier cela ne fonctionne pas peut être que je fais une mauvaise manip