Conjectures sur le test de primalité des nombres de Mersenne

[inviteb0cf188d]

Bonjour,

Vous connaissez probablement le test de primalité LLT (Lucas-Lehmer Test) utilisé pour les nombres de Mersenne , où q est premier (utilisé aussi pour les nombres de Fermat et les nombres de la forme : k.2^n-1) :

Dans la thread:
Another (candidate) test of primality of Mersenne number que j'ai ouverte sur le site du GIMPS, je propose une conjecture et une "idée" liées aux propriétés de la fonction llt(x)=x^2-2 modulo un nombre de Mersenne premier.

Deux chercheurs (Shallit et Vasiga) ont récemment montré que le DiGraph généré par la fonction x^2-2 modulo un nombre de Mersenne premier est constitué d'1 arbre (résultat déjà connu) et d'un ensemble de boucles (nouveau). (Une boucle est : x0 -> x1 -> x2 -> x3 -> ... -> x0 , où l'on passe d'un élément au suivant par : x(i)=llt(x(i-1)) ).
Le test LLT est basé sur la propriété de l'arbre : à partir de 4, on peut construire par la fonction {llt2(x)=x^3-3x modulo M_q} l'ensemble des 2^(q-2) racines qui mènent à 0 modulo M_q en q-1 calculs de x=x^2-2.

Pourquoi ne pas utiliser les propriétés liées aux boucles ?
La formule (trouvée récemment) donnant le nombre de boucles d'une longueur L (L doit diviser q-1) semble montrer que le DiGraph d'un nombre de Mersenne premier possède toujours des boucles de longueur q-1 et (q-1)/2 . Pour les premiers nombres de Mersenne composites (11, 23, 29), j'ai pu observer que ce nombre de boucles est plus petit.
En particulier, pour les boucles de longueur q-1, le point de départ semble toujours être : S_0 = 3^3+1/3^2 .
Pour les boucles de longueur (q-1)/2, je n'ai pas encore trouvé de formule donnant S_0.

La conjecture :
A) est un équivalent du test LLT, en q-1 opérations.
Je l'ai vérifiée jusqu'à 2^23209-1 .

L'"idée" :
B) 1)
puis : 2)
est une tentative pour accélérer la preuve de non-primalité des nombres de Mersenne, où l'on divise les q-1 opérations en 2 étapes : (q-1)/2 opérations, puis encore (q-1)/2 opérations.
L'idée est la suivante : si un nombre de Mersenne ne passe pas l'étape 1, alors il n'est pas premier. S'il passe les 2 étapes, alors il est premier. Un tel test permettrait donc de débusquer les nombres de Mersenne composites 2 fois plus vite qu'actuellement.


Après étude des diverses démonstrations du LLT et grâce aux remarques obtenues sur d'autres forums (il faudrait connaître la factorisation de M_q-1), je pense finalement que la conjecture A) est soit fausse (il existe des valeurs de q probablement très grandes telles que Mq soit non premier mais pour lesquelles le test réussit quand même, soit non prouvable. Pour l'idée B), de la même façon, je pense qu'elle est soit fausse soit non-prouvable. Et elles doivent donc être reformulées ainsi :
A')
et
B') et

Ainsi reformulées, A') est facilement démontrable mais n'est pas très utile, et B') est à prouver.
En ce qui concerne B'), si M_q est premier, quelle valeur de x faut-il prendre pour franchir ces 2 étapes successives ? Et bien, on peut imaginer que quelqu'un trouve un moyen comparable à celui utilisé par le test LLR (Lucas-Lehmer-Riesel) utilisé pour connaître la primalité des nombres de la forme N=k.2^n-1 (où : k petit), où le point de départ du test est calculé en fonction du nombre N.
Ainsi reformulée, si B') était prouvée, elle permettrait de déterminer 2 fois plus rapidement si un nombre de Mersenne n'est pas premier.

A vos crayons !

Si quelqu'un trouve une preuve, cela multipliera par 2 l'efficacité du projet GIMPS, et le découvreur en recevra une (petite) récompense.

Tony
-----

[leg]

