Primalitätstest für eine bestimmte Klasse natürlicher Zahlen unter Verwendung von Faktoren von Lucas-Polynomen

Question

Diese Frage bezieht sich auf meine vorherige Frage .

Können Sie die folgende Behauptung beweisen oder widerlegen:

Lassen $N=2n+1$ wo $n$ ist eine ungerade natürliche Zahl größer als eins, lassen Sie $L_m(x)$ sei das m-te Lucas-Polynom und lass $F_m(x)$ bezeichnen einen irreduziblen Gradfaktor $\varphi(m)$ von $L_m(x)$. Wenn eine Ganzzahl vorhanden ist$a$ so dass $F_{n}(a) \equiv 0 \pmod{N} $ dann $N$ ist eine Primzahl.

Sie können diesen Test hier ausführen . Ich habe diese Behauptung nur für kleine Werte von verifiziert$N$ , das ist $N \in [7,1000]$ mit $a \in [1,100]$ , weil meine PARI / GP-Implementierung des Tests zu langsam ist.

BEARBEITEN

Für Werte von $n$Das sind ungerade Primzahlen, die dieser Test in Polynomzeit ausführt ( PARI / GP-Implementierung ). Eine Liste der Primzahlen von Sophie Germain finden Sie hier .

Answer 1

Diese Behauptung kann im Wesentlichen auf die gleiche Weise wie die vorherige bewiesen werden . Wir haben$$F_n(x)=\prod_{\substack{|m|<n/2\\(m,n)=1}}(x+\zeta^m-\zeta^{-m}),$$ wo $\zeta\in\mathbb{C}$ ist ein Primitiv $2n$-th Wurzel der Einheit. Das Aufteilungsfeld von$F_n(x)$ ist der $n$-th Zyklotomfeld.

Annehmen, dass $q\nmid n$ ist eine Primzahl, so dass die Reduktion von $F_n(x)$ mod $q$ hat eine Wurzel in $\mathbb{F}_q$. Die Wurzeln von$F_n(x)$ im $\overline{\mathbb{F}_q}$ sind von der Form $\xi^m-\xi^{-m}$, wo $\xi\in\overline{\mathbb{F}_q}$ ist ein Primitiv $2n$-th Wurzel der Einheit. Unter der Annahme des Frobenius-Automorphismus$t\mapsto t^q$ behebt eine dieser Wurzeln, was nur möglich ist, wenn $q\equiv 1\pmod{2n}$. Daraus folgt für jeden$a\in\mathbb{Z}$, die Hauptfaktoren von $F_n(a)$ Koprime zu $n$ sind kongruent zu $1$ Modulo $2n$. Insbesondere wenn$2n+1$ teilt $F_n(a)$, dann der einzige Primfaktor von $2n+1$ kann selbst sein, dh $2n+1$ ist Prime.