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) ∈ \mathbb{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 ∩ \mathbb{F}_{13}[x]\).

  2. Quelle est la dimension de \(I_P\) ? Quelle est la dimension de \(\mathbb{F}_{13}[x,\bar{y}]/I_P\) en tant qu’espace vectoriel ?

  3. Vérifier que \(g\) se scinde dans \(\mathbb{F}_{13^4}\), vérifier que toute racine de \(P\) dans \(\mathbb{F}_{13^4}\) est aussi racine de \(g\).

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

  5. Calculer des générateurs des idéaux \(I_P∩\mathbb{F}_{13}[y_1]\), \(I_P∩\mathbb{F}_{13}[y_2]\) et \(I_P∩\mathbb{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 \(\mathbb{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 \(ζ ∈ \mathbb{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 \(\mathbb{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 \(\mathbb{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 ∩ \mathbb{F}_p[y_i]) = \{L_i(α) \mid α∈\mathbb{F}_{p^n}, P(α)=0\}\) pour tout \(i<n\).

  6. Prouver que \(V(I_P ∩ \mathbb{F}_p[y_{n-1}]) ⊂ \mathbb{F}_p\).

Un algorithme de recherche de racines

Réaliser en Sage un algorithme de recherche de racines dans \(\mathbb{F}_{p^n}\). L’algorithme procède en calculant \(V(I_P∩\mathbb{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∩\mathbb{F}_p[y_{n-2}])\), …, \(V(I_P∩\mathbb{F}_p[y_0])\).

Le pseudo-code de l’algorithme suit :

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

Sortie: Les racines de \(P_0\) dans \(\mathbb{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∩\mathbb{F}_p[y_{n-1}])\) par recherche exaustive dans \(\mathbb{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\).

Fork me on GitHub