bonjour tony.
ma première question :
tu es sur que si A') est démontré il ne peut en aucun cas impliquer ou être utile pour démontrer B')
la deuxiéme question:
tu dis (il faudrait connaître la factorisation de M_q-1),est ce que tu entend par là:
2^P-1-1; si oui ,faut il la factorisation compléte,? (car une factoriasation partiel est facile je l'ai déja indiquée dans le fil des Mersenne, justement d'aprés ta formule pour écrire les Mersennes).
et en quoi c'est utile.
En trois:
a tu déjà experimenté ton idée avec un logiciel ou as tu éssayé une valeur de x qui fonctionnerait déjà pour les premiers nombres
En quatre:
aurais tu la gentillesse ("en ce qui me conserne") de me fournir un petit exemple avec les valeur pour A' et B' afin que je n'interprète pas mal tes formules et pour bien les comprendre ensuite je fairais part de ce que je trouve concernant x.
pour faire des essais, a tu déjà ce logiciel en deux étapes du test, et si oui, est ce que tu peux me le télécharger.
merci pour tout A+ leg

[inviteb0cf188d]

L'expression B') est buguée (le est remplacé par : ).

Il faut lire :

B') et

T.

[leg]

qu'elle est la raison de rajouter à la partie entiere de S₀ l'inverse de 9 ? en faisant le test avec S₀= 9;cela fonctionne,
de plus pour q = 7 à (q -1)/2 on obtient pour S₃, 254 qui est effectivement divisible par 127

(mais avec 9.1111111..çà ne marche pas ? peut être que j'ai mal compris quelque chose...,)

il faudrait connaître la factorisation de M_q-1:

qu'apporte cette solution si on connait sa factorisation
je suppose que cela permet de raccourcir le test en (q-1)/2 opérations
que donne le test si on utilise justement un des facteurs de 2^P-1-1 autre que les facteurs 3 ou 5 car, on peut toujours utiliser P, qui divise aussi ce nombre, ("ou alors faut il les autres facteurs de ce nombre")

[A voir en vidéo sur Futura]

[inviteb0cf188d]

tu es sur que si A') est démontré il ne peut en aucun cas impliquer ou être utile pour démontrer B')

Humm. Je vais regarder ...

tu dis (il faudrait connaître la factorisation de M_q-1),est ce que tu entend par là:
2^q-1-1; si oui ,faut il la factorisation complète,? (car une factorisation partielle est facile je l'ai déja indiquée dans le fil des Mersenne, justement d'après ta formule pour écrire les Mersennes).

Oui. M_q-1 = 2^q-2=2(2^q-1-1) . Exemple : M_7-1=126=2*(63)=2*(2^(7-1)-1). Une factorisation partielle suffit. Tu as une démonstration pour cette factorisation ? Si oui, beaucoup de gens sont intéressés !

et en quoi c'est utile ?

La théorie utilisée pour prouver ce genre de propriété utilise phi(N), qui vaut N-((D/N)). ( ((a/b)) : symbole de Legendre) Avec le LLT pour nombre de Mersenne, phi(N)=N+1=2^q ; donc la factorization est évidente. Avec les propriétés A') et B'), il faut apparemment utiliser des Séquences de Lucas ayant la propriété ((D/N))=1 . Donc Phi(N)=N-1=M_q-1 .

a tu déjà experimenté ton idée avec un logiciel ou as-tu essayé une valeur de x qui fonctionnerait déjà pour les premiers nombres

Comme indiqué dans le thread du GIMPS (à lire ...), j'ai trouvé que la valeur x=28 marche pour q=13. Pour q=5 et 7, il y a tellement peu de boucle que la loi des petits nombres intervient : la probabilité de trouver qque chose qui marche "par hasard" est trop grande. Il faudrait aussi chercher pour a=17 et 19 ...

aurais tu la gentillesse ("en ce qui me concerne") de me fournir un petit exemple avec les valeur pour A' et B' afin que je n'interprète pas mal tes formules et pour bien les comprendre ensuite je fairais part de ce que je trouve concernant x.

Pour A'), il suffit d'utiliser PARI/gp et de taper : (3^2+1/3^2)%(2^q-1) et on obtient S0 . D'ailleurs, comme 1/3 mod M_q = (2*M_q+1)/3 (car M_q=1+6qk), il est facile de trouver 1/3^2 mod M_q ...

pour faire des essais, a tu déjà ce logiciel en deux étapes du test, et si oui, est ce que tu peux me le télécharger.

Et non. Pas de logiciel encore. Comme je le dis à la fin du premier post, il y a pas mal de travail à faire encore pour B'). En particulier, définir comment trouver une formule S0=f(x) qui marche pour tout q, comme le fait le test LLR (Riesel).
Des contributeurs (avec plus de compétences que moi dans ces domaines ...) sont bienvenus !
Tony

