Devoir Maison 2015

Ce devoir est à réaliser dans une feuille de calcul Sage. Utilisez les cellules ordinaires pour faire les calculs, et les cellules de texte pour ajouter vos commentaires et les réponses aux questions. Rappel : vous pouvez saisir des formules au format LaTeX entre les symboles $ (dollar).

Envoyez votre travail complet par mail. Vous pouvez soit l’exporter au format .sws (« Save worksheet to a file… »), soit donner le lien du worksheet sur http://sage.math.uvsq.fr/ (et uniquement sur ce serveur).

Le but de ce sujet est de montrer comment on peut réduire un problème de factorisation à de l’algèbre linéaire. Il a été insipiré par ce papier.

Éliminer pour décomposer

Soit $P(x) ∈ \F_{13}[x]$ le polynome

$$P(x) = x^{18} + x^4 + x^3 - x + 1$$

et soit $I_P$ l’idéal

$$I_P = 〈 P,\; y_1-x^{13}-5x,\; y_2-y_1^{13}+5y_1,\; y_3-y_2^{13}-y_2,\; y_3^{13}-y_3 〉$$

1. Calculer un générateur $g$ pour l’idéal $I_P ∩ \F_{13}[x]$.

2. Quelle est la dimension de $I_P$ ? Quelle est la dimension de $\F_{13}[x,\bar{y}]/I_P$ en tant qu’espace vectoriel ?

3. Vérifier que $g$ se scinde dans $\F_{13^4}$, vérifier que toute racine de $P$ dans $\F_{13^4}$ est aussi racine de $g$.

4. Prouver que pour tout polynôme $P$ la variété $V(I_P ∩ \F_{13}[x])$ est de dimension zéro (dans $\F_{13}[x]$) et coincide avec les racines de $P$ dans $\F_{13^4}$.

5. Calculer des générateurs des idéaux $I_P∩\F_{13}[y_1]$, $I_P∩\F_{13}[y_2]$ et $I_P∩\F_{13}[y_3]$ (pour le $P$ donné plus haut).

Les résultants successifs

Soit $p$ un nombre premier et soit $n\mid(p-1)$.

1. Soient $f=\sum_i f_ix^i$, $g=\sum_i g_ix^i$ et $h=\sum_i h_ix^i$ trois polynômes à coefficients dans $\F_p$. Prouver que $h=fg$ si et seulement si

   $$\left(\sum_i f_ix^{p^i}\right)∘\left(\sum_i g_ix^{p^i}\right) = \sum_i h_ix^{p^i}.$$

2. Soit $ζ ∈ \F_p$ un élément d’ordre multiplicatif égal à $n$. Prouver que $(x^p - ζ^nx)∘\cdots∘(x^p - ζ^2x)∘(x^p - ζ x) = x^{p^n} - x$.

3. On définit la famille de fonctions

   $$\begin{aligned} L_0(x) &= x,\\ L_i(x) &= (x^p - ζ^ix) ∘ L_{i-1}(x) \quad\text{pour } 1 ≤ i ≤ n. \end{aligned}$$

   Montrer que $L_i$ est une application linéaire, et que son noyau est de dimension $i$.

4. Soient $α_1, \ldots, α_d$ des éléments de $\F_{p^n}$. Soit $P$ le polynôme

   $$P(x) = \prod_{j=1}^d(x - α_i).$$

   Quelles sont les racines de $\mathrm{Res}_x(P,\; y - L_i(x))$ ?

5. Soit $P$ un polynôme à coefficients dans $\F_{p^n}$, et soit $I_P$ l’idéal

   $$I_P = 〈 P(y_0) 〉 + \left\langle (y_{i+1} - y_i^p + ζ^{i+1}y_i)_{0≤ i<n-1} \right\rangle + 〈 y_{n-1}^p - y_{n-1} 〉$$

   Prouver que $V(I_P ∩ \F_p[y_i]) = \{L_i(α) \mid α∈\F_{p^n}, P(α)=0\}$ pour tout $i<n$.

6. Prouver que $V(I_P ∩ \F_p[y_{n-1}]) ⊂ \F_p$.

Un algorithme de recherche de racines

Réaliser en Sage un algorithme de recherche de racines dans $\F_{p^n}$. L’algorithme procède en calculant $V(I_P∩\F_p[y_{n-1}])$ à l’aide d’une suite de $n$ résultants puis en résolvant $n$ systèmes linéaires pour calculer successivement, $V(I_P∩\F_p[y_{n-2}])$, …, $V(I_P∩\F_p[y_0])$.

Le pseudo-code de l’algorithme suit :

Entrée: Un polynôme $P_0∈\F_{p^n}[x]$, une racine $n$-ième de l’unité $ζ$.

Sortie: Les racines de $P_0$ dans $\F_{p^n}$.

1. Pour $i$ allant de $0$ à $n-2$:

   • Calculer $P_{i+1} = \mathrm{Res}_{y_i}(P_i(y_i),\; y_{i+1} - y_i^p + ζ^{i+1}y_i)$

2. Calculer $V_{n-1} = V(I_P∩\F_p[y_{n-1}])$ par recherche exaustive dans $\F_p$.

3. Pour $i$ allant de $n-1$ à $1$:

   • Calculer $T = \{α \mid α^p - ζ^iα = v, v ∈ V_i\}$ en résolvant un système linéaire.
   • Calculer $V_{i-1} = \{α ∈ T \mid P_{i-1}(α)=0\}$.

4. Renvoyer $V_0$.