Calcul Formel
Master CRYPTIS - 2021/2022
Université de Limoges
Moulay Barkatou
Enseignants de l’UE
Moulay Barkatou - CM et TD
[Link]@[Link]
XLIM Bat G, 4E, bureau X-40?
Mercedes Haiech - TD et TP
[Link]@[Link]
XLIM Bat G, 4E, bureau X-40?
Planning de l’UE
Cours en présentiel (7 ECTS avec Syst. Pol.)
semaines 1-6 : 10/01-18/02
vacances : 21-25/02
semaines 7-13 : 28/02-15/04
vacances : 18-29/04
semaine 14 : 02-06/05
la répartition en CM/TD/TP sera communiqué au fur et à mésure
Modalités de contrôle
Calcul Formel (CF) fait partie de l’UE Algèbre 2 avec Systèmes
Polynomiaux (SP). La note est globale.
Pour CF : note finale 2
3 E 1 + 1 P , où
3 1
• note E1 : épreuve écrite en fin de semestre
• note P1 : participation/projet (modalité à déterminer)
Pour SP : Même chose, avec notes E2 et P2.
Note finale de l’UE Algèbre 2 :
1 (CF) + 1 (SP) = 1(2 E + 1 P ) + 1(2 E + 1 P )
2 2 2 3 1 3 1 2 3 2 3 2
Plateforme en ligne Community
Les notes de cours et les autres sources sont disponibles sur
Community
En particulier, vous allez utiliser les outils suivants
Forum – pour discuter avec les camarades
BBB (BigBlueBotton) – si besoin pour les cours (en ligne)
et les examens (en ligne)
Devoir – éventuellement pour rendre des CR
TD et TP en Maple ou SAGE
Merci de télécharger et installer des maintenant Maple, vous
pouvez trouver une version avec licence étudiants à cet adresse
(voir Community) :
Maple
Le mot de passe pour la page Community/Maple est : MAPLE
Quelques références
Polycopié : “Notes de cours” tapées par T. Cluzeau
Univ. Limoges, 2016.
Livre 1 : “Algorithmes Efficaces en Calcul Formel” par Bostan
et al.
Hal, 2017.
Livre 2 (en anglais) “Modern Computer Algebra” by von zur
Gathen, Gerhard.
Cambridge Univ. Press, 3rd edition 2013.
Mes transparents disponibles sur
Community
Programme (prévisionnel) de l’UE
Rappèls d’algèbre et complexité
Algorithmes rapides pour la multiplication dans K[X] et K n×n
Calcul du PGCD et résultants, applications
Factorisation dans K[X]
Introduction
Calcul formel
Le terme Calcul formel (aka Computer Algebra ou Symbolic
Computation) désigne l’étude de la représentation et de la ma-
nipulation effective d’objets algébriques (nombres, polynômes,
matrices...) par un ordinateur.
En CF nous nous intéressons à montrer des résultats mathéma-
tiques de manière constructive et rigoureuse.
On utilise le terme 00formel00 pour le distinguer du calcul numérique,
qui manipule des représentations tronquées et approchées1. En
CF on s’intéresse à fournir un résultat exact.
1 Par
√
exemple voici deux représentations différentes de 2 :
1.41421356..
racine positive de q(t) = t2 − 2
Un premier objectif, proposer des algorithmes efficaces pour
les opérations de base et d’autres calculs dans les structures
algébriques principales : algèbres de polynômes, espaces vecto-
riels...
Un autre objectif est de montrer que certains problèmes peu-
vent se reduire (ou encore mieux, sont équivalents) à d’autres
problèmes∗ avec une complexité connue.
∗ Par exemple la multiplication de matrices est un problème universel en
algèbre linéaire.
Exemple : factorisation d’un polynôme (Sage)
Exemple : forme implicite d’une courbe (M2)
Courbe : image de ϕ(t) = (t, t3, t5) dans R3
Exemple : calcul du PGCD de deux polynômes
de “Algorithmes Efficaces en Calcul Formel (Bostan et al.)”
Corps de base et espaces vectoriels
K corps de base, par exemple K = Z/pZ, Q, R, C...
K n : K-espace vectoriel de dimension n
K n×n : K-espace vectoriel des matrices n × n sur K
Opérations dans K, K n et K n×n : addition et multiplication par
scalaire.
Opération ulterieure dans K n×n en tant que K-algèbre : produit.
Clôture algébrique
Soit K un corps et L une extension de K. Un élément a ∈ L est
algébrique sur K s’il existe 0 6= f ∈ K[X] tel que f (a) = 0, sinon
il est dit transcendent. Une extension L de K est dite algébrique
si tout a ∈ L est algébrique sur K.
√
Exemples : 2 ∈ R est algébrique sur Q, mais π est transcendent.
Les éléments de L qui sont algébriques sur K forment ce qu’on
appelle la clôture algébrique de K dans L, notée K L.
On va noter QR simplement par Q.
Polynômes et fractions rationnelles
A = K[X1, . . . , Xn] algèbre des polynômes en plusieurs indéterminées
à coefficients sur K, qui est une algèbre graduée par le degré :
M
A= Ad et AdAe ⊂ Ad+e
d
avec Ad = polynômes homogènes de degré d.
K(X1, . . . , Xn) corps des fractions de K[X1, . . . , Xn]:
( )
f
K(X1, . . . , Xn) = : f, g ∈ K[X1, . . . , Xn], g 6= 0 .
g
Le Calcul Formel se base sur sur la contrainte suivante:
Par contre, ça ne veut pas dire qu’on ne peut pas tester ces
égalités dans certains cas particuliers, par exemple on peut décider
l’égalité suivante :
Structures effectives
On parle de structure algébrique pour faire réference aux struc-
tures classiques, par exemple anneaux A = (A, +, ×), groupes
A = (G, +), corps, algèbres etc ...
Une structure algébrique A est dite effective si l’on dispose :
• d’une structure de données pour en représenter les éléments
• d’algorithmes pour en effectuer les opérations et pour y
tester l’égalité à zéro.
Rappel : tester pour a, b ∈ A si a = b se ramène à tester a−b = 0A
Exemples
• Les anneaux Z et Z/pZ sont des structures effectives
• Si K est un corps effectifs, alors sa clôture algébrique K,
et les espaces vectoriels K n et K n×n sont effectives
• Si A est un anneau effectif, alors son corps des fractions,
l’anneau A[X1, . . . , Xn], et A[X]/(X d+1) sont effectifs.
• Pour les systèmes polynomiaux : si K est effectif, alors
K[X1, . . . , Xn]/(f1, . . . , fs) est effectif, pour des polynômes
f1, . . . , fs.
Méthodes modulaires
Le fait que Z/pZ est une structure effective nous permet par-
fois de concevoir des algorithmes basés sur le calcul modulo un
nombre premier p (assez grand).
Au lieu d’effectuer les calculs sur Z, nous effectuons les calculs
dans Z/pZ pour un (ou plusieurs) nombres premiers p.
Cela nous permet, par exemple, de contrôler la croissance des
entiers dans les étapes intermediaires (phénomène courant, voir
exemple PGCD).
Méthodes modulaires
• L’algorithme appliqué “modulo p” donne une méthode prob-
abiliste répondant à la question. Si on maitrise les mau-
vais nombres premiers pour lesquels la réponse est fausse,
alors on obtient une méthode déterministe
• Lorsqu’une borne sur la taille des entiers du résultat est con-
nue, on peut alors utiliser une stratégie basée sur le théorème
des restes chinois, qui implique qu’un entier inférieur à un
produit de nombres premiers p1 · · · pk peut être reconstruit à
partir de ses réductions modulo p1, . . . , pk
Méthodes modulaires en Maple
Calculs qu’on peut mener en 1s en Maple (K = Z/67108879Z) :
• produit de deux entiers avec 30000000 chiffres
• factorisation d’un entier de 42 chiffres
• produit de deux polynômes dans K[X] de degré 650000
• produit de deux matrices dans K 850×850
Correction d’un algorithme
Un algorithme est dit correct si
• l’algorithme est constitué d’un nombre fini d’étapes
• chaque étape est bien définie
• le résultat renvoyé est celui que l’on attend.
Dans un papier scientifique qui utilise des méthodes algébriques /
formelles, tout algorithme fait l’objet d’une preuve mathématique
de correction.
Exemple : évaluation dans K[X]
Soit g = i giX i ∈ K[X]≤d et a ∈ K. Évaluer g en a veut dire
P
calculer l’image eva(g) de g par la fonction d’évaluation :
eva : K[X] → K
i i
i fi X 7→
P P
i fi a
c’est-à-dire la fonction eva(f ) = f (a).
• Algorithme naı̈f : on calcule g1a, g2a2, g3a3, . . . , gdad, qui “coûte”
2d − 1 produits, et après on a d additions, donc 3d − 1
opérations.
• Le schéma de Horner est plus efficace :
g(a) = g0 + a(g1 + a(g2 + a(. . . + a(gd−1 + agd) . . .)))
Exercice : montrer que la formule de Horner est correcte.
Complexité d’un algorithme
Pour définir un modèle de complexité (en temps), nous avons
besoin de définir les opérations disponibles et leur coût unitaire.
Nous nous intéresserons au modèle suivant :
Complexité arithmétique. C’est le modèle de complexité qui
compte le nombre d’opérations élémentaires dans la structure
A. Il reflète le coût réel si les opérations dans A ont un coût
constant et prépondérant.
Il y a d’autres modèles importants en CF : complexité binaire,
machines de Turing, etc..
Asymptotiques /1
Nous utilisons la notation classique O(...) pour définir les asymp-
totiques (n → +∞) :
f (n) = O(g(n)) s’il existe C > 0 tel que |f (n)| ≤ C|g(n)|
pour n >> 0.
Nous utilisons pour simplifier la notation Õ(...) pour oublier les
facteurs logarithmiques:
Õ(n) = O(n log(n)k ) pour un certain k.
Par exemple O(n log(n) log log(n)) = Õ(n).
Asymptotiques /2
On dit qu’un algorithme de complexité
• O((log(n))k ) est logarithmique en n
• O(n) est linéaire en n
• Õ(n) est quasi-linéaire en n (soft-linear)
• O(n2) est quadratique, O(n3) cubique en n
• O(nk ) est polynomiale en n
• O(2n) est exponentiel en n
La pluspart des algorithmes dans ce cours seront en O(n3).
Évaluation-intérpolation (prélude)
C’est un principe général souvent utilisé en CF (mais aussi en
numérique), qui se base sur les étapes suivantes.
On suppose vouloir effectuer une certaine opération binaire ,
c’est-à-dire calculer f g (avec [Link]. f, g ∈ A[X]).
• On choisit des éléments a1, . . . , as ∈ A (par exemple, des
racines de l’unité, ou des valeurs en progression arithmétique)
• On évalue f et g en a1, . . . , as (évaluation)
• On déduit les évaluations (f g)(a1), . . . , (f g)(as)
• À partir de ces évaluations, on reconstruit f g (interpola-
tion)
Diviser-pour-reigner
Plusieurs algorithmes se basent sur le paradigme “diviser-pour-
reigner”, l’idée étant de résoudre un problème en le réduisant à
m instances du même problème sur des entrées de taille n/p.
Soit C(n) la complexité inconnue d’un tel algorithme. Elle va
dépendre:
• du coût κ du même algorithme avec entrée de taille s ≥ p
suffisamment petite
• du coût T (n) de découpage et recombinaison initial
La complexité vérifie alors l’inégalité récurrente
Complexité du diviser-pour-reigner
Théorème.
Soit C(n) une fonction vérifiant l’inégalité récurrente
précédente, avec T telle que qT (n) ≤ T (pn) ≤ rT (n) pour
n assez grand et pour certaines constantes q et r.
Alors pour n → +∞
O(T (n)) si q > m
C(n) = O(T
(n) log(n)) si q = m
log (m) T (n)
O n p sinon.
nlogp (q)
Preuve : voir AECF, page 27, Lemme 1.12.
Un exemple
Nous verrons que le coût K(n) de l’algorithme de Karatsuba pour
le calcul du produit de deux polynômes de degré au plus n − 1
vérifie :
K(n) ≤ 4 n + 3 K(dn/2e), K(1) = 1.
Avec les notations précédentes, on a donc m = 3, p = s = 2,
κ = 1 et T (n) = 4 n vérifie q T (n) ≤ T (p n) ≤ r T (n) avec q = r =
p = 2.
On a donc q < m de sorte que
4n
K(n) = O nlog2(3) = O(nlog2(3)).
nlog2(2)
Représentation (dense) dans K[X1, . . . , Xn]
L’algèbre K[X1, . . . , Xn] a dimension infinie en tant que K−espace
vectoriel (de même pour A[X1, . . . , Xn] en tant que module et
algèbre sur A), mais on peut tronquer en degré d et obtenir des
espaces vec. de dimension finie.
Il y a plusieurs façons de représenter un polynôme f ∈ K[X1, . . . , Xn]
dans un ordinateur, la plus simple étant en base monomiale
Nn
fα X α
X
f = ∼ (fα)α∈Nn ∈K d
d
α
où d = deg(f ) et
Nn
d = {β ∈ N n : β + · · · + β ≤ d}
1 n
α = (α1, . . . , αn) ∈ Nn
d
α α
X α = X1 1 X2 2 · · · Xnαn
Représentation (dense) dans K[X1, . . . , Xn]
Par exemple (n = 1)
f = X 5 + 3X 2 + X + 1 ∼ (1, 0, 0, 3, 1, 1)
Ou encore pour n = 3, on a
f = 1 + X1X2X32 − 3X25 = X (0,0,0) + X (1,1,2) − 3X (0,5,0)
∼ (1, 0, . . . , 0, 1, 0, . . . , 0, −3, 0, . . . , 0)
Pour n = 1, le terme de plus haut degré est dit terme de tête.
En plusieurs variables : ordres monomiaux (voir UE Systèmes
Polynomiaux).
Représentation creuse dans K[X1, . . . , Xn]
Dans certains situations les polynômes qu’on manipule ont très
peu de coefficients différents de zero, ce qui amène à la necessité
d’une représentation plus efficace.
On appelle représentation creuse d’un polynôme f = α fαX α la
P
suite de ses coéfficients différent de zero, ou plus formellement
la suite :
[(fα1 , α1), . . . , (fαt , αt)]
telle que
f α X α = f α1 X α1 + · · · + f αt X αt .
X
α6=0
En représentation creuse, on aurait
f = 1+X1X2X32 −3X25 ∼ [(1, (0, 0, 0)), (1, (1, 1, 2)), (−3, (0, 5, 0))]
