Test de primalité pour une classe spécifique de nombres naturels utilisant des facteurs de polynômes de Lucas

Aug 15 2020

Cette question est liée à ma question précédente .

Pouvez-vous prouver ou réfuter l'affirmation suivante:

Laisser $N=2n+1$$n$ est un nombre naturel impair supérieur à un, soit $L_m(x)$ être le mth polynôme de Lucas et laisser $F_m(x)$ dénotent un facteur de degré irréductible $\varphi(m)$ de $L_m(x)$. S'il existe un entier$a$ tel que $F_{n}(a) \equiv 0 \pmod{N} $ puis $N$ est un premier.

Vous pouvez exécuter ce test ici . J'ai vérifié cette affirmation uniquement pour les petites valeurs de$N$ , C'est $N \in [7,1000]$ avec $a \in [1,100]$ , parce que mon implémentation PARI / GP du test est trop lente.

ÉDITER

Pour des valeurs de $n$qui sont des nombres premiers impairs ce test s'exécute en temps polynomial ( implémentation PARI / GP ). La liste des nombres premiers de Sophie Germain peut être trouvée ici .

Réponses

2 GHfromMO Aug 15 2020 at 19:53

Cette affirmation peut être prouvée essentiellement de la même manière que la précédente . Nous avons$$F_n(x)=\prod_{\substack{|m|<n/2\\(m,n)=1}}(x+\zeta^m-\zeta^{-m}),$$$\zeta\in\mathbb{C}$ est un primitif $2n$-ème racine de l'unité. Le champ de fractionnement de$F_n(x)$ est le $n$-ème champ cyclotomique.

Suppose que $q\nmid n$ est un nombre premier tel que la réduction de $F_n(x)$ mod $q$ a une racine dans $\mathbb{F}_q$. Les racines de$F_n(x)$ dans $\overline{\mathbb{F}_q}$ sont de la forme $\xi^m-\xi^{-m}$, où $\xi\in\overline{\mathbb{F}_q}$ est un primitif $2n$-ème racine de l'unité. Par hypothèse, l'automorphisme de Frobenius$t\mapsto t^q$ corrige l'une de ces racines, ce qui n'est possible que lorsque $q\equiv 1\pmod{2n}$. Il s'ensuit que, pour tout$a\in\mathbb{Z}$, les facteurs premiers de $F_n(a)$ coprime à $n$ sont congruents à $1$ modulo $2n$. En particulier, si$2n+1$ se divise $F_n(a)$, alors le seul facteur premier de $2n+1$ peut être lui-même, c'est-à-dire $2n+1$ est primordial.