Preuve de primalité des nombres de Wagstaff

[T.Rex]

Soit $q$ premier. Un nombre de Wagstaff est noté : $W_q = \frac{2^q+1}{3}$.
Jusqu'à présent, il existe des preuves de primalité extrêmement rapides uniquement pour les nombres de Mersenne : $2^q-1$ ou les nombres de Fermat : $2^{2^n}+1$. Traditonnellement, on utilise le test LLT (Lucas-Lehmer Test) pour les Mersenne, et le test de Pépin pour les Fermat. Mais il est également possible d'utiliser un test LLT pour les nombres de Fermat (ce n'est pas dans les livres de Théorie des Nombres, mais uniquement dans 3 papiers sur le Web, dont le mien).
Un LLT "classique" utilise un grand arbre du DiGraph sous $x^2-2$ modulo N.

Pour les nombres de Wagstaff, il n'existe pas (encore) de test de primalité équivalent. Il n'existe qu'un test rapide de PRP (PRobable Prime) basé sur un dérivé du LLT : un test basé sur un cycle du DiGraph sous $x^2-2$ modulo $W_q$. Cette méthode a été implémentée sous le nom Vbra-Reix, et j'ai trouvé avec cette méthode implémentée dans l'outil du GIMPS un très grand PRP de Wagstaff (voir Wikipedia). Et cette méthode est la partie "necessity" : si le nombre est premier, ALORS il a cette propriété. Il reste maintenant à prouver la "sufficiency" : si un nombre a cette propriété, ALORS il est premier.

Utiliser un Cycle du Digraph plutôt que l'arbre a été essayé pour les nombres de Mersenne et Fermat en plus de Wagstaff . Voir :
http://tony.reix.free.fr/Mersenne/Conje ... rsenne.pdf
https://trex58.files.wordpress.com/2009 ... fermat.pdf
Voici le résumé des 3 conjectures :
http://tony.reix.free.fr/Mersenne/Summa ... ctures.pdf

Terence Tao a publié un post sur la preuve du LLT pour les nombres de Mersenne, mais il n'est pas allé plus loin :
https://terrytao.wordpress.com/2008/10/ ... ne-primes/

Et, très récemment, un chercheur chinois a publié un papier très intéressant qui donne de nouvelles propriétés liées au LLT, dont une pour les nombres de Wagstaff :
https://arxiv.org/pdf/2010.02677.pdf

Maintenant, question :
Quelqu'un est-il intéressé à travailler sur ce sujet et essayer de prouver la conjecture sur une preuve de primalité pour les nombres de Wagstaff ?
Diverses méthodes ont été utilisées dans le passé, comme la "Lucas-Lehmer" theory, reprise par Paolo Ribenboim et HC Williams. Il existe des preuves du LLT pour les nombres de Mersenne au moyen de courbes elliptiques. Mais d'autres méthodes sont certainement possibles.

[JRManda]

Bonjour,

Ceci n'est pas une proposition de test de primalité pour les nombres de Wagstaff, mais une sorte de retour sur quelques propriétés de ces types de nombres. Peut-être que cela peut contribuer à diversifier la réflexion sur le sujet.

1. Tout facteur premier $w_{q}$ du nombre de Wagstaff $W_{q}=\frac{2^{q}+1}{3}$ est d'ordre simple ;
2. Pour $q\geq 3$, $W_{q}\equiv +3\bmod 8$ ;
3. $W_{q}$ possède au moins un facteur premier congru à +3 modulo 8 ;
4. $W_{q}$ possède un nombre impair de facteurs premiers congrus à $\pm 3$ modulo 8 ;
5. Tout facteur premier $w_{q}$ de $W_{q}$ est de la forme $w_{q}=2\lambda q + 1$, $\lambda \in \mathbb{N}^{\ast}$ ;
6. Si $W_{q}$ est composé, alors c'est un supernombre de Poulet.

[Yoan]

Bonjour,

Vos observations ajoutent certainement de la profondeur à notre compréhension de ces nombres particuliers. Je trouve particulièrement intrigante la propriété selon laquelle tout facteur premier d'un nombre de Wagstaff est congru à +3 modulo 8, ainsi que la relation avec les nombres de Poulet lorsque le nombre de Wagstaff est composé. Ces caractéristiques pourraient ouvrir des pistes de recherche intéressantes, notamment dans le domaine de la cryptographie. Avez-vous exploré davantage ces propriétés ou d'autres applications potentielles des nombres de Wagstaff ?

[T.Rex]

Les nombres de Wagstaff et les polynômes irréductibles.


Lorsqu'on étudie le DiGraph sous $x^2-2$ modulo un nombre de Wagstaff premier pour les premiers nombres de Wagstaff ($q <= 31$), on voit que le nombre de cycles de longueur $q-1$ et $q-2$ correspond (pour les $W_q$ premiers) à la série A165921 d'OEIS https://oeis.org/A165921 qui a été créée par JF Michon lors de son étude des polynômes irréductibles dans son papier "On different families of invariant irreducible polynomials over F2", colonne h6 de la table en page 173 : https://doi.org/10.1016/j.ffa.2010.01.004 .

Code : Tout sélectionner

     L          N           OEIS
  Longueur    Nombre       A165921
des cycles  de cycles       a(L)
           de longueur L
----------------------------------
q=7 :
     1          2
     3          1
     5          1             1
     6          1             1
q=11 :
     1          2
     3          1
     5          4
     9          9             9
    10         15            15
q=13 :
     1          2
     2          1
     3          1
     4          1
     6          6
    11         31            31
    12         53            53
q=17 :
     1          2
     2          1
     4          2
     5          3
     8         20
    15        363           363
    16        672           672
q=19 :
     1          2
     3          2
     6          4
     9         37
    17       1285          1285
    18       2407          2407
q=23 :
     1          2
     7          9
    11        124
    21      16641         16641
    22      31713         31713
q=29 :
     1          4
     2          6
     3          2
     4          4
     6          1
    12          9
    14         22
    28         24       1597440
    42          1
    84          2
   363         18
   726          9
  1452          9
  5082          9
 10164        198
 21665          2
 43330          8
 86660         23
129990         18
259980         46
q=31 :
     1          2
     3          1
     5          6
     6          1
    10         48
    15       1454
    29    3085465      3085465
    30    5964488      5964488

Lorsqu'on étudie le DiGraph sous $\frac{\displaystyle x^4+2x^2+1}{\displaystyle 4(x^3-x)}$ modulo un nombre de Wagstaff, on voit que le nombre de cycles de longueur $q-2$ pour les $W_q$ premiers est le double de la valeur dans A165921 d'OEIS.

$\frac{\displaystyle x^4+2x^2+1}{\displaystyle 4(x^3-x)}$ vient de la Preuve de Primalité par Courbe Elliptique des nombres de Fermat comme démontré en 2009-2010 par les auteurs suivants :
R. Denomme et G. Savin : "Elliptic curve primality tests for Fermat and related primes" : https://doi.org/10.1016/j.jnt.2007.12.009
Yu Tsumura, Yu : "Elliptic curve primality tests for Fermat and related primes" : {https://doi.org/10.48550/arXiv.0912.2116

Code : Tout sélectionner

     L          N           OEIS
  Longueur    Nombre       A165921
des cycles  de cycles       a(L)
           de longueur L    
-----------------------------------
q=7  :
     5          2             1
q=11 :
     1          2
     3          2     
     9         18             9
q=13 :
    11         62            31
q=17 :
     1          1
     5          6     
    15        726           363
q=19 :
    17       2570          1285
q=23 :
     1          1
     7         18     
    21      33282         16641
q=29:
     1          6
     2         68
     4         72
     6         30
    12        300
   324         28
   648       8176
  1184         56
  2368        112
q=31 :
    29    6170930       3085465

Pourquoi y-a-t-il un lien entre les nombres de Wagstaff et les polynômes irréductibles ??

[T.Rex]

Pour $q\geq 3$, $W_{q}\equiv +3\bmod 8$ ;

Plus précisément, il semble qu'on ait : $q\geq 5$, $W_{q} = 3+ 8 Q$ avec $Q$ impair.

[T.Rex]

Pour $q\geq 3$, $W_{q}\equiv +3\bmod 8$ ;

Avec $q'=\frac{\displaystyle q-1}{\displaystyle2}$, on a même : $W_q = 3 + 8 \times \Bigg( W_{q'}^2 - \bigg(\frac{\displaystyle W_{q'} +1}{\displaystyle 2}\bigg)^2 \Bigg) = 3+ 2 \times (W_{q'} - 1) \times (3W_{q'} + 1) $ .

Ou, avec $q'=\frac{\displaystyle q-3}{\displaystyle2}$, $M_q=2^a-1$, et $N_a=2^a+1$ : $W_q = 3 + 8 \times \frac{\displaystyle M_{q'} \times N_{q'}}{\displaystyle 3} $ .