J'ai peut être un moyen de trouver des Mersennes premiers

[acx01b]

Bonjour,

le but du Lucas Lehmer test pour prouver que est premier est de montrer que

---------------------------------------------------------------------------------------------------------
où : , , ,

dans on a la multiplication suivante :
où et
on a le groupe des inversibles de noté . En particulier, est l'inverse de dans : on note

le but c'est de montrer que c'est à dire que l'ordre de est exactement ce qui amène à une contradiction si n'est pas premier car dans ce cas (le nombre d'éléments du groupe des inversibles) est inférieur à .

pour calculer on peut considérer les suites :
et
et

ce qui est intéressant c'est que doit être égal à 0, ainsi pour un certain , . Quand on lance quelques tests, on s'aperçoit qu'en général c'est pour ce qui ne nous avance donc pas beaucoup (toujours autant de calculs à faire).

cependant, je fais la conjecture qu'il existe des nombres premiers pour lesquels avec très petit. Ainsi, si on tombe sur un tel , il ne reste plus qu'à vérifier que et c'est gagné on a un nombre de Mersenne premier !
-----

[acx01b]

petite erreur (si un modérater voulait bien remplacer à la 4ème ligne, merci ? )


dans on a la multiplication suivante :

où et

[Médiat]

Bonjour
j'ai fait la modification en apportant la mienne, si vous êtes d'accord : au lieu de

[acx01b]

ok merci beaucoup !

par contre, vous l'aurez compris, il y a de grandes chances pour qu'il y ait une bonne raison à que ce soit toujours qui est nul quand est premier, ce qui rendrait ma conjecture fausse. Mais bon dans le doute j'ai fait un programme (sans fuite mémoire) qui tourne depuis 3 heures et utilise la lib de grands nombres gmp, et j'espère la multiplication par fft, avec (le plus grand Mersenne premier connu).

[A voir en vidéo sur Futura]

[acx01b]

j'ai réussi à compiler prime95 (le programme du GIMPS avec lequel tous les grands mersenne premiers ont été découverts depuis 15 ans), et ces malades ils ont programmé la partie lucas-lehmer-test en assembleur !!!! j'hallucine.

[Médiat]

ces malades ils ont programmé la partie lucas-lehmer-test en assembleur !!!! j'hallucine.

Je ne comprends pas cette remarque, l'assembleur est le langage le plus rapide possible ( il m'est arrivé de dupliquer du code assembleur 16 fois plutôt que de faire une boucle, afin d'aller plus vite à l'exécution, genre de choses que je n'ai jamais vues avec des langages plus évolués)

[acx01b]

mais non, un programme c'est fait pour être lisible aussi !
l'algorithme de lucas lehmer il devrait être écrit en 4 lignes, dont l'une d'entre elles (la multiplication)
renvoie vers une multiplication par fft, qui à la rigueur, la fft, peut être faite en assembleur mais c'est tout. le reste doit être hyper clair et donc pas en assembleur mais plutôt en C/C++ avec de jolis noms de fonctions/variables.
et là je regarde le code de prime95 et je ne comprends mais rien du tout, il y a de l'assembleur mélangé avec du code C pour gérer les évènements de fenêtres pour pouvoir suivre le calcul dans la fenêtre de prime95, c'est horriblement bordélique. ça me donne presque envie de réécrire moi même une multiplication par fft.

et à part pour sauter le prologue/épilogue du C (*), l'assembleur en tant que vrai langage est à proscrire. le C notamment les compilateurs qui acceptent l'assembleur inline (donc visual et gcc) est toujours plus intéressant que l'assembleur. et pour déplier les boucles, souvent on peut le faire directement en C, même si je le répète on a toujours l'assembleur inline (au milieu des fonctions C).

(*) en optimisation -O2 sur gcc, les prologues/épilogues sont enlevés quand c'est possible.

[Médiat]

mais non, un programme c'est fait pour être lisible aussi !

Personnellement, je trouve un programme en assembleur très lisible, c'est juste une question d'expérience !

[acx01b]

Personnellement, je trouve un programme en assembleur très lisible, c'est juste une question d'expérience !

je suis développeur C/C++ et donc je lis de l'assembleur tout le temps dans le débugeur, et je ne suis pas du tout d'accord

mais bon on dévie du sujet : j'aimerais bien savoir si on a une chance de trouver un mersenne premier avec la méthode du premier post. ça dépend vraiment de si le a_k = 0 (qui implique que les b_k suivant sont nuls) n’apparaît forcément que à la fin, ou bien s'il peut apparaitre n'importe quand, donc potentiellement dans les 1000 premières itérations de la suite.