Polynôme de Conway (corps finis)

Cet article est orphelin. Moins de trois articles lui sont liés (novembre 2022).

Vous pouvez aider en ajoutant des liens vers [[Polynôme de Conway (corps finis)]] dans les articles relatifs au sujet.

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^[1], Macaulay2 (en)^[2], Magma^[3], SageMath, et le site internet de Frank Lübeck^[4].

Contexte[modifier | modifier le code]

Les éléments de F_pⁿ peuvent être représentés comme des sommes de la forme a_n−1βⁿ⁻¹ +⋅⋅⋅+ a₁β + a₀ 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ⁿ à 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_pⁿ 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_pⁿ - 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_pⁿ sont des corps de F_p^m, avec m diviseur de n. Le groupe cyclique formé à partir des éléments non nuls de F_p^m est un sous-groupe du groupe cyclique F_pⁿ. Si α engendre ce dernier, alors la plus petite puissance de α qui engendre F_p^m est α^r où r = (pⁿ − 1)/(p^m − 1). Si f_n est un polynôme primitif de F_pⁿ avec α pour racine, et si f_m est un polynôme primitif de F_p^m, 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^[5].

Définition[modifier | modifier le code]

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_dx^d − a_d−1x^d−1 +⋅⋅⋅+ (−1)^da₀ et est ensuite formulé simplement a_da_d−1⋅⋅⋅a₀.

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[modifier | modifier le code]

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^[6]. Lübeck note^[4] que leur algorithme est une redécouverte de la méthode de Parker.

Source[modifier | modifier le code]

• (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).

Références[modifier | modifier le code]

• Portail de l’algèbre