L’arithmétique dans les corps finis
MVE VERIL-GERIEL
Directeur de mémoire : Pr. Tony Ezome
Département de Mathématiques
École Normale Supérieure
Chapitre 1
Applications de l’arithmétique dans
les corps finis
1.1 Introduction
L’arithmétique dans les corps finis, longtemps étudiée pour son intérêt théorique, a
trouvé depuis plusieurs décennies des applications pratiques majeures dans les domaines
de la sécurité de l’information, des communications numériques et du calcul informatique.
Ce chapitre présente les principales applications de cette théorie, en insistant sur les
domaines de la cryptographie, de la théorie des codes correcteurs d’erreurs et du
calcul symbolique.
1.2 Cryptographie moderne
L’un des domaines où les corps finis s’illustrent de manière remarquable est la cryp-
tographie. La sécurité de nombreux protocoles repose sur des propriétés algébriques des
éléments de Fq , telles que l’inversibilité, la difficulté de la factorisation, ou encore le calcul
de logarithmes discrets.
1.2.1 Algorithmes cryptographiques sur Fq
Des systèmes tels que Diffie-Hellman, ElGamal, ou DSA sont construits sur le
problème du logarithme discret dans F∗q , dont la complexité est un atout pour garantir la
sécurité.
Par exemple, dans le système ElGamal :
— L’utilisateur choisit un corps Fq , un générateur g, et une clé secrète a.
— La clé publique est (q, g, g a ).
— Le chiffrement repose sur le calcul de puissances dans Fq , et le déchiffrement sup-
pose la connaissance de a.
1.2.2 Courbes elliptiques sur Fq
Les courbes elliptiques définies sur des corps finis offrent un cadre plus sécurisé
pour une taille de clé plus petite. Les opérations algébriques définies sur les points de
la courbe forment un groupe abélien fini utilisé dans l’algorithme ECC (Elliptic Curve
1
Cryptography). Par exemple, la courbe y 2 = x3 + ax + b sur Fp avec 4a3 + 27b2 6= 0 permet
de définir des opérations sécurisées sur les points.
1.3 Théorie des codes
La transmission de l’information nécessite des mécanismes de détection et de correc-
tion d’erreurs. C’est dans ce contexte que s’inscrivent les codes correcteurs d’erreurs,
notamment ceux construits sur Fq .
1.3.1 Codes de Reed–Solomon
Définis sur un corps fini Fq , les codes de Reed–Solomon permettent de corriger plusieurs
erreurs sur des blocs de données. Ils sont utilisés dans :
— les CD, DVD, QR codes ;
— les communications satellites ;
— les transmissions numériques sécurisées.
Le codage consiste à évaluer un polynôme de degré < k en n points distincts de Fq .
1.3.2 Codes de BCH et Goppa
Ces codes sont également construits à partir de polynômes sur Fq et offrent de très
bonnes capacités de correction. Les codes de Goppa, en particulier, sont utilisés dans la
cryptographie post-quantique (comme McEliece).
1.4 Calcul symbolique et applications informatiques
Dans les logiciels de calcul formel (comme SageMath, Maple ou Magma), les corps finis
sont utilisés pour des manipulations efficaces d’objets algébriques, comme :
— la factorisation de polynômes,
— le calcul de matrices sur Fq ,
— les algorithmes de résolution d’équations.
1.5 Cryptographie post-quantique : perspectives
Face à l’avènement des ordinateurs quantiques, certains systèmes classiques deviennent
vulnérables. Les corps finis sont au cœur de nouvelles approches comme :
— la cryptographie basée sur les codes (McEliece),
— les constructions multivariées (systèmes polynomiaux sur Fq ),
— les protocoles à base de réseaux ou isogénies sur courbes.
1.6 Conclusion
Les applications des corps finis sont à la fois profondes et actuelles. Leur structure
permet de concevoir des systèmes robustes pour la sécurité, les communications et le
traitement de l’information. L’évolution vers la cryptographie post-quantique renforce
encore leur importance dans les décennies à venir.
2
1.7 Bases normales
Dans cette section, nous introduisons la notion de base normale dans une extension
finie de corps finis. Ces bases possèdent des propriétés algébriques et computationnelles
très utiles, notamment dans les applications en cryptographie et en calcul algorithmique.
1.7.1 Définitions et premiers exemples
Soient q une puissance d’un nombre premier p, et Fqn une extension de degré n du
corps fini Fq . Un élément θ ∈ Fqn est dit normal sur Fq si l’ensemble de ses conjugués
sous l’action de l’endomorphisme de Frobenius
2 n−1
{θ, θq , θq , . . . , θq }
forme une base de l’espace vectoriel Fqn sur Fq . Une telle base est appelée une base
normale.
Considérons le corps F4 = F2 [α] où α est une racine irréductible de x2 + x + 1. On a
alors :
F4 = {0, 1, α, α2 }
On vérifie que α2 = α + 1, et que α4 = α. L’élément α est normal sur F2 , car :
{α, α2 } = {α, α + 1}
est une base de F4 sur F2 .
1.7.2 Théorème d’existence
[Théorème de la base normale] Pour toute extension finie Fqn /Fq , il existe une base
normale.
Ce résultat repose sur des considérations du groupe de Galois de l’extension. Soit
Fqn une extension de Fq , alors son groupe de Galois est cyclique d’ordre n engendré par
l’endomorphisme de Frobenius σ : x 7→ xq .
Il existe un théorème général de la théorie de Galois (cf. [1]) qui affirme qu’un corps
fini est un module simple sur son algèbre de groupe. En particulier, cela signifie qu’il
existe un élément θ tel que ses conjugués sous σ soient linéairement indépendants sur Fq :
une base normale.
1.7.3 Multiplication dans une base normale
La multiplication de deux éléments exprimés dans une base normale est particulière-
ment intéressante car l’application de Frobenius, x 7→ xq , devient une simple permutation
circulaire des coordonnées.
n−1
Soit une base normale {θ, θq , . . . , θq }, et soient
n−1 n−1
i i
xi θ q , yi θ q
X X
x= y=
i=0 i=0
alors
n−1 n−1
q q i+1 i
xi−1 θq (mod n)
X X
x = xi θ =
i=0 i=0
ce qui correspond à une rotation circulaire à droite.
3
1.7.4 Bases normales optimales
Dans certaines situations, il est possible de construire des bases normales dites opti-
males, ou ONB (Optimal Normal Basis), qui minimisent la complexité de la multiplica-
tion.
Une base normale est dite optimale si le nombre de produits non nuls requis pour
multiplier deux éléments du corps dans cette base est minimal.
Il existe deux types de bases normales optimales (type I et II), mais leur existence
dépend de conditions précises sur n et q (cf. [2], [3]).
La base {α, α2 } de F4 sur F2 est une base normale optimale de type I.
1.7.5 Applications
Les bases normales sont très utilisées dans les domaines suivants :
— Cryptographie : multiplication efficace dans des corps étendus, comme dans les
courbes elliptiques ou les systèmes RSA à clés tordues.
— Codage : représentation efficace pour les codes de Reed-Solomon ou les codes
BCH.
— Calcul hardware : multiplication rapide par circuits logiques utilisant des déca-
lages.
1.7.6 Références
4
Bibliographie
[1] R. Lidl, H. Niederreiter, Finite Fields, Cambridge University Press, 1997.
[2] S. Gao, Normal Bases over Finite Fields, PhD thesis, University of Waterloo, 1993.
[3] J. Dempsey, A. Hasan, Multiplication in Optimal Normal Bases Using Low Complexity
Multipliers, IEEE Transactions on Computers, 2016.