# Polynôme de Conway (corps finis)

En mathématiques, le polynôme de Conway C$_{p,n}$ sur le corps fini F$_{p,n}$ est un polynôme irréductible particulier de degré n sur F$_p$ qui peut être utilisé pour définir une représentation standard de F$_{p,n}$ en tant que corps de décomposition de C$_{p,n}$. Les polynômes de Conway ont été baptisés d'après John Horton Conway par Richard A. Parker, qui a été le premier à les définir et à calculer des exemples. Les polynômes de Conway satisfont une certaine condition de compatibilité, proposée par Conway, entre la représentation d'un corps et celles de ses sous-corps. Ils sont utiles pour le calcul formel pour lequel ils fournissent une portabilité parmi différentes bases de données mathématiques et des systèmes de calcul formel. Étant donné le coût important du calcul des polynômes de Conway, ils doivent être enregistrés pour être utilisés en pratique. Des bases de données de polynômes de Conway sont disponibles dans les systèmes de calcul formel GAP, Macaulay2 (en), Magma, SageMath, et le site internet de Frank Lübeck.

## Contexte

Les éléments de F$_{pn}$ peuvent être représentés comme des sommes de la forme a$_{n−1}$β$^{n−1}$ +⋅⋅⋅+ a$_1$β + a$_0$ où β est une racine d'un polynôme irréductible de degré n défini sur F$_p$ et les a$_j$ sont des éléments de F$_p$. L'addition d'éléments du corps dans cette représentation est simplement une addition vectorielle. Bien qu'il n'y a qu'un corps fini unique d'ordre p$^n$ à isomorphisme près, la représentation des éléments du corps dépend du choix du polynôme irréductible. Le polynôme de Conway est une manière de standardiser ce choix.
Les éléments non nuls d'un corps fini forment un groupe cyclique par la multiplication. Un élément primitif, α, de F$_{pn}$ est un élément qui engendre ce groupe. Représenter les éléments non nuls du corps comme des puissances de α permet à la multiplication au sein du corps d'être maniée efficacement. Le polynôme primitif de α est le polynôme unitaire de plus petit degré possible à coefficients dans F$_p$ avec α pour racine dans F$_{pn}$ - le polynôme minimal pour α. Il est nécessairement irréductible. Le polynôme de Conway est choisi primitif, ainsi, chacune de ses racines engendre le groupe multiplicatif du corps fini associé.
Les sous-corps de F$_{pn}$ sont des corps de F$_{pm}$, avec m diviseur de n. Le groupe cyclique formé à partir des éléments non nuls de F$_{pm}$ est un sous-groupe du groupe cyclique F$_{pn}$. Si α engendre ce dernier, alors la plus petite puissance de α qui engendre F$_{pm}$ est α$^r$ où r = (p$^n$ − 1)/(p$^m$ − 1). Si f$_n$ est un polynôme primitif de F$_{pn}$ avec α pour racine, et si f$_m$ est un polynôme primitif de F$_{pm}$, alors, d'après la définition de Conway, f$_m$ et f$_n$ sont compatibles si α$^r$ est racine de f$_m$. Cela nécessite que f$_n$(x) divise f$_m$(x$^r$). Cette notion de compatibilité est nommée compatibilité en norme par certains auteurs. Le polynôme de Conway pour un corps fini est choisi afin d'être compatible avec les polynômes de Conway de chacun de ses sous-corps. La possibilité d'un tel choix a été prouvée par Werner Nickel.

## Définition

Le polynôme de Conway C$_{p,n}$ est défini comme le polynôme primitif, unitaire et lexicographiquement minimal de degré n défini sur l'espace F$_p$ qui est compatible avec C$_{p,m}$ pour tout m diviseur de n. Ceci est une définition inductive sur n : le cas basique est C$_{p,1}$(x) = x − α où α est l'élément primitif et minimal pour l'ordre lexicographique de F$_p$. La notion d'ordre lexicographique utilisé est le suivant :
* les éléments de F$_p$ sont ordonnés selon 0 < 1 < 2 < ⋅⋅⋅ < p − 1 ;
* un polynôme de degré d dans F$_p$[x] s'écrit a$_d$x$^d$ − a$_{d−1}$x$^{d−1}$ +⋅⋅⋅+ (−1)$^d$a$_0$ et est ensuite formulé simplement a$_d$a$_{d−1}$⋅⋅⋅a$_0$.
Puisqu'il ne semble pas y avoir de critère mathématique naturel qui permettrait de deviner un polynôme primitif unitaire satisfaisant aux conditions de compatibilité, imposer l'ordre lexicographique dans la définition du polynôme de Conway devrait être considéré comme une convention.

## Calcul

Des algorithmes pour calculer des polynômes de Conway plus efficaces qu'une recherche naïve ont été développés par Heath et Loehr. Lübeck note que leur algorithme est une redécouverte de la méthode de Parker.

## Source

* (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Conway polynomial (finite fields) » (voir la liste des auteurs).