Test di primalità per classi specifiche di numeri naturali utilizzando fattori di polinomi di Lucas
Questa domanda è correlata alla mia domanda precedente .
Puoi provare o confutare la seguente affermazione:
Permettere $N=2n+1$ dove $n$ è un numero naturale dispari maggiore di uno, let $L_m(x)$ sii il mesimo polinomio di Lucas e lascia $F_m(x)$ denotano un irriducibile fattore di grado $\varphi(m)$ di $L_m(x)$. Se esiste un numero intero$a$ tale che $F_{n}(a) \equiv 0 \pmod{N} $ poi $N$ è un primo.
Puoi eseguire questo test qui . Ho verificato questa affermazione solo per piccoli valori di$N$ , questo è $N \in [7,1000]$ con $a \in [1,100]$ , perché la mia implementazione PARI / GP del test è troppo lenta.
MODIFICARE
Per valori di $n$che sono numeri primi dispari questo test viene eseguito in tempo polinomiale ( implementazione PARI / GP ). L'elenco dei numeri primi di Sophie Germain può essere trovato qui .
Risposte
Questa affermazione può essere dimostrata essenzialmente nello stesso modo della precedente . abbiamo$$F_n(x)=\prod_{\substack{|m|<n/2\\(m,n)=1}}(x+\zeta^m-\zeta^{-m}),$$ dove $\zeta\in\mathbb{C}$ è un primitivo $2n$-esima radice dell'unità. Il campo di scissione di$F_n(x)$ è il $n$-esimo campo ciclotomico.
Assumilo $q\nmid n$ è un numero primo tale che la riduzione di $F_n(x)$ mod $q$ ha una radice in $\mathbb{F}_q$. Le radici di$F_n(x)$ nel $\overline{\mathbb{F}_q}$ sono della forma $\xi^m-\xi^{-m}$, dove $\xi\in\overline{\mathbb{F}_q}$ è un primitivo $2n$-esima radice dell'unità. Per ipotesi, l'automorfismo di Frobenius$t\mapsto t^q$ risolve una di queste radici, il che è possibile solo quando $q\equiv 1\pmod{2n}$. Ne consegue che, per qualsiasi$a\in\mathbb{Z}$, i fattori primi di $F_n(a)$ coprime a $n$ sono congruenti a $1$ modulo $2n$. In particolare, se$2n+1$ divide $F_n(a)$, quindi l'unico fattore primo di $2n+1$ può essere se stesso, cioè $2n+1$ è il primo.