[inviteb0cf188d]

quelle est la raison de rajouter à la partie entiere de S₀ l'inverse de 9 ?

Il faut lire le papier de Shallit&Vasiga On the iteration of certain quadratic maps over GF(p) et lire le thread sur le forum du GIMPS : ils disent que les éléments des boucles sont générés par : (3^2)^n+(1/3^2)^n . Ce qui est en partie vrai ...

en faisant le test avec S₀= 9;cela fonctionne,

Lequel des 2 ? Avec S0=9 et q=13, cela ne marche ni pour A') ni pour B') . Manisfestement, 9 fait partie de l'arbre, pas des boucles.
9 -> 79 -> 6239 -> ... -> 128 -> 0 -> -2 -> 2 -> 2.
PARI/gp : x=9;q=13;M=2^q-1;for(i=1,q-1,x=(x^2-2)%M;print(x))

de plus pour q = 7 à (q -1)/2 on obtient pour S₃, 254 qui est effectivement divisible par 127 .

Parce que 9 appartient aussi à l'arbre généré par q=7 . Par contre, 9 n'appartient pas aux arbres généré par q=17, 19 ou 31.

(mais avec 9.1111111..çà ne marche pas ? peut être que j'ai mal compris quelque chose...,)

Oui. 1/9 mod Mq, cela reste un nombre entier. (Et 1/9 mod Mq existe toujours, que M_q soit premier ou non).

il faudrait connaître la factorisation de M_q-1:
qu'apporte cette solution si on connait sa factorisation ? je suppose que cela permet de raccourcir le test en (q-1)/2 opérations

Selon les méthodes utilisées pour prouver le test LLT, il faut connaître M_q -((D/N)) . Ici, c'est M_q-1. Il faudrait que tu lises quelques papiers sur le sujet ...

que donne le test si on utilise justement un des facteurs de 2^P-1-1 autre que les facteurs 3 ou 5 car, on peut toujours utiliser P, qui divise aussi ce nombre, ("ou alors faut il les autres facteurs de ce nombre")

Oui. Certains théorèmes classiques permettent de donner une preuve de primalité d'un nombre N à condition de connaître un nombre suffisant de facteurs de N-1. Mais c'est un peu compliqué ... Il te faut chercher et apprendre un peu plus ... Commence par regarder le Wiki du GIMPS.
T.

[leg]

Humm. Je vais regarder ...
Oui. M_q-1 = 2^q-2=2(2^q-1-1) . Exemple : M_7-1=126=2*(63)=2*(2^(7-1)-1). Une factorisation partielle suffit. Tu as une démonstration pour cette factorisation ? Si oui, beaucoup de gens sont intéressés !
La théorie utilisée pour prouver ce genre de propriété utilise phi(N), qui vaut N-((D/N)). ( ((a/b)) : symbole de Legendre) Avec le LLT pour nombre de Mersenne, phi(N)=N+1=2^q ; donc la factorization est évidente. Avec les propriétés A') et B'), Tony

