TP: Algorithme de Wiedemann
Option Algèbre et Calcul Formel, Préparation à l'Agrégation de Mathématiques d'Orsay
Examples de codes correcteurs d'erreurs
Document disponible au format: PDF, Postscript, DVI, Text, LaTeX, LyX.
1 Pot Pourri autour de l'algorithme d'Euclide
1.1 Calcul de PGCD (oeuf corse)
Exercice 1
Calculer le pgcd de 126 et 35
Applications:
-
Simplification de fractions rationnelles
- Forme normales dans Q, K(X), ...
- Extensions transcendantales de corps, ...
1.2 Décomposition sans carrés d'un polynôme
Exemple 1
Recherche de la décomposition sans carrés d'un polynôme, puis factorisation.
x5+x4−2x3−2x2+x+1
-
> > p := x^5 + x^4 - 2*x^3 -2*x^2 + x + 1;
> > pprime := diff(p, x);
> > g := gcd(p, pprime);
> > squareFree := divide(p, g, Exact);
> > factor(squareFree);
> > g := divide(g, x-1, Exact);
> > divide(g, x-1, Exact);
> > g := divide(g, x+1, Exact);
> > expand((x-1)^2 * (x+1)^3 );
1.3 Expansion en fractions continues
Exercice 2
Mettre 126/35 sous la forme q1+1/q2+1/q3+...
1.4 Euclide étendu, Bezout effectif
Algorithme d'Euclide étendu de deux éléments f et g d'un
anneau principal (Z, K[X], ...).
On note r0:=f, r1:=g, puis r2,...,rl et q2,...,ql
les restes et quotients successifs.
On veut maintenir l'invariant: sif+tig=ri.
Exercice 3
Retrouver s0, s1, t0, t1 et les équations
de mise à jour exprimant si et ti en fonction de si−2,
si−1, ti−2 et ti−1 .
Exemple 2
Calcul du PGCD étendu de x3−x et x2+1 (exemple 5.19 of
MCA).
Exercice 4
Compléter les colonnes si et ti du pgcd de 126 et 35.
1.5 Équations linéaires diophantiennes
Exercice 5
Résoudre l'équation diophantienne linéaire 126a+35b=21.
Applications:
-
Résolution d'équation linéaires sur Z, forme de Hermite,
- Algèbre linéaire sur les PID, structure des Z-modules,
...
- Classification des groupes commutatifs
1.6 Calcul d'inverse modulo n
Exercice 6
Inverse de 11 modulo 13?
Applications:
-
Corps effectifs: Z/pZ, extensions algébriques
K[X]/X2+1
- Calcul des clefs RSA, ...
1.7 Algorithme des restes chinois
Exemple 3
Trouver 0≤ f<100 tel que f=2mod11 et f=7mod13.
-
> > [g, s, t] := [igcdex(11,13)];
> > l1 := t*13; l2 := s*11;
> > l1 mod 11, l1 mod 13;
> > l2 mod 11, l2 mod 13;
-
> > f := (2 * l1 + 7 * l2) mod 11 * 13
> > f mod 11, f mod 13;
Exercice 7
Même chose, avec 3 entiers: f=2mod11, f=−1mod13, f=10mod17:
-
Construction des interpolants
- Description de l'ensemble des solutions
1.7.1 Cadre général (p. 102)
Description précise.
Theorem 4
5.2, Interpolants de Lagrange, ...
Application: méthodes multimodulaires en algèbre linéaire
Exemple 5
Calcul de déterminant sur Z.
-
> > M := Dom::Matrix(Dom::Integer):
A := M::random(6,6);
> > linalg::gaussElim(A);
Principe: se ramener à un calcul dans Z/pZ?
-
Étape 1: obtenir une borne sur |detA|:
Inégalité de Hadamard: |detA|≤C1⋯Cn≤ nn/2max(Aij)n
-
> > hadamard := float(6^(6/2) * 1000^6);
-
> > hadamard := float(_mult( norm(linalg::col(m,j),2)
$ j=1..6));
- On cherche suffisament de nombre premiers p1,...,pl tels
que p1... pl>|detA|:
-
> > p := 10000:
primes := []:
pprimes := 1;
while float(hadamard) / pprimes > 1 do
p := numlib::prevprime(p-1);
pprimes := pprimes * p;
primes := append(primes, p);
end:
- Pour chacun de ces nombres premiers, la taille des coefficients est
bornée:
-
> > Zp := Dom::IntegerMod(p): Zp::print := expr:
> > Ap := Dom::Matrix(Dom::IntegerMod(p)) (A);
> > linalg::gaussElim(Ap);
-
> > dets :=[linalg::det(Dom::Matrix(Dom::IntegerMod(p)) (A))
$ p in primes];
- On utilise le théorème des restes chinois pour reconstruire le déterminant:
-
> > lagrange := [op([igcdex(p, pprimes/p)],3) *
pprimes/p
$ p in primes];
> > map(lagrange, _mod, primes[3]);
> > _plus(op(zip(expr(dets), lagrange, _mult))) mod pprimes;
> > % -pprimes;
> > linalg::det(A);
Note: avec Maple ou MuPAD les arithmétiques modulaires ne sont pas
brillantes d'efficacité.
Du coup, le seuil au dela duquel les méthodes multimodulaires sont
rentables sont très élevés.
Par contre, tous les systèmes raisonnables les utilisent
couramment.
1.7.3 Interpolation de Lagrange
Trouver un polynôme ayant certaines valeurs en certains points.
Exercice 8
5.4 p. 131.
Applications:
-
Calcul rapide de produits de polynômes (complexité?)
- Codage, partage de secret
- Calcul de déterminant sur K[X] (voir TP, ou
exercice 5.32 p. 134)
- Calcul du polynôme caractéristique
1.7.4 Exemple trivial: Taylor
Trouver un polynôme ayant un certain développement de Taylor au point
x0=1.
1.7.5 Interpolation de Hermite
Mix de Taylor et Lagrange.
Applications:
-
Cubic spline (cf. ex. 5.35 p. 135):
Trouver une fonction de R dans R polynomiale
cubique par morceaux qui interpole les valeurs et dérivées premières
et secondes données en les bornes des intervalles.
- Courbes de Bézier (cf. ex 5.46 p. 136):
Courbe paramétrique cubique dans le plan passant par des points donnés,
avec des dérivées à gauche (Bi) et à droite (Ci) fixées.
1.7.6 Décomposition partielle des fractions rationnelles g/f
-
g/f1f2 avec f1∧ f2=1 .
- Cas f sans carrés.
- Cas f puissance; décomposition p-adique.
1.8 Algorithme des restes chinois rationnels
-
> > extendedEuclide :=
proc(f, g)
begin
r[0] := f; s[0] := 1; t[0] := 0;
r[1] := g; s[0] := 1; t[0] := 0;
i := 2;
while ... do
end_while
end_proc:
1.8.1 Interpolation de Cauchy
Exemple 6
(5.19 ii p. 118)
Objectif: trouver une fraction rationnelle r/t dans Q(x)
telle que:
Solution triviale par interpolation de lagrange: r/t=x2+1/1.
Du coup, r/t vérifie les conditions ci-dessus si et seulement
si r/t=x2+1mod x3−x.
On voudrait que r et t soient de petit degré.
Que peut-on espérer mettre comme contraintes?
Applications:
-
Calcul de déterminant dans K(X).
- Calcul de solutions Ax=y avec A à coeffs dans Q
(Cf. Ex 5.33 p.134).
1.8.2 Approximant de Padé (en TP)
1.8.3 Suites récurentes, Berlekamp-Masse
Lien suites récurentes / fractions (sur l'exemple de Fibonacci).
Reprendre l'exemple de l'article, dans Z/2Z,
s = 1 0 1 0 0.
1.9 Coefficients de Bezout et fonctions symétriques des racines
2 TP: Autour d'Euclide
Exercice 9
Comparer sur des matrices carrées aléatoires n× n à coefficients
dans Q[x] les différentes méthodes de calcul du déterminant:
-
Calcul direct
- Gauss / Gauss sans fractions / Gauss-Hermite
- Interpolation de Lagrange + Gauss
Pour aller plus loin:
-
Interpolation de Lagrange + Wiedemann + préconditionnement
- Qu'est-ce que cela donne pour calculer le polynôme charactéristique?
Comparer avec Wiedemann + préconditionnement
Une correction possible:
-
> > K := Dom::UnivariatePolynomial(z, Dom::Rational):
> > M := Dom::Matrix(K):
> > n := 8:
d := 5: // Random sur K renvoie des polynômes de degré <= 5
m := M::random(n,n):
> > time((det1 := linalg::det(m))); // 51 secondes
//mexpr := Dom::Matrix(Dom::ExpressionField(normal))(m):
//time(linalg::det(mexpr)); // Là, on est mort: 137 secondes
> > detMultiModulaire :=
proc(m)
begin
borne := d * n ; // le degré du déterminant est inférieur à cette borne
result := K::zero:
for i from 0 to d*n do
lagrange := _mult( K(z-j)/(i-j) $ j in {$0..i-1, $i+1..borne} );
me := matrix(mapcoeffs(m, evalp, z=i)):
result := result + lagrange * linalg::det(me);
end_for:
result;
end_proc:
> > time((det2 := detMultiModulaire(m)))
Exercice 10
Approximation de Cauchy
Calculer une fraction rationnelle ρ(x)=r(x)/t(x) dans
F5(X) avec degt(x)=degr(x)=1 telle que ρ(i)=2i
pour i=0,1,2.
Exercice 11
Approximation de Padé.
On appelle (n,k)-approximant de Padé en zéro de la fonction
tangente une fraction rationnelle réduite r(x)/t(x) avec
degr<k et degt≤ n−k telle que tan(x)−r(x)/t(x)=o(xn).
Un tel approximant est typiquement utile en analyse numérique pour
calculer des valeurs approchées de la fonction tangente.
Calculer de tels approximants pour quelques valeurs de n et k
et utiliser une représentation graphique pour évaluer leur qualité.
Indication: soit g(x)∈Q[x] constitué des n premiers
termes du dévelopement de Taylor de tan(x); utiliser l'algorithme
des restes chinois rationnel qui consiste à chercher les polynômes
r(x) et t(x) tels que r(x)=t(x)g(x)+s(x)xn dans les résultats
intermédiaires du calcul du pgcd étendu de f(x)=xn et g(x)
par l'algorithme d'Euclide. Si r(x)∧ t(x)=1, on a gagné (le
vérifier!). Sinon, on sait qu'il n'y a pas d'approximant (mais cela
demande une démonstration par un argument d'unicité!).
Utiliser l'algorithme des restes chinois pour construire une fonction
rationnelle qui approxime tan simultanément aux alentours de 0
et de π.
Exercice 12
Berlekamp-Massey, via Euclide.
Soit u0,u1,...,un−1 une séquence de n nombres. L'objectif
est de déterminer la relation de récurence de longueur l minimale
telle que la suite u est déterminée par ses l termes initiaux
u0,...,ul−1 et uk=−t1uk−1−t2uk−2−...−tluk−l
pour k>l. Vérifier que cela est équivalent à trouver deux polynômes
r de degré <l et t=t0+t1x+...+tlxl tels
que:
|
|
|
=u0+u1x+...+un−1xn−1+O |
⎛
⎝ |
xn |
⎞
⎠ |
Exercice 13
Courbes de Bézier
Exercice 5.46, p. 136-137 of Modern Computer Algebra.
Exercice 14
Opérateur Omega de Mac Mahon sur les séries génératrices et équations
diophantiennes
Développer en série les fractions rationnelles suivantes, et interpréter
combinatoirement leur termes:
|
|
| 1 |
|
| (1−tx1)(1−t2x2)(1−t3x3)⋯ |
|
, |
|
On cherche les solutions de l'équation diophantienne 2a1−3a2+a3+2=0
avec (a1,a2,a3)∈N.
Comment peut-on interpréter les termes de la série suivante, dans
laquelle on considère 1≫ z≫ x1≫ x2≫ x3:
|
|
| z2 |
|
| (1−x1z2)(1−x2z−3)(1−x3z) |
|
Calculer ce terme constant, en utilisant une décomposition partielle
en fractions.
En déduire le nombre de solutions de l'équation diophantienne avec
a1+a2+a3=20.
TP: Algorithme de Wiedemann
Option Algèbre et Calcul Formel, Préparation à l'Agrégation de Mathématiques d'Orsay
Examples de codes correcteurs d'erreurs
TP: Autour de l'algorithme d'Euclide /
Option Algèbre et Calcul Formel /
Nicolas M. Thiéry
Dernière modification: Mar 27 Mar 2007 10:32:52