Polinomi irriducibile su un campo finito

[fpeve]

Salve a tutti. Dovrei trovare un polinomio irriducibile di grado 4 su un campo finito di caratteristica p. Esiste un metodo operativo? L'unico modo che mi è venuto in mente è il test: $gcd(f(x),x^(p^i)-x)=1$ con $i=1,2$, ma non è molto comodo

[Stickelberger]

Per certi numeri primi $p$ e’ facile scrivere un polinomio irriducibile
di grado $4$ in $F_p[X]$. Per esempio, se $p$ e’ congruo a $2$ o $3$ mod $5$,
il quinto polinomio ciclotomico e’ irriducibile modulo $p$.
Per $p=3$ mod $8$, il polinomio $X^4-2^{\frac{p+1}{4}}X^2-1$ e’ irriducibile … etc.

Ma in generale e’ difficile. Un problema un po' piu’ facile e’ di trovare un
polinomio irriducibile di grado $2$. E se sappiamo fare questo,
basta farlo due volte per ottenere un polinomio irriducibile di grado $4$.

Se la caratteristica del campo finito $F_q$ e’ diversa da $2$, esibire un polinomio
irriducibile di grado $2$ e’ equivalente ad esibire un non quadrato in $F_q$.
Questo e’ facile se $q$ non e' congruo a $1$ mod $8$. Infatti, se $q\equiv 3$ mod $4$,
allora $-1$ non e’ un quadrato e se $q\equiv 5$ mod $8$, allora $2$ non e’ un un quadrato.

Per $q\equiv 1$ mod $8$, non c’e’ una formula. Un modo efficiente per trovare un
non quadrato e’ di semplicemente provare elementi a caso.
Ogni volta la probabilita’ di successo e’ del $50%$.