tout d'abord merci pour tes renseignements complémentaires qui me premettent de mieux comprendre .
(comme je travail uniquement dans les entiers certaine formule je ne les comprend pas)
pour ta question, oui j'ai une formule qui est simple et de plus évidente a prouver pour la factorisation de M_q-1
je pensais l'avoir déjà mis sur l'autre fil des nombres de Mersenne, je vais la mettre au propre et la mettre sur ce fil ou tu pourras ensuite me posér des questions si nécéssaire; quoique tu vas vite comprendre car, c'est en rapport avec ta paire 8X et 3pY ("p=q")
.............................. .............................. ................
[ hors sujet:
Par contre je découvre que l'on utilise phi; ce qui est curieux, car moi même je l'utilise pour calculer le nombre de nombres premiers jusqu'à 2^N, plus N augmente, plus l'estimetion se rapproche du réel
voila ce que je fais
je calcule le nombre de premiers jusqu'a la racine carrée de 2ⁿ que je divise par phi ,( arrondi à 0.6181)
j'obtiens Q que je met ensuite au carré .
ex : pour n = 2¹⁸
nombre de premiers jusqu'à sqart de n qui vaut 512 il y a 94 P sans compter 2.3 et 5
puis (94/0.6181)² = 152²
le nombre de P pour 2¹⁸ dans l'algo P(30)
donne pour les 4 premiéres séries(2842 + 2875+ 2885 + 2892)soit le double pour les 8 séries donc 151,6² environ car je n'ai pas compter les 4 autres séries..voila pour la petite histoire.]
.............................. .............................. ................
Pour trouver a et b, on factorise : de façon simple. 2^(p – 1) -1

Factorisation de : (2^p-1)-1

On connais déjà un certain facteur de (2^p-1)-1 ; en générale 3 et l'exposant et (si il se termine par 5, on rajoute 5), dans l'exemple cité :

2^23 -1 = 8388607 et (Mq – 1)/2 = 4194303 ce qui donne déjà : 2 facteurs P
3 et 23 et 60787 est composé !

Or, (2^p) - 2 = (U² - V²) / 2 et, pour V = 2 ; U’ et V’ s’obtiennent avec les facteurs de :
(Mq – 1)/2, pour cette exemple 4194303.

Question peut on factoriser facilement ce produit, oui en principe.
Connaissant 3 et 23, il nous faut un troisième facteur.

(Mq – 1) * 2 = ((2^p) -2)* 2 = U² -V², donc comme V = 2, U² = 2² + (2^p * 2) par conséquent, U = √U².
Exemple : 8388606 * 2 = 16777212, et + 4 = U², soit √16777216 = U = 4096 et bien sûr, 4096 / 2 = 2048 ce qui donne : v’ = 2048 – 1 ; et u’ = 2048 + 1, qui sont divisibles par 23 et 3, 2047 / 23 = 89 ; 2049 / 3 = 683 .

et 89 divise M_q-1 : 4194303/89 = 47127
47127/683 = 69 = 3*23
.............................. .............................. ...............
[ On sait que le reste 60787 est composé = (a+b) (a-b) = a² - b².
(" note: c'est marrant, on retrouve la formule des triplets pythagoricien, que l'on retrouve souvent partout et qui a du donner des idées à Fermat pour son petit théorème d'apres le nombres de Mersenne")

(" Ceci va nous donner un premiers indice : 8388607/60787= 138,xxx que l’on pourra utiliser pour retrouver A et B des que 60787 a été factorisé = 89*683 ;
Et (683 + 89) / 2= 386 ; et 386 – 89 = 297.")]
.............................. .............................. ................

pour M 29,= 536870911, (536870910 *2) + 4 = U² ; U = 32768 ; on connait déjà pour M_q -1 = 3*5*29 * x*y
u’ = 16385 et
v’ = 16383 . et 16385/5/29 = 113 ; 16383 /3 = 5461 qui restera a factoriser.

113 est un des autres facteurs qui divise M_q -1

[voila pourquoi je disais qu'il était important de factoriser M_q-1 sur l'autre fil , et qu'avec cette propriété on pouvait arriver à connaitre si Mq était premier ou pas.
et tu vois que la paire u' et v' est en "relation" avec ta paire X ,Y soit 8X et 3pY mais beaucoup plus réduite et calculer en partant justement de M_q -1]
en espérant que cela te serve A+ leg

[leg]

.............................. .............................

Factorisation de : (2^p-1)-1

On connais déjà un certain facteur de (2^p-1)-1 ; en générale 3 et l'exposant et (si il se termine par 5, on rajoute 5), dans l'exemple cité :

2^23 -1 = 8388607 et (Mq – 1)/2 = 4194303 ce qui donne déjà : 2 facteurs P
3 et 23 et 60787 est composé !

Or, (2^p) - 2 = (U² - V²) / 2 et, pour V = 2 ; U’ et V’ s’obtiennent avec les facteurs de :
(Mq – 1)/2, pour cette exemple 4194303.

(Mq – 1) * 2 = ((2^p) -2)* 2 = U² -V², donc comme V = 2, U² = 2² + (2^p -2 * 2) par conséquent, U = √U².
Exemple : 8388606 * 2 = 16777212, et + 4 = U², soit √16777216 = U = 4096 et bien sûr, 4096 / 2 = 2048 ce qui donne : v’ = 2048 – 1 ; et u’ = 2048 + 1, qui sont divisibles par 23 et 3, 2047 / 23 = 89 ; 2049 / 3 = 683 .

et 89 divise M_q-1 : 4194303/89 = 47127
47127/683 = 69 = 3*23


pour M 29,= 536870911, (536870910 *2) + 4 = U² ; U = 32768 ; on connait déjà pour M_q -1 = 3*5*29 * x*y
u’ = 16385 et
v’ = 16383 . et 16385/5/29 = 113 ; 16383 /3 = 5461 qui restera a factoriser.

113 est un des autres facteurs qui divise M_q -1

bonjour tony
il faut que je te dise aussi que la raison de pouvoir factorisé facilement M_q -1 = 2^p-1-1;
provient de la paire u' et v' qui mis au carré est en rapport avec Mq plus précisément
comme on le voit je trouve tout simplement les deux carrés de (2 (Mq -1)) en partant de 4.
puis il me faut la paire u' et v' ;qui n'est autre que (U/2) +1 et -1.
parce que cette paire contient toujours les facteurs de M_q-1 et comme on peut le constater ces facteurs se partage entre u' et v' or comme on a déjà une partie obligatoire des facteurs en l'ocurence 3 et l'exposant le restant des facteurs et simple a trouver car tres souvent un troisième facteur et donné comme on le voit pour M.29 ; M.23
pour M.7 cela aurait donné :
a)
(126 *2) + 4 = 256 = U²; donc U = 16

b)
u' = (U/2) +1 ; v' = (U/2) -1 (" et u'² - v'² = 2*U ")

c)
M_q -1 = 63 on connait 7 et 3. et U' = 9 = 3²; v' =7
63 /u' = v'

