Polynôme irréductible sur un corps fini

Approche simple : prendre un polynôme de degré $k$ au hasard et regarder s’il est irréductible, répéter tant que ça marche pas

C’est pas très dur de montrer que la proba de tomber sur un polynôme irréductible est $\ge 1/2k$, et y a des tests d’irréductibilité dans $\mathbf{F}_p$ assez simples à coder. Par exemple, $P\in \mathbf{F}_p[X]$ de degré $k$ est irréductible ssi. $P\mid X^{p^k}-x$ et pour tout $q$ premier divisant $k$, $\text{pgcd}(P,X^{p^{k/q}})=1$ (théorème dû à Rabin, cf. la page Wikipedia sur la factorisation des polynômes sur des corps finis). Si on utilise que des algos naïfs, en $O(k^4)$ t’as une probabilité constante de trouver un polynôme irréductible, mais avec une FFT tu peux déjà avoir du $O(k^3\log k)$ assez simplement (sans compter les facteurs polylogs en $q$).

Après évidemment c’est un problème assez étudié dans la littérature, par exemple cet article semble être ce qui se fait de plus moderne et donne du $k^{1+o_k(1)}(\log q)^{5+o_q(1)}$ randomisé. Visiblement la question déterministe est également assez intéressante, cf. ce vieux papier d’Adleman et Lenstra qui donne du $(k \log q)^{O(1)}$ sous l’hypothèse de Riemann généralisée.

Note qu’on obtient pas forcément un polynôme primitif avec cette méthode, ce qui j’imagine peut être embêtant pour implémenter les opérations sur le corps (t’as pas forcément accès à une représentation "multiplicative").

Oui, parce que la multiplication de classes modulo $P$ dans $\mathbf F_p[X]$ est un morphisme multiplicatif.

Oui, pardon, c’est juste une histoire de complexité. Avec ta représentation, un élément de $\mathbf{F}_{p^k}$ ça prend $k\log p$ bits de mémoire, additionner c’est $k$ opérations de $\mathbf{F}_p$ et multiplier ça dépend, mais ça va être en gros au moins du $k\log k$ ($k^2$ si tu fais ça naïvement).

Je crois que ce que les gens font généralement, c’est au lieu de dire qu’un élément de $\mathbf{F}_{p^k}$ c’est un polynôme de degré $< k$, tu dis que c’est un truc de la forme $X^i$, en supposant que le polynôme $X$ est un générateur du groupe multiplicatif du corps $\mathbf{F}_p[X]/P$ où $P$ c’est ton polynôme irréductible (condition qui est réalisée quand $P$ est primitif, justement). Tu représentes l’élément $0$ par $0$, $1$ par $p^k-1$ et $X^i$ par $i$ pour $1\le i< p^k-1$. Ça prend toujours $k\log p$ bits en mémoire, mais multiplier/diviser devient super rapide (c’est en gros une seule addition dans $\mathbb{Z}/(p^k-1)\mathbb{Z}$). Additionner/soustraire c’est un peu relou, mais en écrivant $X^i+X^j=X^i(1+X^{j-i})$ tu vois que si t’as assez de place pour stocker ton corps en mémoire, il suffit juste de précalculer la représentation multiplicative de tous les $X^i+1$. Si t’as ça, additionner/soustraire c’est aussi 2 ou 3 opérations de $\mathbb{Z}/(p^k-1)\mathbb{Z}$.

Pour le coup c’est facile de compter le nombre de polynômes primitifs unitaires de degré $k$ : il y en a $\phi(p^k-1)$, donc la proba de tomber dessus c’est $\phi(p^k-1)/kp^k$. Bon et avec les mains, si on utilise la borne inf sur $\phi$ de Wikipedia, apcr on a :

$\frac{\phi(p^k-1)}{kp^k}\ge \frac{1}{k(C(\log k+\log\log p)+1)}$

Donc en gros tout à l’heure notre proba était de l’ordre de $1/k$, maintenant de l’ordre de $1/k \log k$, donc il faudra juste un facteur $\log k$ en plus pour ré-obtenir une probabilité constante d’avoir un polynôme primitif (ce qui est plus fort qu’irréductible).

Mais effectivement, ce que tu dis marche tout à fait (et il y a même des cas où c’est plus intéressant de faire comme tu dis).

mais je vais jeter un coup d’œil au papier de J.M. COUVEIGNES et R. LERCIER, qui s’il tient ses promesses a l’air très intéressant

Bonne chance, il a pas l’air facile

Oui c’est ça, je pense que t’as tout compris. Après on rentre très vite dans des questions d’implémentation, donc on peut débattre que telle ou telle méthode est meilleure pendant des heures (la taille du corps par rapport au nombre d’opérations que tu comptes faire, si tu veux construire une surcouche de primitives arithmétiques par-dessus, etc.). BTW, apparemment ce qu’on a appelé représentation multiplicative a un nom : la représentation en logarithme de Zech.

Un autre truc qu’on a pas abordé, c’est qu’on peut aussi essayer de chercher en priorité des polynômes irréductibles "sparse" (avec peu de coefficients non nuls) pour que les opérations avec la représentation additive soient rapides (notamment le modulo $P$ dans la multiplication). Par exemple, ici ils construisent des opérations de corps super rapides dans le cas particulier des optimal extension fields, qui sont les corps de cardinal $p^k$ où $p$ est un nombre premier "pseudo-Mersenne" et il existe un polynôme irréductible de la forme $X^k-x\in \mathbf{F}_p[X]$ (là c’est un cas très favorable : on a un truc super sparse, avec seulement deux coefficients non nuls).