AnnalesEnseignement

Agrégation externe 2020 — Mathématiques générales

Factorisation des polynômes de $\mathbb{Z}[t]$ par réduction modulo $p$ et réduction de réseaux · 12 pages

Le problème développe les outils d'un algorithme de factorisation des polynômes unitaires de $\mathbb{Z}[t]$ à partir d'une factorisation dans $\mathbb{Z}/p\mathbb{Z}[t]$ . Il étudie une suite matricielle arithmético-géométrique $X_{\ell+1} = A X_\ell + G$ construite à partir de matrices de moyennes, borne le déterminant de la matrice de Sylvester pour montrer qu'un polynôme à petits coefficients révèle un facteur non trivial, puis factorise dans $\mathbb{Z}/p\mathbb{Z}[t]$ par la décomposition en degrés distincts et un algorithme probabiliste à la Cantor-Zassenhaus. Les deux dernières parties décrivent la réduction de Gauss en dimension 2 et une réduction de réseaux de type LLL fournissant un vecteur presque minimal.

Le sujet, partie par partie

Notations et Exercice 1 — Une matrice $4 \times 4$ p. 2–3

Diagonalisation · Calcul matriciel · Déterminants · Applications linéaires et rang — rang, noyau, valeurs propres, matrice compagnon

Exercice 2 — Localisation des racines et coefficients des diviseurs p. 3

Racines et relations coefficients-racines · Matrices remarquables · Réduction des endomorphismes · Inégalités classiques — matrice compagnon, matrice à diagonale strictement dominante, disques de Gershgorin, borne de Cauchy sur les racines, coefficients d'un diviseur

Exercice 3 — Orthogonalisation de Gram-Schmidt et inégalité de Hadamard p. 4

Procédé de Gram-Schmidt · Déterminants · Espaces préhilbertiens et euclidiens · Inégalités classiques — procédé de Gram-Schmidt, déterminant de Gram, inégalité de Hadamard, famille orthogonale

Exercice 4 — Polynômes irréductibles sur $\mathbb{Z}/p\mathbb{Z}$ p. 4

Corps finis · Polynômes · PGCD, Bézout, Gauss · Anneaux et idéaux · Congruences et Z/nZ — polynôme $t^{p^n} - t$ , polynômes irréductibles sur $\mathbb{Z}/p\mathbb{Z}$ , anneau quotient, corps fini à $p^r$ éléments, pgcd de polynômes

Préambule et Partie 1 — Une suite matricielle arithmético-géométrique p. 5–6

Sous-espaces stables · Matrices stochastiques et bistochastiques · Rayon spectral · Applications linéaires et rang · Espaces préhilbertiens et euclidiens · Normes subordonnées et applications linéaires continues — matrice bistochastique, hyperplan stable, convergence des puissances d'une matrice, projection sur une droite parallèlement à un hyperplan, suite arithmético-géométrique matricielle

Partie 2 — Résultant et diviseurs à petits coefficients p. 6–7

Résultant et discriminant · PGCD, Bézout, Gauss · Polynômes · Déterminants · Congruences et Z/nZ · Inégalités classiques — matrice de Sylvester, relation de Bézout dans $\mathbb{Q}[t]$ , inégalité de Hadamard, réduction modulo $p$ , polynôme sans facteur carré, réseau $L_p(h)$

Partie 3 — Factorisation dans $\mathbb{Z}/p\mathbb{Z}[t]$ p. 7–8

Corps finis · Polynômes · Espaces probabilisés · Loi géométrique · Espérance, variance, moments · Anneaux et idéaux — factorisation en degrés distincts, algorithme de Cantor-Zassenhaus, carrés dans un corps fini, restes chinois, algorithme probabiliste, espérance du nombre d'essais

Partie 4 — Réduction de Gauss d'un réseau de dimension 2 p. 8–9

Polytopes et géométrie combinatoire · Projection orthogonale et moindres carrés · Groupes de matrices · Espaces préhilbertiens et euclidiens · Informatique et algorithmique — réseau de dimension 2, réduction de Gauss, matrice unimodulaire, entier le plus proche, vecteur court

Partie 5 — Réduction de réseaux de type LLL p. 9–11

Procédé de Gram-Schmidt · Polytopes et géométrie combinatoire · Matrices positives et stochastiques · Projection orthogonale et moindres carrés · Suites numériques · Informatique et algorithmique — algorithme LLL, réseau euclidien, vecteur le plus court, orthogonalisation de Gram-Schmidt, matrice à coefficients positifs, ordre partiel

Dans l'édifice

Matrices d'une application linéaire Déterminant d'un endomorphisme Formes multilinéaires alternées Applications linéaires Théorème du rang Anneaux de polynômes Espaces vectoriels normés et espaces de Banach Espaces de Hilbert et théorème de projection Théorème de représentation de Riesz Corps finis PGCD, théorème de Bézout, lemme de Gauss Anneaux Idéaux d'un anneau commutatif Anneau quotient et théorème d'isomorphisme Idéaux premiers et maximaux Les anneaux ℤ/nℤ Applications linéaires continues et dual topologique Spectre premier d'un anneau Espaces probabilisés et probabilités conditionnelles Variables aléatoires, lois, fonctions de répartition Espérance, variance et inégalités Théorème de Hahn-Banach Division euclidienne Le groupe linéaire et l'inversion des matrices Groupes de Lie et groupes de matrices Théorème de Cartan-von Neumann Théorème de définition par récurrence Suites réelles et limites Théorème de Bolzano-Weierstrass Complétude de ℝ