pour M.11 , 13 , 17 , 19 c'est toujours pareil

en définitive je part de 2^p+1 pour factoriser 2^p-1-1
car la paire u' et v' contient obligatoirement les facteurs premiers de 2^p-1-1 , facteurs qui se partage justement entre u' et v'

il faudrait voir pourquoi x = 28 marche ; puis si x à un lien avec u' ou v' .
de mon coté je vais controler ce que cela donne avec q = 5. 7 et 13 pour x = 28 puis je verrai avec 17.19.31

[leg]

bonjour tony
dans tes explications tu dis que, ("en prenant 29 comme exemple ") 2^29 -1 = 1+6qk

donc ce qu'il vous faudrait, serait la factorisation de K
soit : 2²⁹ - 2 = 6qk = 536870910
donc qk = 5*29*617093 = a² - b²

or : a et b , sont trouvable imediatement :
a = (U + ou -1)/3
b = (v'/3)+1

qk est divisible par b = x qui est divisble par q
qk est aussi divisble par u'

pour M 29,= 536870911, (536870910 *2) + 4 = U² ; U = 32768 ;( U/2 ) +1 = u’ = 16385 et u' - 2 = v’ = 16383 .

et en utilisant déjà les facteurs connus 3,5 et 29:

16385/5/29 = 113 ; 16383 /3 = 5461 qui restera a factoriser.

Ou encore v’/3 = b -1 = 5461 et 617093/5461=113

(2^(p -1)-1 / 2, donne 3.5.29 et 617093 = 43*14351 ; et 14351 = 113*127

(617093*5*29) = a² - b² = (a+b) (a-b)

(U + - 1) /3 = a =10923 et a² - (617093*5*29) = b² où b = 5462 = ( v’ /3) +1

a = 10923 , b = 5462;

[invite6411921e]

Euh Salut d'abord j'ai une question

mod(2^17-1,17)=1

mod(2^63-1,63) n'est pas égal a 1

mod (2^521-1,521)=1

mod(2^53-1,53)=1

mod(2^a-1,a)= 1 Donc les nombre de mersenne on tous sa en commun oki ?

Mais c'est utiliser sa dans les test ?????

A premier vu on calcul pas grand chose la non ?

Sa a un nom deja ?
Baleze ma ti 89 xD

[inviteb0cf188d]

mod(2^a-1,a)= 1 Donc les nombres de Mersenne on tous ça en commun oki ?

Mais c'est utilisé dans les tests ?????

A première vue on calcule pas grand chose là non ?

Ca a un nom déjà ?
Baleze ma ti 89 xD

Si q est premier, alors M_q=2^q-1 a 1 pour reste 1 modulo q. Ce qui veut dire M_q=1+Kq . (En fait : M_q=1+6kq).
Voir : Prime Pages. Cela vient du théorème 3. Ce théorème indique la forme des facteurs possibles d'un nombre de Mersenne. Et c'est utilisé dans les programmes de recherche de nombres de Mersenne premier : avec un facteur possible petit, c'est rapide. Ensuite, on utilise le test LLT.
Plutôt que la TI 89, mieux vaut utiliser :PARI/gp, pour Windows ou Linux. Plus puissant !

Tony