0% ont trouvé ce document utile (0 vote)

13 vues155 pages

Cryptographie et Codes M1 MIC 2020-2021

Transféré par

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

0% ont trouvé ce document utile (0 vote)

13 vues155 pages

Cryptographie et Codes M1 MIC 2020-2021

Transféré par

Qobbi

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Codes et crypto M1 MIC

année 2020-2021

Pascal Molin

13 décembre 2021
Cryptographie

I Notes de cours 1
1 Introduction 3

2 Théorie du chiffrement de Shannon 7

3 Cryptographie symétrique 13

4 Suites récurrentes linéaires 21

5 Algorithmes 29

6 Résultats d’arithmétique 41

7 Cryptographie asymétrique 49

8 Composition, primalité 59

9 Factorisation d’entiers 69

10 Logarithme discret 79

11 Protocoles cryptographiques 85

12 Réseaux et cryptographie 95

i
13 Codes linéaires 113

14 Représentations matricielles 117

15 Bornes, décodage 121

16 Constructions 127

17 Codes cycliques 133

18 Distance prescrite, codes BCH 139

19 Décodage des codes BCH 145

ii
Première partie

Notes de cours

1
CHAPITRE 1
Introduction

1.1 Protection de l’information

Le traitement ou l’échange d’information suit le schéma

général suivant. Un ensemble de données est successivement
— encodé, c’est-à-dire représenté sous une forme algébrique
permettant les opérations suivantes
— compressé,
— chiffré, c’est à dire protégé contre l’accès par des tiers
non autorisés (de sorte que l’information n’a plus de
signification pour qui ne possède pas une clef de
déchiffrement)
— inséré dans code correcteur, pour le protéger contre les
dégradations physiques
— transmis (réseau) ou stocké (disque)
À la réception ou lors de la restitution, les données font un
parcours inverse, elles sont décodées et d’éventuelles erreurs
sont corrigées, déchiffrées à l’aide d’une clef de déchiffrement,
décompressées et restituées sous forme finale.
Par exemple, le texte d’un article de journal est codé en langage
html sur le code UTF8, compressé via l’algorithme zip, authen-
tifié et chiffré suivant les standards SSL, puis codé et transmis
sur internet par paquets suivant le protocole TCP. Un lecteur
ayant une connexion SSL valide pourra déchiffrer les informa-
tions correspondantes et les restituer comme un texte mis en

3
Chapitre 1. Introduction

forme dans son navigateur.

Un autre exemple, un son musical enregistré est
d’abord échantillonné avec une certaine précision (taux
d’échantillonage, profondeur en bits, nombre de canaux)
pour être représenté par un ensemble fini de bits de données,
lesquels sont compressés selon le schéma MP3. Le fichier
produit peut être chiffré et inséré dans un conteneur DRM,
puis codé avec le double code CIRC avant d’être écrit bit à bit
sur un CD. À la lecture, le code CIRC permet de passer outre
les dégradations liées aux rayures du support, puis une licence
valide permet de déchiffrer les données pour accéder à un
format MP3 valide que le lecteur décompresse sous forme de
courbe de signal électrique que l’on transmet aux enceintes.
Remarque 1.1.1. Attention à ne pas révéler d’information sur le
message à cause de la phase de compression, voir par exemple
CRIME attack où la longueur du chiffré révèle l’efficacité de la
compression, et potentiellement des données.
Dans ce cours, on n’étudie que les parties chiffrement et la
dernière étape de codage (correcteur d’erreurs).

1.2 Cryptologie

Pour ce qui est du chiffrement, on peut détailler un peu plus :

avec des échanges à distance et dématérialisés, il est nécessaire
de pouvoir assurer quatre aspects
— confidentialité ≪ le message n’est compréhensible que
par ses seuls destinataires ≫. C’est l’objet du chiffrement.
— authentifier ≪ mon interlocuteur est bien celui qu’il
prétend être ≫ ; ≪ ce document a bien été écrit par moi
à cette date ≫
— vérifier l’intégrité ≪ ces données n’ont pas été altérées ≫
— empêcher la répudiation ≪ je ne peux pas nier que j’ai
effectué telle démrche ≫.
On doit prendre en compte la présence d’adversaires passifs
(écoute les communications) ou actifs (perturbe les messages,

4
1.2. Cryptologie

essaie d’usurper une identité. . .)

La cryptographie propose des méthodes, la cryptanalyse valide
ou infirme leur robustesse en cherchant des failles.

5
Chapitre 1. Introduction

6
CHAPITRE 2
Théorie du chiffrement de Shannon

Une référence : [?] (publication d’un rapport classifié de 1945)

2.1 Formalisme adopté

Un cryptosystème est la donnée de (M , C , K , e, d) où

— M , l’ensemble des messages possibles
— C , l’ensemble des chiffrés
— K , l’ensemble des clefs
— e : M × K → C la fonction de chiffrement
— d : C × K → M la fonction de déchiffrement
vérifient

∀k e ∈ K , ∃k d ∈ K , ∀m ∈ M , d(e(m, k e ), k d ) = m.

Le chiffrement est dit symétrique si k e = k d , et asymétrique

si connaissant k e il est calculatoirement très difficile de
déterminer k d .

7
Chapitre 2. Théorie du chiffrement de Shannon

2.2 Exemple des chiffres classiques

— Jusqu’à Vigenère : Voir la feuille.

Chiffres monoalphabétiques ou par blocs.
— Machine enigma : [Link]
enigma-machine

2.3 Attaques cryptographiques

Pour mesurer la résistance d’un chiffre à la cryptanalyse, on

distingue les degrés d’intrusion dans le sytème cryptogra-
phique suivants :
1. chiffré seul : on connaı̂t un chiffré. C’est le cadre clas-
sique.
2. clair connu : on connaı̂t un ou plusieurs couples clair-
chiffré.
3. clair choisi : on a accès à la fonction de chiffrement m ↦→
e(m, k) pour une ou plusieurs clefs k inconnues.
4. chiffré choisi : on a accès à la fonction de déchiffrement.
Un chiffre peut succomber à certaines attaques et résister à
d’autres. Ces attaques étant toutes très plausibles, un chiffre
doit être résistant pour chacune d’elles.
Exemple : le chiffre de Hill succombe immédiatement aux at-
taques 2-4.
Quelques techniques d’attaque :
— cryptanalyse fréquentielle : triviale pour le chiffre de
César, voir cette illustration pour le chiffre de Vigenère.
— force brute sur les clefs : on essaie toutes les clefs, on
utilise des mes mesures statistiques pour reconnaı̂tre les
bonnes clefs.
— technique du mot probable : on suppose la présence
d’une séquence dans le clair, et on réalise une attaque
à clair connu. C’est le principe de la bombe de Turing

8
2.4. Principes de la cryptographie moderne

pour attaquer Enigma, on réalise une attaque à force

brute pour trouver les clefs compatibles avec un mes-
sage contenant la date ou des indications de bulletin
météo.

2.4 Principes de la cryptographie moderne

2.4.1 Principe de Kerchkoffs

La sécurité d’un chiffre ne doit pas reposer sur le secret de la

méthode, mais sur le secret de la clef utilisée.

2.4.2 Principes de Shannon

Un chiffre doit apporter de la confusion et de la diffusion,

c’est-à-dire :
Confusion Il n’y a pas de relation algébrique simple entre
le clair et le chiffré. En particulier, connaı̂tre un certain
nombre de couples clair-chiffré ne permet pas d’interpo-
ler la fonction de chiffrement pour les autres messages.
Tout le contraire d’un chiffre affine.
Diffusion La modification d’une lettre du clair doit modi-
fier l’ensemble du chiffré. On ne peut pas casser le chiffre
morceau par morceau. Tout le contraire d’un chiffre mo-
noalphabétique.

2.5 Le théorème du secret parfait

Pour étudier un cryptosystème, Shannon introduit un modèle

de sécurité probabiliste. La sécurité est en effet toujours de na-
ture probabiliste : un attaquant peut tomber par hasard sur
la bonne clef. L’essentiel est que les interceptions de messages
n’augmentent pas ses chances.

9
Chapitre 2. Théorie du chiffrement de Shannon

Soit (M , C , K , e, d) un cryptosystème. On suppose

que l’émetteur choisit ses clefs de manière aléatoire
indépendamment des messages. Les messages qu’il en-
voie n’ont rien d’aléatoire, eux, mais l’attaquant qui essaie de
les deviner attribue à chacun une certaine probabilité a priori
(par exemple on pourrait considérer probable que le message
soit un texte en français, ou dans l’ensemble des en-têtes xml
valides, etc.).
On a donc deux variables aléatoire à valeurs dans M et K .
— Pour toute clef k ∈ K , on note Pr(k) la probabilité que
l’émetteur utilise la clef k.
— Pour tout message m ∈ M , on note Pr(m) la probabilité
a priori que le message émi soit m.
La fonction de chiffrement e : (m, k) ↦→ c = e(m, k) munit C
d’une probabilité sur les chiffrés, qui par indépendance vaut

Pr(c) = ∑ Pr(m) Pr(k).

e(m,k )=c

On a par ailleurs les probabilités conditionnelles suivantes

— Pr(c|m), la probabilité d’obtenir le chiffré c à partir de m,
qui est la probabilité de choisir une clef k qui envoie m
sur c. Cette probabilité vaut donc

Pr(c|m) = ∑ Pr(k )
k,e(m,k )=c

— Pr(m|c), la probabilité que c soit issu de m. C’est cette

probabilité a posteriori que l’émetteur ait émi m sachant
qu’on a intercepté le chiffré c, qui intéresse l’attaquant.
Via la formule de Bayes, elle vaut
Pr(c|m) Pr(m)
Pr(m|c) =
Pr(c)
Définition 2.5.1. Un cryptosystème est dit à secret parfait si la
réception d’un chiffré ne donne aucune information sur le clair dont
il est issu

∀m, c, Pr(m|c) = Pr(m)

10
2.5. Le théorème du secret parfait

Théorème 2.5.2. Soit (M , C , K , e, d) un cryptosystème. On sup-

pose que #M = #C = #K < ∞, et que Pr(m) > 0 pour tout clair
m ∈ M . Alors ce cryptosystème a secret parfait si et seulement si
— la distribution des clefs suit une loi uniforme ;
— pour tout clair m ∈ M ,
(
K →C
φm :
k ↦→ e(m, k)

est une bijection.

Démonstration. On suppose avoir secret parfait. On montre

d’abord la bijectivité, puis l’équiprobabilité.
Bijectivité s’il existe m tel que φm : k ↦→ e(m, k) est non
surjective, il existe c tel que ∀k ∈ K , e(m, k) ̸= c. En
particulier Pr(c|m) = 0, d’où l’on tire Pr(m|c) = 0 ̸=
Pr(m) > 0, impossible. Donc φm est surjective, et par
égalité des cardinaux bijective.
Équiprobabilité Soit c ∈ C un chiffré fixé. Pour tout m ∈
M , on note k(m) l’unique clef telle que e(m, k(m)) = c
(d’après la bijectivité). On a Pr(c|m) = Pr(k(m)).
Puisque par hypothèse Pr(m|c) = Pr(m), on obtient
Pr(k(m)) = Pr(c).
Or le chiffrement m ↦→ e(m, k) est injectif à clef fixé, donc
bijectif. Donc pour toute clef k, il existe m tel que k =
k ( m ).
Ainsi, Pr(k) = Pr(k(m)) = Pr(c) est constante, et vaut
1/#K .
Dans le sens réciproque, il suffit d’effectuer le calcul : par
équiprobabilité des clefs on a Pr(c) = ∑m,k Pr(m) Pr(k) =
Pr(k), d’où Pr(m|c) = Pr(c|m) Pr(m)/ Pr(c) =
Pr(m) Pr(k)/ Pr(k ) = Pr(m).

Exercice 2.5.3. Montrer qu’un cryptosystème est à secret parfait

si la probabilité d’obtenir un chiffré donné est indépendante du

11
Chapitre 2. Théorie du chiffrement de Shannon

message clair dont il est issu. En d’autres termes,

∀ m1 , m2 ∈ M , ∀ c ∈ C , p ( c | m1 ) = p ( c | m2 ).

2.6 Le chiffre de Vernam (1917)

Construire un cryptosystème à secret parfait est très simple : le

chiffre de Vigenère convient, à condition que la clef soit tirée
uniformément parmi les chaı̂nes de même longueur que le
message. Et pour ne pas divulguer cette longueur, il faut même
se placer dans un espace de messages de longueur fixée suffi-
sante, au moyen de padding.
Pour simplifier, on ne perd rien à effectuer les choses sur l’al-
phabet {0, 1}, si bien que le chiffre de Vernam n’est autre que
le xor du message et de la clef.
Évidemment, la clef ne doit être utilisée qu’une fois, puisque
m ⊕ k ⊕ m = k (attaque à clair connu sur la clef).

12
CHAPITRE 3
Cryptographie symétrique

3.1 Principes

La théorie de Shannon montre l’existence d’un chiffre sûr : le

chiffre de Vernam (one-time-pad). Sa sécurité repose sur le ca-
ractère vraiment aléatoire d’une clef aussi longue que le clair.
En pratique cependant,
— on ne sait pas générer de suite vraiment aléatoire
— une telle clef pose un problème de protocole : comment
la transmettre de manière sécurisée. . .
En cryptographie symétrique, on renonce à la sécurité recom-
mandée par Shannon, au profit d’une approche pragmatique :
avoir la plus grande sécurité possible pour une clef de taille
fixée à par exemple 128 ou 256 bits.
Pourquoi 128 bits ? [?]
On suppose donc K = F2` fixé, avec par exemple ` = 128, et
on suppose qu’on sait choisir de manière aléatoire un élément
k∈K.
Pour cela, deux grandes techniques :
— le chiffrement par flot (stream cipher) : on construit une
suite pseudo-aléatoire Lk : Z → F2 , et on utilise sa sortie
pour pour faire un chiffre de Vernam (xor avec le clair).

13
Chapitre 3. Cryptographie symétrique

— le chiffrement par bloc (block cipher) : on découpe le

clair en blocs de ` bits et on applique à chacun un cryp-
tosystème sur ` bits.
Deux remarques préliminaires :
Dans les deux cas, les méthodes adoptées combinent deux
ingrédients
— un côté algébrique qui assure de la diffusion
— un côté non-linéaire qui assure la confusion.
Par ailleurs la tendance en cryptographie est de prendre pour
chacun de ces ingrédients un système extrèmement simple, de
sorte qu’on suit les recommandations de Shannon sans y ajou-
ter quoi que ce soit.
Attention avec le mot aléatoire :
— pour faire un chiffrement par flot, on a besoin d’une
séquence pseudo-aléatoire (qui ressemble à de l’aléa)
mais parfaitement déterministe, puisque devant ne
découler que de la clef.
— pour choisir une clef (ou les paramètres d’un crypto-
système), on a besoin d’une source d’aléa forte.
Les techniques actuelles pour obtenir de l’aléa fort consistent
la plupart du temps à utiliser des chiffres par blocs nourris par
des compteurs et des valeurs système (heure, température du
processeur).

3.2 Chiffrement par flot

Une variante pratique du chiffre de Vernam est donnée par

les générateurs pseudo-aléatoires. La clef de chiffrement (et de
déchiffrement) étant l’initialisation du générateur.
On utilise en particulier les générateurs donnés par de simples
suites récurrentes linéaires d’ordre élevé : à petite échelle, elles
ont des propriétés statistiques similaires aux suites aléatoires.

14
3.2. Chiffrement par flot

Une suite récurrente de degré d est une suite pour laquelle il

existe des coefficients c0 , . . . cd−1 tels que
d −1
∀n, un+d = − ∑ ci u n +i
i =0
Sur le corps F2 ces suites récurrentes sont appelées LFSR, pour
Linear Feedback Shift Register : en effet on peut voir le fonc-
tionnement par récurrence comme l’application d’un masque
que l’on décale à chaque fois.

Théorème 3.2.1. Soit (un ) ∈ FN 2 une suite récurrente de degré d.

Alors
— (un ) est périodique, sa période est au plus 2d − 1
— il existe des coefficients c0 , . . . cd−1 tels que pour tout choix
d’initialisation u0 , . . . ud−1 , la suite (un ) obtenue est de
période 2d − 1.

15
Chapitre 3. Cryptographie symétrique

Même si le fait que la période est grande donne des propriétés

statistiques de type aléatoire à la suite, il ne faut surtout pas
l’utiliser directement comme séquence pseudo-aléatoire, car il
est facile de reconstruire algébriquement le polynôme minimal
d’une suite récurrente.
En revanche, combiner plusieurs générateurs permet d’obtenir
des suites qui résistent à l’étude.
Une technique est d’appliquer une fonction booléenne non
linéaire f : F2k → F2 aux sorties de k générateurs.
Une autre technique semble-t-il communément employée
consiste à prendre trois suites récurrentes : une suite de
contrôle C et deux suites de valeurs L0 et L1. La première est
incrémentée à chaque tour, sa valeur détermine laquelle des
deux suites L0 ou L1 est incrémentée. La sortie du générateur
est la somme des sorties courantes de L0 et L1.
Remarque 3.2.2. Attention, des variantes simples ne
fonctionnent absolument pas, comme le générateur de
Geffe [Link] attack#
Breaking the Geffe generator

3.3 Chiffres par blocs

Le message est découpé en blocs F2l sur lesquels opère le chif-

frement, avec l assez grand pour qu’une attaque par force brute
soit impossible.
Exemples :
— DES, blocs de 64 bits et clefs de 56 bits : ce n’est plus
assez (DES cracker opérait en ˜50h en 1998).
— AES, blocs de l = 128 ou 256 bits, clef de même taille l.

16
3.4. Construction du chiffre

3.3.1 Modes de chiffrement

Soit un message m découpé en blocs mi ∈ F2l , que l’on chiffre

avec un chiffre par blocs e : F2l × K → F2l .
Il y a plusieurs manières de procéder.
Mode ECB ≪ electronic code book ≫, blocs chiffrés
indépendemment, en parallèle

ci = e ( mi , k )

de sorte que

mi = d ( ci , k )

Mode CBC ≪ cipher block chaining ≫, un bloc dépend du

précédent
c1 = e ( m1 , k )
ci = e(mi + ci−1 , k) pour i > 1.
de sorte que

m i = d ( c i , k ) − c i −1

Mode CTC On chiffre successivement les entiers 1, . . . n, ce

qui construit un flot que l’on ajoute au message.

ci = mi + e(i, k)

Si le cryptosystème est résistant aux attaques à clair

connu cela ne pose pas de problème.

3.4 Construction du chiffre

Le principe général des chiffrements par blocs est d’effectuer

un certain nombre de tours d’un chiffrement élémentaire assu-
rant les deux aspects de confusion (par l’application de fonc-
tions non linéaires) et de diffusion (par permutation des bits),

17
Chapitre 3. Cryptographie symétrique

chaque tour étant paramétré par une clef de tour dérivée de la

clef initiale (en général il suffit d’ajouter la clef de tour avec un
Généralités DES AES
Clé secrète
xor).
Chi↵rement par blocs Feistel

CONSTRUCTION
Pour ces chiffres, un tourDE CHIFFREMENT
est très BLOCS
facile à casser, mais l’accumu-
lation de tours rend l’analyse extrèmement difficile.

Bloc de clair

Tour no 1

Dérivation Tour no 2
K des
sous-clés Tour 3

Tour no r

Bloc de chi↵ré

M1 – option Cryptologie — E. Bresson

Par exemple, le chiffrement d’un bloc DES se fait par 16 tours
CHIFFREMENT SYMÉTRIQUE 13/59
avec des sous-clefs de 48 bits. Pour AES, c’est aussi entre 10
et 20 tours, suivant la taille des blocs (on sait casser jusqu’à 7
tours).

3.4.1 Le schéma de Feistel

C’est une manière commode d’obtenir un tour inversible sur 2l

bits à partir d’une fonction non injective sur l bits.

18
ODE N 2: SCHEMA DE FEISTEL

e
3.4. Construction du chiffre
ne bijection sur 2n bits, à partir d’une fonction
non-bijective sur n bits
L0 R0
K
f (R0 ) f

est trivial :

f (R0 ) L1 R1

ction f est appelée la fonction de confusion

3.4.2 Substitutions-permutations
gie — E. Bresson
YMÉTRIQUE 15/59

s Dans AES, les transformations sont toutes inversibles et obte-

Feistel
nues par des opérations du corps F28 : la confusion est assurée
MÉTHODE No 1:x ↦→ x−1 (substitution
par l’inversion hautement non-linéaire),
TITUTIONS–PERMUTATIONS
et la diffusion par l’application d’une matrice circulante sur
F428 .

Message tour i

Ki
d’un tour:
n de la sous-clé
substitution Substitution
permutation
Permutation

Message tour i + 1

— E. Bresson
MÉTRIQUE 14/59

19
Chapitre 3. Cryptographie symétrique

20
CHAPITRE 4
Suites récurrentes linéaires

4.1 Cas binaire : LFSR

4.2 Définitions

Définition 4.2.1. Soit P( x ) = ∑id=0 ci xi un polynôme, tel que cd =

1. Alors pour tout d-uplet de valeurs initiales u0 , . . . ud−1 on définit
une suite (un ) par la relation de récurrence

d
∀k ≥ 0, ∑ uk+i ci = 0.
i =0

En d’autres termes, pour n ≥ d,

d −1
un = − ∑ ci u n − d +i
i =0

Ci-dessous, on calcule les n premiers termes de la suite (un )

dont c( x ) est un annulateur. Par commodité, on peut entrer les
premiers termes u0 , . . . ud−1 et le polynômes c0 , . . . cd comme
vecteur ou comme polynôme.
Par exemple, quelle est la période de la suite d’annulateur x6 +
x + 1 et commençant par 1, 0, 1, 0, 1, 0 ?

21
Chapitre 4. Suites récurrentes linéaires

Algorithme 4.2.1 suite récurrente

linrec(u0,c,n) = {
if(type(c)=="t POL",c=Vecrev(c));
d = #c - 1;
if(type(u0)=="t POL",u0=Vecrev(u,d));
v = Vec(u0,n);
for(k=d,n, v[k] = -sum(i=1,d,v[k-d+i]*c[i]));
v;
}

Algorithme 4.2.2 code gp

linrec([1,0,0,1,0],[1,0,0,0,1],40)

4.2.2 En termes de k [ x ]-module

Soit k un corps. On munit l’espace U = kN des suites à va-

leurs dans k d’une structure de k[ x ]-module via l’opérateur de
décalage

x.(un )n∈N = (un+1 )n∈N .

Pour toute suite (un ), on a un idéal annulateur

Iu = { P( x ) ∈ k [ x ], P( x ).u = (0)n }

Une suite récurrente est alors une suite (un ) dont l’idéal annu-
lateur est non-nul. Les éléments non nuls de Iu sont appelés des
polynômes annulateurs de la suite, et le générateur unitaire de
Iu est appelé polynôme minimal de la suite (il n’a aucune rai-
son d’être irréductible). On appelle ordre de la suite le degré de
son polynôme minimal.

22
4.3. Cas de Fq, suites maximales

Algorithme 4.2.3 code gp

linrec([1,1,1,1,1],[1,0,0,1,0],40)

Algorithme 4.2.4 code gp

4.2.3 Suites périodiques

Une suite est périodique de période l ≥ 1 si pour tout n ≥ 0,

un+l = un , c’est-à-dire que x l · (u) = (u), de sorte que x l − 1 ∈
Iu . Ainsi
Proposition 4.2.4. Soit (u) une suite récurrente de polynôme mini-
mal Pu . Alors (u) est périodique de période l ssi Pu | x l − 1.
Plus précisément, on a l’équivalence entre
— la période de (u) est exactement l
— l’ordre de x modulo Pu ( x ) vaut l.

4.3 Cas de Fq, suites maximales

Si k = Fq est fini, toute suite récurrente est ultimement

périodique.
Proposition 4.3.1. Soit (un ) une suite récurrente linéaire d’ordre d
sur Fq . Alors (un ) est ultimement périodique de période l ≤ qd − 1.

Démonstration. Appelons état une suite de d valeurs

(uk , . . . uk+d−1 ). Alors les valeurs ultérieures de la suite sont
déterminées par un état ; sur Fq il n’existe que qd états
différents. Par conséquent, on recroise un état en au plus qd
étapes. Si l’on met de côté l’état nul qui engendre la suite nulle,
la période maximale est même majorée par qd − 1.

On peut d’autre part exhiber des suites maximales

23
Chapitre 4. Suites récurrentes linéaires

Proposition 4.3.2. Soit d ≥ 2. La période maximale d’une suite

de degré d sur Fq est l = qd − 1, et il existe de telles suites, obte-
nues en prenant pour polynôme annulateur le minimal d’un élément
générateur de F×
qd
.

Un tel polynôme est dit primitif. De manière équivalente, ce sont les

φ ( q d −1)
facteurs irréductibles de Φqd −1 ( X ) sur Fq , il y en a d .

On construit une suite de période 63 d’une des deux manières

suivantes :

Algorithme 4.3.1 code gp

u = ffgen([2,6],'u) ∖∖ générateur algébrique, ie F64 = F2[u]
a = ffprimroot(u) ∖∖ élément d'ordre 63
p = minpoly(a)

ou bien

Algorithme 4.3.2 code gp

f = factormod(polcyclo(63),2) ∖∖ factorisation
p = f[1,1] ∖∖ premier facteur

Algorithme 4.3.3 code gp

linrec([1,0,1,0,1,0],x^6+x+1,70)

4.4 Calcul des termes

Pour calculer directement le n-ième terme de la suite, on peut

utiliser l’exponentiation rapide. En effet, si le polynôme m( x )
annule la suite (un ),

un = x n .u0 = ( x n mod m( x )).u0

24
4.5. Algorithme de résolution

4.5 Algorithme de résolution

4.5.1 Système linéaire

Si l’on connaı̂t 2d termes d’une suite de degré d, on retrouve un

polynôme annulateur en écrivant le système d × d vérifié par
ses coefficients.

Algorithme 4.5.1 code gp

sys lin(u,d) = {
my(m=matrix(d,d));
for(i=1,d,for(j=1,i,
m[j,i-j+1]=u[i];
m[d-j+1,d-i+j] = u[2*d-i];
));m;
}

Algorithme 4.5.2 code gp

sys lin(['u1,'u2,'u3,'u4,'u5,'u6,'u7],4)

Algorithme 4.5.3 code gp

u = [2,3,5,7,11,13,17,19,23,29];
s = sys lin(u,5);
Polrev(matsolve(s,-Col(u[6..10])))+x^5

Remarque 4.5.2. Il y a une solution si la suite est bien de

degré d. Et dans ce cas il ne peut y en avoir plusieurs sinon
la différence des deux polynômes obtenus serait un annulateur
de degré inférieur, de sorte que le système est bien inversible.
En revanche si la suite est de degré inférieur le système peut
ne pas être inversible, dans ce cas on peut résoudre en degré
inférieur, ou mieux, considérer le polynôme non nul de plus
petit degré dans le noyau du système homogène d’inconnues
a0 , . . . a d .

25
Chapitre 4. Suites récurrentes linéaires

4.5.3 Approximants de Padé

On peut faire plus efficace que le système linéaire en écrivant

le problème différemment.
Soit (un ) une suite récurrente linéaire, on construit la série for-
melle
g( x ) = ∑ un x n .
n

Soit P( x ) = ∑i ci xi un annuleur de (un ). On exprime l’annula-

tion de la récurrence en terme de produit de séries formelle via
le polynôme réciproque

P̃( x ) = x d P(1/x ) = ∑ ci x n −i .
i

On a alors

P̃( x )S( x ) = P̃( x )Sd ( x ) = r ( x )

où r ( x ) est un polynôme de degré inférieur ou égal à d − 1.

Réciproquement, la théorie des approximants de Padé affirme
que pour tout couple m, n, et toute série g( x ) telle que g(0) ̸= 0,
il existe une unique fraction rationnelle

r(x)
≡ g( x ) mod x m+n+1
v( x )
avec degv ≤ m et degr ≤ n.
Il suffit de considérer le système du résultant.
En outre, déterminer cette solution peut se faire en résolvant
un système linéaire (en complexité (n + m)3 ), ou bien via l’al-
gorithme d’Euclide étendu en complexité quadratique.
Dans le cas qui nous intéresse, si (un ) est une suite récurrente
linéaire d’ordre d, le théorème affirme que l’approximant de
Padé de niveau (d − 1, d) de g( x ) mod x2d est égal au couple
(r ( x ), P̃( x )).

26
4.5. Algorithme de résolution

Algorithme 4.5.4 code gp

minimal(u,d) = {
my(x='x);
g = sum(k=0,2*d-1,u[k+1]*x^k)+O(x^(2*d));
rv = bestapprPade(g,d);
polrecip(denominator(rv));
}

Algorithme 4.5.5 code gp

minimal(linrec([1,1],x^2-x-1,4),2)

Théorème 4.5.4. Il existe deux polynômes v, r de degrés inférieurs

à d et d − 1 tels que
r
≡ g( x )
v

27
Chapitre 4. Suites récurrentes linéaires

28
CHAPITRE 5
Algorithmes

5.1 Complexité des opérations

élémentaires

Soit N un entier. On peut représenter sa valeur sur n =

⌊log2 ( N )⌋ + 1 bits, on dit que N est de taille n. Ceci est valable
pour toute base :
Proposition 5.1.1. Soit b ≥ 2 un entier. Alors pour tout N ≥ 0, il
existe une unique suite finie d0 , . . . dn ∈ {0, b − 1}n−1 × {1, b − 1}
telle que
n
N= ∑ di bi .
i =0

De plus, n = logb ( N ) et l’on obtient les di par divisions eucli-
diennes successives.

Sans parallélisme, la complexité minimale de tout algorithme

sur un entier de taille n est n. Le seul fait de stocker ou de lire
l’entier prend ce temps. Une opération élémentaire quand on
travaille sur les entiers est une modification d’un bit.
Soit P( x ) ∈ A[ x ] un polynôme de degré n à coefficients dans
un anneau A. On peut représenter P à l’aide de n + 1 coeffi-
cients dans A, ont dit que P est de taille n sur A. Une opération

29
Chapitre 5. Algorithmes

élémentaire relativement à A[ X ] est une opération +, −, × de

A.
On mesure la complexité d’un algorithme en nombre
d’opérations élémentaires.
Définition 5.1.2. Soit x un objet de taille n. Un algorithme est dit :
— polynomial s’il nécessite O(nk ) opérations élémentaires,
pour un certain k ≥ 1.
— exponentiel s’il nécessite O(eλn ) opérations élémentaires,
pour un certain λ > 0.
— sous-exponentiel d’exposant 0 < α < 1 s’il nécessite
α log(n)1−α
O(ecn

opérations élémentaires, pour une certaine constante c > 0.

Proposition 5.1.3. Soient des objects de tailles n1 et n2 avec
n1 , n2 ≤ n. On a les complexités suivantes :
— A(n) : addition dans Z≤2n ou K≤n [ x ]
— O(n) (≪linéaire≫)
— M(n) : multiplication dans Z≤2n ou K≤n [ x ]
— algorithme naı̈f O(n2 ) (≪quadratique≫) (pour des objets
de taille n1 et n2 , vaut O(n1 n2 )).
— décomposition de Karatsuba O(n1.58 )
— algorithme de Shönhage-Strassen (FFT)
O(n log(n) log log(n)2 ) (≪quasi-linéaire≫)
— algorithme Harvey-VanDerHoeven (FFT) O(n log(n))
[?].
— multiplication dans Mn (K)
— algorithme naı̈f O(n3 )
— décomposition de Strassen O(n2.81 )
Remarque 5.1.4. Une étude plus fine de la croissance des co-
efficients (qui dépend de la suite d’opérations réalisées) est
nécessaire pour calculer la complexité binaire des opérations
sur Z[ X ].

30
5.2. Exponentiation rapide

5.2 Exponentiation rapide

Le calcul de x n dans un groupe G se fait de manière naı̈ve en

n − 1 multiplications dans G.
On peut réduire ce nombre à 2 log2 (n) opérations.
Pour développer cette idée, décomposons n en base deux

n = e0 + e1 2 + e2 4 + . . . e k −1 2k −1 + 2k

on peut écrire
i
a n = a ∑ ei 2
k
= a e0 × ( a 2 ) e1 × . . . ( a 2 ) e k
2 2 2
= a e0 a e1 . . . a e k . . . .

Dans les deux dernières lignes, l’expression ne fait plus in-

tervenir que k carrés et au plus k + 1 multiplications, avec
k = ⌊log2 (n)⌋ (plus précisément, k carrés et un nombre de mul-
tiplications égal au nombre de 1 dans l’écriture binaire de n).
Exemple 5.2.1. Calcul des trois derniers chiffres de 3n en base
10.
— méthode naı̈ve, produit dans Z

n −1
∑ O ( k ) = O ( n2 )
k =1

— exponentiation rapide dans Z

⌊log2 (n)⌋
∑ M(2k ) = O(n log(n))
k =0

— exponentiation rapide dans Z/1000Z

log(n) M(1) = O(log n)

31
Chapitre 5. Algorithmes

5.2.2 Application : ordre d’un élément

Proposition 5.2.3. Soit x un élément d’un groupe, et soit n > 0.

Alors x est d’ordre n si et seulement si
— xn = 1
— ∀ p | n, p premier, x n/p ̸= 1.
Exemple 5.2.4. On détermine un générateur de F×
q en vérifiant
que son ordre est l’ordre attendu.
Exemple 5.2.5. Avec un ordinateur, exhiber un générateur de
×
F256 .

5.2.6 Application : suites récurrentes

Pour calculer le n-ième terme de la suite de Fibonacci, ou plus

généralement d’une suite récurrente, on écrit

1 1
( f n +1 , f n ) = ( f n , f n −1 )
1 0

soit pour n ≥ 1

( f n , f n−1 ) = (1, 1) An−1

Le calcul se fait en O(log(n) étapes au lieu de O(n).

Avec la même idée, mais un formalisme différent, on détermine
le nombre f n en calculant

x n .( f 0 , f 1 , . . . ) = ( x n mod x2 − x − 1).( f 0 , f 1 , . . . )

soit

Algorithme 5.2.1 code gp

f(n) = polcoeff(lift(Mod(x,x^2-x-1)^n*(1+x)),0)

32
5.3. Algorithme d’Euclide

5.3 Algorithme d’Euclide

On note R un anneau euclidien, qui sera dans ce cours Z ou [ x ].

Proposition 5.3.1. Soient a, b ∈ Z, on définit r0 , r1 = a, b et pour
k ≥ 1 tel que rk > 0 on définit rk+1 par la division euclidienne

rk−1 = qk rk + rk+1 , où 0 ≤ rk+1 < rk (5.1)

Alors il existe k tel que rk+1 = 0, auquel cas rk = pgcd( a, b).

Démonstration. D’une part pgcd(rk−1 , rk ) = pgcd(rk , rk+1 ),

d’autre part rk est strictement décroissant dans N, d’où la ter-
minaison.

Si l’on veut obtenir une relation de Bézout au + bv = d il est

commode d’introduire la famille de relations auk + bvk = rk où
par linéarité uk et vk obéissent à la récurrence donnée par (5.1)
     
u k +1 u k −1 uk
 v k +1  =  v k −1  − q k  v k  (5.2)
r k +1 r k −1 rk

Exemple 5.3.2.
Calculons une relation de Bezout entre 213 − 1 et
28 − 1.
On écrit le tableau suivant, où l’on passe d’une ligne
à la suivante avec (5.2)

33
Chapitre 5. Algorithmes

k qk rk uk vk
0 213 − 1 0
1
1 25 28 − 0 1
1
2 23 25 − 1 −25
1
3 22 23 − −23 1 + 28
1
4 21 22 − 1 + 25 −25 − 22 − 210
1
5 1 −23 − 2 − 26 1 + 28 + 26 + 23 +
211

Soit la relation (en base 2)

1 = −1001010 × 1111111111111 + 100101001001 × 11111111

qui reste valable en base 10.

Proposition 5.3.3. Soient a > b > 0. Le nombre d’itérations de
l’algorithme d’Euclide (étendu) vérifie

k ≤ logφ (b) + 1

où φ est le nombre d’or

√
5+1
φ= ≈ 1.618.
2

Démonstration. Cela correspond à l’étude du pire cas qk = 1,

donné par la suite de Fibonacci f n+1 = f n + f n−1 .
Notons en effet R j = rk− j pour −1 ≤ j ≤ k. Alors on a R−1 = 0,
R0 ≥ 1 et pour tout j, R j+1 = qk− j R j + R j−1 ≥ R j + R j−1 , donc
par récurrence R j ≥ f j pour tout j. En particulier, b = r1 =
R k −1 ≥ f k −1 .
φk+1 −(1−φ)k+1
Or l’expression exacte f k = 2φ−1 donne f k ≥ φn .

34
5.3. Algorithme d’Euclide

On en déduit que k − 1 ≤ logφ (b).

Proposition 5.3.4. La complexité de l’algorithme d’Euclide est de

O(log( a) log(b) opérations.
Proposition 5.3.5. Soient a, b ∈ A[ x ], avec deg( a) > deg(b).
L’algorithme d’Euclide nécessite O((1 + deg( a))(1 + deg(b))
opérations +, ×, / dans A.

Démonstration. La suite des degrés est strictement

décroissante, donc l’algorithme s’arrête en moins de deg(b)
itérations, et chaque itération fait intervenir des polynômes de
degré inférieurs à deg( a).

Remarque 5.3.6. cet énoncé ne rend pas compte de la com-

plexité réelle dans Z[ X ] ou Q[ X ], où a lieu une explosion des
coefficients.

5.3.7 Applications

Inverse modulaire :
— calculer l’inverse de 7 modulo 103
— calculer l’inverse de a+1 dans F3 [ a]/a3 − a − 1.
Lemme chinois, voir ci-dessous.

5.3.8 Versions rapides

Une stratégie diviser pour régner appliquée à l’algorithme

d’Euclide permet de passer à une complexité quasi linéaire :
Proposition 5.3.9. On peut calculer le pgcd de deux entiers de taille
n en O( M(n) log(n)) opérations.
On peut calculer le pgcd de deux polynômes de degré n en
O( M(n) log(n)) opérations de A.

35
Chapitre 5. Algorithmes

Démonstration. Admis, algorithme de Lehmer pour les entiers,

de Knuth, Shönhage, . . . en général.

5.4 Lemme chinois

Proposition 5.4.1. Soit R un anneau euclidien, et m1 , . . . mr des

éléments de R deux à deux premiers entre eux.
Alors en notant m = ∏ mi , on a un isomorphisme d’anneaux

∏ R/⟨mi ⟩

R/⟨m⟩ →
π:
x ↦→ ( x mod mi )i

Proposition 5.4.2. Pour 1 ≤ i ≤ r, on pose Mi = ∏ j̸=i m j et on

calcule une relation de Bézout Mi ui + mi vi = 1. Alors l’application

∏ R/⟨mi ⟩ →

R/⟨m⟩
ρ:
x 1 , . . . x m ↦ → ∑ x i u i Mi

est l’inverse de π.

Démonstration. On a bien π ∘ ρ( x1 , . . . xr ) = ( x1 , . . . xr ) en
écrivant M j ≡ 0 mod mi pour j ̸= i et ui Mi ≡ 1 mod mi sinon.

Naı̈vement, les algorithmes de calcul de réduction modulaire

ou de reste chinois sont en O(n2 ). On peut toutefois faire
mieux :
Théorème 5.4.3. Si ∑ |mi | ≤ n, on peut calculer des images π ( x )
ou ρ( x1 , . . . xr ) en O( M (n) log(n) opérations élémentaires relative-
ment à R.

36
5.5. Méthode de Newton

5.5 Méthode de Newton

5.5.1 Version classique

En analyse, la méthode de Newton consiste à approcher

numériquement la solution d’une équation f ( x ) = 0 en la
linéarisant au voisinage d’un point x0 non critique :

f ( x0 ) + f ′ ( x0 )( x − x0 ) = 0

ce qui fournit une approximation

x 1 = x 0 − f ′ ( x 0 ) −1 f ( x 0 ).

On recommence en réinjectant.
S’il existe une solution f ( x ) = 0 telle que f ′ ( x ) ̸= 0, on montre
que le schéma converge pour tout x0 appartenant à un certain
voisinage de x, et que la convergence est quadratique : il existe
n
C > 1 tel que | xn − x | ≤ C −2 , de sorte que le nombre de
chiffres corrects double à chaque itération.
Exemple 5.5.2. Pour calculer la racine carrée d’un réel a > 0,
on écrit cette racine comme solution de l’équation f ( x ) = 0
pour f ( x ) = x2 − a. Ceci donne l’itération xn+1 = xn +2a/xn . Une
petite étude analytique (≪suites de√la forme xn+1 = f ( xn )≫)
montre que la convergence xn → a a lieu pour toute valeur
x0 ≥ 0.
Exemple 5.5.3. Une application plus surprenante : la méthode
de Newton permet de calculer l’inverse d’un réel a ∈ R× sans
effectuer de division. Exercice.
Grâce à la méthode de Newton, la complexité du calcul
d’une racine ou de l’inverse est de O( M(n)), où M(n) est la
complexité de la multiplication. On devrait avoir un facteur
supplémentaire log(n) pour compter le nombre d’étapes : ce
n’est pas le cas si on effectue chaque étape avec une précision
qui double pour atteindre la précision du résultat, la com-
plexité est alors ∑k O( M (n/2k )) = O( M (n)).

37
Chapitre 5. Algorithmes

Exemple 5.5.4. Les algorithmes de calcul de racine ou d’inverse

décrits dans R permettent de calculer des racines entières ou
des divisions euclidiennes en O(n), il suffit d’effectuer le calcul
jusqu’à une précision suffisante pour identifier la partie entière
du résultat.

5.5.5 Lemme de Hensel

Ce schéma se transpose parfaitement au monde de l’algèbre,

dans lequel les notions de convergence sont plus diverses et
plus faciles à obtenir. Quand on travaille pour une valuation
p-adique, il prend le nom de relèvement de Hensel.
Proposition 5.5.6. On considère un entier m et un polynôme
P( x ) ∈ Z[ x ] tel qu’il existe a ∈ Z vérifiant P( a) ≡ 0 mod m et
P′ ( a) ∈ (Z/mZ)* . Alors pour tout k ≥ 0, il existe ak ∈ Z tel que
k
P( ak ) ≡ 0 mod m2 .

La suite ak est donnée par a0 = a puis la récurrence

k
ak+1 = ak − P′ ( ak )−1 P( ak ) mod m2 (5.3)

Démonstration. On utilise la formule de Taylor exacte

Par récurrence, il suffit de montrer qu’avec les hypothèses, en
posant b = a − P′ ( a)−1 P( a) mod m2 , on a
— b ≡ a mod m, et donc pgcd( P′ (b), m) = 1 ;
— P(b) ≡ 0 mod m2 .
Le premier point découle de P( a) ≡ 0 mod m, le second de
la formule de Taylor P(b) = P( a) + P′ ( a)(b − a) mod m2 (car
m2 | (b − a)2 ).
On remarque que l’équation de récurrence (5.3) est écrite mo-
dulo m2 , mais qu’il suffit de calculer un inverse P′ ( a)−1 mod
m. En effet, P( a) est en facteur de P(b), l’autre terme (1 −
P(′ a)−1 P′ ( a)) n’a besoin d’être nul que modulo m.

38
5.5. Méthode de Newton

Plus généralement, on peut remplacer dans la proposition Z

par un anneau de polynômes A[ x ] et m par x n .
Proposition 5.5.7. Soit A un anneau, f ∈ A[ x, y]. Soit P ∈ A[ x ]
tel que f ( x, P( x )) ≡ 0 mod x n et pgcd( ∂P
∂y ( x, P ), x ) = 1. Alors il
existe Q ≡ P mod x n tel que f ( x, Q) ≡ 0 mod x2n .

39
Chapitre 5. Algorithmes

40
CHAPITRE 6
Résultats d’arithmétique

6.1 Théorèmes fondamentaux sur les

groupes

Proposition 6.1.1. Soit G un groupe fini d’ordre n, alors pour tout

x ∈ G, l’ordre de x divise n.

Démonstration. Démonstration élémentaire dans le cas

abélien : puisque G = xG, ∏G y = ∏G ( xy) = x n ∏G y donc
x n = 1.

Proposition 6.1.2. Soit G un groupe fini de cardinal n. Alors pour

tout diviseur premier p de n, il existe un élément d’ordre p.

Démonstration. Démonstration élémentaire dans le cas

abélien : soient x1 , . . . xk des générateurs de G, d’ordres respec-
tifs n1 , . . . nk . Alors on a un morphisme surjectif

∏ Z/ni Z → G
∏ xi i
e
( ei ) ↦ →
donc p | #G | ∏ ni , d’où p | ni pour un certain i, d’où l’élément
ni
p
xi d’ordre p.

41
Chapitre 6. Résultats d’arithmétique

Proposition 6.1.3. Soit G un groupe abélien fini, il existe d1 |

d2 · · · | dr tel que G ≃ ∏ Z/di Z.

Démonstration. Appliquer une réduction de Smith au noyau

du morphisme surjectif ci-dessus.

Proposition 6.1.4. Soit G un groupe cyclique d’ordre n, G est iso-

morphe à Z/nZ. Pour tout d | n, G possède un unique sous-groupe
d’ordre d, qui est cyclique. Les générateurs de Z/nZ sont les classes
d’entiers premiers à n.

6.1.5 Puissances

Théorème 6.1.6. Soit G un groupe de cardinal n. Alors pour k ∈

Z/nZ, l’exponentiation

G → G

ek : ,
x ↦→ xk

est bijective si et seulement si pgcd(k, n) = 1. Son inverse vaut alors

el où l = k−1 mod n.

Démonstration. L’application ne dépend que de k mod n car

mn = 1 (Lagrange). Si k est inversible, on a en effet mkl = m.
Pour la réciproque on peut utiliser le théorème de Cauchy : si
p | pgcd(k, n), alors il existe m ∈ G d’ordre p, et mk = 1 = 1k
donc ek n’est pas bijective.

Dans le cas où k n’est pas inversible, on comprend bien le noyau

Proposition 6.1.7. Soit G un groupe cyclique d’ordre n. Alors le
noyau de ek est de cardinal pgcd(k, n).

42
6.2. L’anneau Z/nZ

Démonstration. Notons d ce pgcd, n | xk ssi nd | x, donc le

noyau est nd Z/nZ ∼ Z/dZ. $kx ∖equiv 0∖bmod n ∖

6.1.8 Exponentielle et logarithme

Soit ( G, g) la donnée d’un groupe cyclique d’ordre n, muni

d’un générateur g.
Alors on appelle exponentielle et logarithme de base g les iso-
morphismes inverses l’un de l’autre

Z/nZ → G

expg :
k ↦→ gk
et
→ Z/nZ

G
logg : .
x ↦→ kt.q. x = gk

6.2 L’anneau Z/nZ

6.2.1 Structure

Proposition 6.2.2. Soit n un entier et n = ∏ pe p sa factorisation

en produit de facteurs premiers, alors on a l’isomorphisme d’anneaux

Z/nZ ≃ ∏ Z/pe p Z
Il reste à étudier la structure de (Z/pe Z)* .
Proposition 6.2.3. Soit p ≥ 3 et e ≥ 1. Alors (Z/pe Z)× est
cyclique d’ordre ( p − 1) pe−1 .
D’autre part, pour p = 2 et e ≥ 2, (Z/2e Z)× ≃ Z/2Z ×
Z/2e−2 Z.

43
Chapitre 6. Résultats d’arithmétique

Remarque 6.2.4. On ne connaı̂t pas de générateur explicite de

(Z/pZ)× , c’est même un problème ouvert (conjecture d’Ar-
tin). Toutefois il est très facile d’en déterminer en pratique en
tirant au hasard.
Ensuite, 1 + p (resp. 1 + 4) est un générateur du sous-groupe
d’ordre pe−1 (resp. 2e−2 ).

6.2.5 Propriétés

On note ϕ(n) le cardinal de (Z/nZ)* .

D’après le lemme chinois, ϕ(n) = ∏ p e | n ( p e − p e −1 ) =
n ∏ p|n (1 − 1/p).

Théorème 6.2.6. Soit n > 1 et a ∈ (Z/nZ)* . Alors a ϕ(n) ≡

1 mod n.
Lemme 6.2.7. Soit n un entier impair sans facteur carré. Alors on a
équivalence entre
— n n’est pas premier
— il existe a tq a ̸= ±1 mod n mais a2 = 1 mod n.
De plus, dans ce cas toute telle valeur de a fournit une factorisation
non triviale n = pgcd( a − 1, n) pgcd( a + 1, n).

Démonstration. Si n = pq, toute valeur a tq a = 1 mod p et

a = −1 mod q convient.
Tandis que si n = p est premier, alors ±1 sont les deux seules
racines carrées de 1.
Enfin si n | a2 − 1 = ( a − 1)( a + 1) mais que n - a − 1 et n - a + 1
alors les deux pgcd sont non triviaux.

Lemme 6.2.8. Soit n = pq un entier et m un entier tel que

∀ a, a2m = 1 mais ∃ a, am ̸= 1.

44
6.3. Résidus quadratiques

Alors

# { a, am = ±1 mod n} ≤ ϕ(n)/2

En d’autres termes, plus de la moitié des a sont tels que pgcd( am +

1, n) est un facteur strict de m.

Démonstration. Notons H = { a, am = ±1}, alors H est un

sous-groupe de (Z/nZ)× , et un sous-groupe strict car par hy-
pothèse il existe a tq am ̸= 1 mod p ou a ̸= 1 mod q, de sorte
que b tq b = a mod p et b = 1 mod q n’est pas dans H. Ainsi,
H est d’indice au moins 2.

6.3 Résidus quadratiques

6.3.1 Structure

Définition 6.3.2. On appelle résidus quadratiques modulo n les

carrés modulo n, c’est-à-dire les a ∈ Z/nZ tels qu’il existe x,
a ≡ x2 mod n.
p −1
Proposition 6.3.3. Soit p ≥ 3 un nombre premier. Il existe 2
résidu quadratiques dans (Z/pZ)* .

Démonstration. Puisque Z/pZ est un corps, on a 1 → ±1 →

p −1
F*p → (F*p )2 → 1, ce qui fait 2 résidus quadratiques non
nuls.

45
Chapitre 6. Résultats d’arithmétique

6.3.4 Reconna^ıtre les carrés

Proposition 6.3.5. Soit p premier impair et a ∈ Z. Alors on définit

le symbole de Legendre

a p −1
= a 2 mod p ∈ {−1, 0, 1}
p

et l’on a

0
 si p | a
a
= 1 si a est un carré modulo p
p 
−1 sinon


Définition 6.3.6. On étend le symbole de Legendre à tout couple

e
d’entiers a, n, avec n impair, de la manière suivante : si n = ∏ pi i ,
on pose
a ei
a
=∏ .
n i
p i

Ce symbole est multiplicatif en a, n, c’est-à-dire que pour tous

a, b, m, n on a

ab a b a a a
= et =
n n n mn m n

n

Attention : on n’a plus n carré mod m ssi m = 1. Ainsi, si n
=
a
pq et a est non-résidu quadratique modulo p et q, alors n =
(−1)(−1) = 1 mais a n’est pas résidu quadratique modulo n.
Le même exemple fonctionne modulo p2 .
Toutefois on garde l’implication a carré ⇒ na = 1.

Le calcul de na sans factorisation de n est rendu possible par

l’énoncé suivant
Théorème 6.3.7. Soient m, n ∈ Z impairs, avec pgcd(m, n) = 1.
Alors on a les formules

46
6.3. Résidus quadratiques

m −1

— −1 = (−1) 2 ;
m
2
m2 −1
— m = (−1) ;8
(m−1)(n−1)
m n

— m = (−1) .
4
n

Grâce à la réciprocité quadratique, on peut calculer des sym-

boles de Jacobi modulo de grands entiers sans avoir besoin de
les factoriser.

47
Chapitre 6. Résultats d’arithmétique

48
CHAPITRE 7
Cryptographie asymétrique

Note : Intercaler ce chapitre avec les chapitres d’algo

arithmétique qu’il motive, par exemple : RSA, primalité,
sécurité de RSA, carrés, système de Rabin, factorisation, El Ga-
mal, logarithme discret.

7.1 Principe

Chaque agent possède un couple (clef publique, clef privée) de

sorte que
— avec la clef publique, tout le monde peut chiffrer ;
— seule la clef privée peut déchiffrer un message chiffré
avec la clef publique.
Avantage pratique : un couple de clefs par agent suffit pour
toutes les communications, et non un couple par paire de cor-
respondants.
Pour mettre cela en œuvre, besoin de ≪fonctions trappes≫ : fa-
ciles à calculer mais dont on ne sait pas calculer l’inverse de
manière raisonnable à moins de disposer d’une information
supplémentaire (la trappe).
On pourrait formaliser une définition de fonction trappe (par
exemple calcul direct de complexité polynomiale, mais proba-

49
Chapitre 7. Cryptographie asymétrique

bilité négligeable de calculer l’inverse pour toute machine de

Turing sur une instance aléatoire). Dans tous les cas on ne sait
pas démontrer l’existence d’une telle fonction, on en est réduit
à choisir des problèmes réputés durs, comme la factorisation.
Quelques exemples de problèmes mathématiques donnant
naissance à des fonctions trappes :

crypto- cadre problème problème informa-

système simple dur tion
RSA (Z/nZ)× , puis- puissance φ(n)
n = pq sance inverse
Rabin (Z/nZ)× , carré racine p, q
n = pq
EL F×p, exponen- loga- (pas
Gamal E (F p ). . . tiation rithme besoin)
NTRU, réseau combi- vecteur bonne
LWE Zn ⊂ Rn naisons court base
Mac code cor- codage décodage structure
Eliece recteur cachée

7.2 Le chiffrement RSA

7.2.1 Principe

1. Choisir p, q deux grands nombres premiers aléatoires.

2. Poser n = pq
3. Calculer ϕ(n) = ( p − 1)(q − 1)
4. Choisir e ∈ (Z/φ(n)Z)× (en général 216 + 1 = 65537
convient)
5. Calculer d = e−1 mod ϕ(n).

Alors la clef publique est constituée du couple (n, e), et la clef

privée du couple (n, d).

50
7.2. Le chiffrement RSA

Sur M = C = (Z/nZ)* , on a une application de chiffrement

ee : m ↦→ me mod n

et une application de déchiffrement

ed : c ↦→ cd mod n

Remarque 7.2.2. On reviendra sur l’importance d’avoir de

≪grands≫ premiers ≪aléatoires≫.

7.2.3 Sécurité

Toute la sécurité de RSA est fondée sur le fait que connaissant

n, on ne sache pas calculer ϕ(n), ou de manière équivalente
factoriser n.
On considère N = {n = pq, p < q < 2p}.
Définition 7.2.4. On définit la suite de problèmes
— 𝒫 RSA : étant donné (n, e) et c ∈ (Z/nZ)* , déterminer m ∈
(Z/nZ)* tel que c = me .
— 𝒫 RSA−d : étant donné (n, e), trouver d tel que ed = 1 mod
φ ( n ).
— 𝒫 RSA− phi : étant donné n, calculer ϕ(n).
— 𝒫 f actor : étant donné n, factoriser n = p × q.

Pour tous problèmes 𝒫 A , 𝒫 B , on note 𝒫 A ≤ 𝒫 B s’il existe un

algorithme polynomial qui permet de ramener la résolution
d’une instance du problème A à un nombre polynomial de
résolutions d’instances problème B. Et on note 𝒫 A = 𝒫 B si
𝒫 A ≤ 𝒫 B et 𝒫 B ≤ 𝒫 A .
Proposition 7.2.5. On a

𝒫 RSA ≤ 𝒫 RSA−d = 𝒫 RSA− phi = 𝒫 f actor

Démonstration. On a d’après la description du système

𝒫 RSA ≤ 𝒫 RSA−d ≤ 𝒫 RSA− phi ≤ 𝒫 f actor .

51
Chapitre 7. Cryptographie asymétrique

Il suffit donc de montrer que 𝒫 f actor ≤ 𝒫 RSA−d .

Soit donc un couple (n, e) fixé. On récupère via 𝒫 RSA−d un ex-
posant d tel que ed = 1 mod ϕ(n), de sorte que ∀ a ∈ Z/nZ,
aed−1 = 1.
On va appliquer le lemme de factorisation, il suffit de
déterminer un exposant m convenable.
Or puisque p, q sont impairs, e et d sont impairs et on écrit ed −
1 = 2r ` , 2 - ` .
Puisque (−1)` = −1 il existe un exposant k pour lequel l’expo-
sant m = 2k ` vérifie
— ∃ a, am = −1
— ∀ a, a2m = 1
Ainsi, il existe un entier m de la forme (ed − 1)/2i tel que pour
la moitié des a mod n, pgcd( am + 1, n) est un facteur de n.
En essayant plusieurs valeurs, on obtient un algorithme (pro-
babiliste) de factorisation de n.

Remarque 7.2.6. Le fait qu’on ait une inégalité a priori stricte

𝒫 RSA < 𝒫 f actor est plutôt une bonne nouvelle : l’accès au
déchiffrement ne permet pas de factoriser n. Sinon RSA serait
vulnérable aux attaques chiffré choisi.

7.2.7 Mise en œuvre

Il existe beaucoup d’attaques sur la mise en œuvre de RSA, qui

doit obéir à des règles strictes.
Mentionnons un aspect essentiel : p et q doivent être vraiment
aléatoires. On a de nombreux exemples de clefs vulnérables à
cause de génération biaisée. Par exemple :
— des nombres premiers obtenus via nextprime(random)
où random est issu d’un générateur pseudo-aléatoire de
bibliothèque standard.

52
7.3. Cryptosystème de Rabin

— en 2012, diverses équipes se sont amusées à calculer des

pgcd(n, n′ ) de diverses clefs publiques collectées sur in-
ternet [?], pour constater que 0.2% des clefs reposaient
sur des nombres premiers utilisés plusieurs fois. Ce qui
ne devrait évidemment jamais arriver s’ils étaient choi-
sis avec un bon aléa.
Il faut prendre garde à beaucoup de choses, en particulier
— ne jamais chiffrer directement un message donné
mais toujours ajouter un padding aléatoire (plus
généralement, un cryptosystème à clef publique doit
toujours chiffrer de manière randomisée).
— avoir une implantation sécurisée : si on calcule l’ex-
ponentiation rapide de manière naturelle, on fait une
multiplication de plus à chaque bit non nul de l’expo-
sant ; mettre en œuvre des techniques d’observation de
la consommation électrique ou des rayonnements émis
pour deviner des bits de l’exposant de déchiffrement
(side-channel attack) est plus simple que factoriser n.

7.3 Cryptosystème de Rabin

Lemme 7.3.1. Soit p ≡ 1 mod 4 un nombre premier, et a un carré

p +1
modulo p. Alors a 4 mod p est une racine carrée de a modulo p.
p −1
Démonstration. On fait le calcul en isolant a 2 = 1.
On peut aussi remarquer que le sous-groupe des carrés est de
p −1
cardinal impair 2 , donc la puissance x ↦→ x2 y est inversible,
p +1
son inverse étant la puissance x ↦→ x 4 .

53
Chapitre 7. Cryptographie asymétrique

7.3.2 Principe

On choisit p, q deux grands premiers congrus à 3 mod 4, on

pose n = pq.
Le chiffrement est l’application carré m ↦→ m2 mod n.
On déchiffre en calculant une racine carrée modulo p et q, via
le lemme chinois.
En l’état ce n’est pas un cryptosystème, puisque le chiffrement
n’est pas injectif : un carré possède 4 racines carrées modulo
n = pq.
Ce peut être corrigé en rajoutant deux bits d’information per-
mettant de choisir la bonne racine :
Proposition 7.3.3. Soit n = pq impair, l’application
m
m ↦ → ( m2 , , m mod 2)
n
est bijective de Z/nZ)× sur {carrés} × {±1} × {0, 1}.

Démonstration. Voir feuille d’exercices.

p +1
Soit (c, s, b) un chiffré. Notons m p = c 4 mod p et mq =
q +1
c 4 mod q, ce sont des carrés modulo p et q.
Alors les 4 racines carrées de c sont

m

(m mod p, m mod q) n m mod 2
(m p , mq ) 1 e1
(−m p , −mq ) 1 1 − e1
(−m p , mq ) −1 e2
(m p , mq ) −1 1 − e2

la bonne est donc déterminée par les deux bits s ∈ {±1} et

b ∈ {0, 1}.

54
7.3. Cryptosystème de Rabin

7.3.4 Mise en œuvre

1. On choisit p, q deux premiers congrus à 3 mod 4, on

pose n = pq.
2. La clef publique est n.
3. La clef privée est le couple ( p, q).
4. Le chiffrement est l’application m ↦→ (m2 mod
n, m

n , m mod 2 ) .
5. Pour déchiffrer, on calcule des racines carrée modulo p
et q, on recompose via le lemme chinois en choisissant
parmi les 4 racines celle qui a le bon symbole de Jacobi
et la bonne parité.

7.3.5 Sécurité

On définit les problèmes

— 𝒫rabin : avoir accès à la fonction de déchiffrement
(m2 , mn , m mod 2) ↦→ m.
— 𝒫sqrt : étant donné n et a un carré modulo n, en
déterminer une racine carrée.
Proposition 7.3.6. 𝒫 f actor = 𝒫rabin = 𝒫sqrt

Démonstration. Si l’on a accès au déchiffrement, pour tout

message m, le déchiffrement de (m2 , − m

n , m mod 2) est un
m′ tel que m′ ≡ ±m mod p et m′ ≡ ±m mod q, de sorte que
pgcd(m − m′ , n) vaut p ou q.
Si l’on n’a accès qu’à une fonction de racine carrée, la même
technique devient probabiliste : il y a deux chances sur quatre
qu’une racine m′ de m2 soit distincte de ±m, ce qui fournit une
factorisation.

Cela montre la force du cryptosystème, mais aussi sa faiblesse

puisqu’il est vulnérable aux attaques à chiffré choisi. On peut

55
Chapitre 7. Cryptographie asymétrique

corriger ce point en restreignant l’espace des messages admis-

sibles : par exemple en ne chiffrant que des concaténations bi-
naires m|m.

7.4 El Gamal

7.4.1 Principe

On choisit un groupe cyclique G d’ordre n donné par un

générateur g. Par exemple, G = F*q d’ordre q − 1.
Alice tire aléatoirement a ∈ Z/nZ et calcule A = g a . Sa clef
secrète est a, sa clef publique A.
Le chiffrement procède comme suit : pour tout message m, on
tire un exposant r aléatoirement dans Z/nZ, et on transmet le
chiffré

c = ( gr , mAr ) = ( R, M )

Pour déchiffrer un message ( R, M ) de la forme ci-dessus, on

calcule

MR− a = m( g a )r ( gr )− a = m.

7.4.2 Sécurité

Soit G = ⟨ g⟩ un groupe cyclique. On définit les problèmes

— 𝒫 ElGamal : étant donnés ( g a , gr ) ∈ G2 , calculer g ar ;
— 𝒫 Log : étant donné g a , calculer a.
Le problème El Gamal est équivalent à savoir déchiffrer les
messages (sans connaissance de la clef privée), le problème du
Log discret est équivalent à retrouver la clef privée.
On a en particulier

𝒫 ElGamal ≤ 𝒫 Log

56
7.4. El Gamal

On ne sait rien faire dans l’autre sens.

7.4.3 Groupes utilisés

— F×p , pour p premier. On choisit en pratique un nombre

premier p de Sophie Germain, c’est-à-dire tel que p =
2q + 1 pour q premier, de sorte que l’ordre p − 1 se fac-
torise le moins possible (cf. décomposition en restes chi-
nois).
— F× e
q pour q = p . En pratique il faut éviter les petites
valeurs de p, car on a de bons algorithmes de calcul de
logarithme discret dans ce cadre.
— E(F p ) où E est une courbe elliptique d’équation y2 =
x3 + ax + b (pour des coefficients a, b ∈ F p tels que p -
4a3 + 27q2 ), c’est-à-dire l’ensemble
n o
E(F p ) = ( x, y), y2 = x3 + ax + b ∪ {∞}

muni de la loi d’addition ≪corde et tangente≫ : si P =

( x P , y P ) et Q = ( xQ , yQ ) sont deux points, la droite pas-
sant par P et Q intersecte la courbe en un troisième point
R = ( x R , y R ). On pose P ⊕ Q = ⊖ R = ( x R , −y R ).
Alors ( E(F p ), ⊕) est un groupe abélien d’élément neutre
∞.
En outre,
√ √
— p + 1 − 2 p ≤ #E(F p ) ≤ p + 1 + 2 p (Théorème de
Hasse)
— pour tout p, et pour tout n dans l’intervalle ci-dessus,
il existe des courbes elliptiques de cardinal n. En par-
ticulier il existe des courbes de cardinal un nombre
premier (pour lesquelles E(F p ) est cyclique et ro-
buste du point de vue de la décomposition en restes
chinois)

57
Chapitre 7. Cryptographie asymétrique

58
CHAPITRE 8
Composition, primalité

Soit n ∈ N. Le théorème fondamental de l’arithmétique n’étant

pas effectif, on peut se poser trois questions de difficulté algo-
rithmique croissante :
— n composé ? tests de composition
— n premier ? preuves de primalité
— factorisation de n ? méthodes de factorisation
Répondre oui à la première question est facile et l’on peut le
faire pour des entiers de milliards de chiffres, via les tests de
composition.
Si l’on n’arrive pas à montrer qu’un entier est composé,
démontrer rigoureusement qu’il est premier est possible en
temps polynomial (AKS, mais ce n’est pas le plus efficace). En
pratique cela marche pour des entiers ayant jusqu’à quelques
milliers de chiffres.
Enfin, même si l’on sait qu’un entier est composé, on ne sait
pas en déterminer un facteur efficacement. Les meilleurs algo-
rithmes sont sous-exponentiels, et en pratique
— on peut factoriser en quelques millisecondes des entiers
de moins de 30 chiffres
— pour 100 chiffres, il faut quelques heures
— le record de factorisation est le module RSA-250, soit 829
bits.
— dix ans plus tôt, la mise au point du programme de fac-
torisation Cado-nfs lors de la factorisation de RSA-768
(768 bits pour 230 chiffres) avait mobilisé une équipe

59
Chapitre 8. Composition, primalité

d’experts pendant trois ans, et des centaines de ma-

chines.

8.1 Résultats

Théorème 8.1.1. Soit π ( x ) = # { p ≤ x, p premier}. Alors π ( x ) ∼

x
log x .

8.2 Tests de composition

Le but est de trouver un comportement qui caractérise les

nombres premiers, et qui soit facile à tester.

8.2.1 Test de Fermat

Par exemple le petit théorème de Fermat

Proposition 8.2.2. Soit n ∈ N. S’il existe a ∈ (Z/nZ)* tel que
an−1 ̸= 1 mod n, alors n n’est pas premier.

Ce critère est très efficace en pratique : en tirant un résidu a au

hasard, cela permet de démontrer la non-primalité de la plu-
part des nombres.
Par exemple, parmi les 100 000 premiers entiers impairs de 1024
bits, tous ceux qui ne sont pas premiers échouent au test de Fer-
mat pour a = 2 ou a = 3 (et l’on isole 292 nombres premiers).

Algorithme 8.2.1 pseudopremiers de Fermat

n = 1<<1023 + 1; c = 0;
for(i=1,10^5,if(Mod(2,n)^n==2,c++;if(!ispseudoprime(n),print(n)));n+=2);c

Toutefois, l’énoncé de Fermat ne caractérise pas les nombres

premiers.

60
8.2. Tests de composition

Définition 8.2.3. On appelle nombres de Carmichael les entiers n

non premiers tels que ∀ a ∈ (Z/nZ)* , an−1 ≡ 1 mod n.

Ces nombres existent, par exemple : 561, 1729.

Algorithme 8.2.2 nombres de Carmichael

{ for(n=2,2000,
if(!isprime(n)&&sum(a=1,n-1,Mod(a,n)^n==a)==n-1,
print(n)) ) }

Infinité démontrée en 1994 (Granville).

Théorème 8.2.4. Soit C ( X ) le nombre de nombres de Carmichaël
inférieurs à X. Pour X > 104 , on a
3
( X )/ log2 ( X )
X 1/3 < X < Xe−2 log(X ) log

On sait même les caractériser complètement :

e
Proposition 8.2.5. Soit n un entier non premier, et n = ∏i pi i sa
factorisation en produit de facteurs premiers.
Alors n est de Carmichael si et seulement si pour tout i, ei = 1 et
pi − 1 | n − 1.

Démonstration. Supposons d’abord que n vérifie le critère,

alors pour tout a, an−1 = 1 mod pi donc n est de Carmichael.
Réciproquement, si n est de Carmichael alors modulo chaque
e e
pi i on doit avoir an−1 = 1 mod pi i pour tout a, en particulier
e e
pour a un générateur de (Z/pi i Z)× , donc d’ordre ϕ( pi i ). Cela
e e −1
impose ϕ( pi i ) = ( pi − 1) pi i | n − 1. Or pi | n donc pi - n − 1,
ce qui impose ei = 1. On a bien la condition cherchée.

En exercice, montrer
— que si n est de Carmichael, n a au moins 3 facteurs pre-
miers

61
Chapitre 8. Composition, primalité

— que si n n’est ni premier ni de Carmichael, alors la pro-

portion de a tq an = a mod n est inférieure à 1/2.
Soit n un entier impair, et supposons que pour k valeurs
aléatoires a1 , . . . ak on ait ain−1 = 1 mod n. Alors
— soit n est premier
— soit n est de Carmichael, mais la probabilité est
inférieure à 2−300 pour n de 512 bits (à 2−588 pour n de
1024 bits)
— soit chaque ai est dans H, mais la probabilité est
inférieure à 2−k .
Ainsi, le test de Fermat est bien suffisant pour trouver de
grands nombres premiers en pratique, et donne une garantie
parfaitement satisfaisante.

8.2.6 Test de Miller-Rabin

Néanmoins on peut affiner à peu de frais le critère et faire dis-

paraı̂tre les exceptions de type Carmichael, en utilisant
Lemme 8.2.7. Si n est premier et a2m = 1, alors am ∈ {±1}.
Théorème 8.2.8. Soit n un nombre premier impair, on écrit n − 1 =
2r m, 2 - m. Alors pour tout a ∈ (Z/nZ)* ,
(
soit am ≡ 1 mod n
i (8.1)
soit ∃0 ≤ i ≤ k − 1, a2 m ≡ −1 mod n

Démonstration. si n est premier, on a an−1 = 1, puis par

i +1 i
récurrence descendante pour i ≥ 0, si a2 m = 1, alors a2 m =
±1 (racines carrées de 1 dans un corps).

On a à présent une réciproque partielle

Théorème 8.2.9. Si n > 9 impair n’est pas premier, alors

ϕ(n)
#{ a ∈ (Z/nZ)* , a vérifie :eq :‘miller‘} ≤ .
4

62
8.2. Tests de composition

Démonstration. Soit n non premier, et S l’ensemble cherché. On

e
écrit n = ∏il=1 pi i , et on pose q = 2i m, où i est le plus grand ex-
q
posant tel qu’il existe a0 , a0 = −1 mod n. Un tel i existe puisque
(−1)m = −1
On écrit alors la suite de sous-groupes

G4 ⊂ G3 ⊂ G2 ⊂ G1 ⊂
e
{ aq = 1[n]} ⊂ { aq = ±1[n]} ⊂ a q = ±1[ p i i ] ⊂ a n −1 = 1 [ n ] ⊂

et l’on a
— par définition de q, S ⊂ G3 ;
— [ G3 : G4 ] = 2 car on a une partition G3 = G4 ∪ a0 G4 ;
— [ G2 : G4 ] = 2l d’après le lemme chinois, car la même
partition vaut sur chaque premier ;
— [ G0 : G1 ] ≥ 2 dès que n n’est pas de Carmichael.
Ainsi, si l ≥ 3 c’est bon. Si l = 2 c’est bon car n ne peut être de
Carmichael, enfin si l = 1 les éléments de G1 sont ceux d’ordre
divisant p − 1 (car p est premier à pe − 1), donc [ G0 : G1 ] =
( p −1 ) p e −1
p −1 = pe−1 qui est supérieur à 4 si p ≥ 5 ou e ≥ 3.

D’où un test de composition

Proposition 8.2.10. Si n est tel que (8.1) est vérifiée pour k valeurs
a aléatoires, alors la probabilité que n soit non premier est inférieure
à 4−k .

Ce résultat est extrèmement pessimiste : pour un entier n non

premier aléatoire, la proportion de mauvais témoins est en
général beaucoup plus faible, voire nulle. Si l’on fait une étude
en moyenne sur les entiers d’une certaine taille on se rend
compte que même avec un seul test, la probabilité de ne pas
avoir détecté un entier composé est extrèmement faible. Le
NIST recommande de ne faire que 4 tests de Miller-Rabin pour
des entiers entre 512 et 1024 bits, et même seulement 3 au-delà
(la proportion de couples (n, a) passant le test décroı̂t rapide-
ment).

63
Chapitre 8. Composition, primalité

Algorithme 8.2.3 Miller-Rabin

miller(n,a=0) = {
if(a,a=Mod(a,n),a=random(Mod(1,n)));
k = valuation(n-1,2); m=(n-1) >> k;
a = a^m; if( a == 1, return(1));
for(j=0,k,
if(a==-1, return(1));
a = a^2
);
return(0);
}

Exemple 8.2.11. Avec n = 1729 (qui est de Carmichael), on a

n − 1 = 26 × 27. Pour a = 2, α = 2m = 645 ̸= ±1, puis α2 =
1065 ̸= −1, puis α4 = 1 ̸= −1, ainsi que toutes les puissances
ultérieures. Ainsi n n’est pas premier.
D’autre part, on obtient dans ce cas gratuitement une solution
non triviale x = 1065 de x2 − 1, donc une factorisation de n en
écrivant n = pgcd(n, x − 1) pgcd(n, x + 1) = 133 × 13 (on a
d’un côté les premiers tels que x = 1 mod p et de l’autre ceux
pour lesquels x = −1 mod p).
Exemple 8.2.12. Déterminer si l’entier suivant est premier, et
sinon le factoriser :

n = {
,→8185845834785787715500975919455614329511502614694099294667

,→ 8560866952810920232221199291120876931129919023416710799705

,→ 8608462266924211628867527238069614177979241512780491103207

,→ 6679384558425720022941343121103938057297224254397874444742
03520320009 }

64
8.3. Preuves de primalité

8.3 Preuves de primalité

8.3.1 Méthode n-1

Proposition 8.3.2. Soit n ∈ N, alors on a équivalence entre

— n est premier ;
— ϕ(n) = n − 1 ;
— ∃ a ∈ (Z/nZ)* d’ordre n − 1 ;
De plus, dans ce cas, il y a φ(n − 1) tels éléments a.

Vérifier qu’un élément est d’ordre n − 1 est aisé si l’on connaı̂t

la factorisation de n − 1.
Théorème 8.3.3. Soit n ≥ 1. On suppose qu’il existe a ∈ (Z/nZ)*
tel que

an−1 ≡ 1 mod n
(
n −1
a q ̸≡ 1 mod n pour tout q | n − 1, q premier.

Alors n est premier.

Un certificat de primalité est alors la donnée d’un tel élément a

assorti d’une factorisation de n − 1, où l’on peut récursivement
prouver la primalité de chaque facteur.
Un exemple :

[ 192383, 5, [ 2, 1, 43, 1, [ 2237, 2, [ 2, 2, 13,

,→1, 43, 1 ] ] ] ]

En posant n1 = 192383 et n2 = 2237, ce certificat correspond

65
Chapitre 8. Composition, primalité

aux affirmations

n1 − 1 = 21 × 431 × n2
5n1 −1 = 1 mod n1
n1 −1
5 2 ̸= 1 mod n1
n1 −1
5 43 ̸= 1 mod n1
n1 −1
5 n2
̸= 1 mod n1

qui prouvent la primalité de n1 , sous réserve de celle de n2 ,

laquelle procède de

n2 − 1 = 22 × 131 × 431
2n2 −1 = 1 mod n2
n2 −1
2 2 ̸= 1 mod n2
n2 −1
2 13 ̸= 1 mod n2
n2 −1
2 43 ̸= 1 mod n2 .

On peut affiner ce résultat en ne disposant que d’une factorisa-

tion partielle de n.
Théorème 8.3.4. Soit n ≥ 1. On suppose connaı̂tre une factorisa-
tion partielle de n − 1 de la forme n − 1 = FQ où
— F = ∏ qeq est complètement factorisé en produit de facteurs
premiers ; √
— le cofacteur Q satisfait Q < n.
Alors n est premier si et seulement si il existe a tel que

an−1 ≡ 1 mod n
(
n −1
pgcd( a q − 1, n) = 1 pour tout q | F, q premier.

66
8.3. Preuves de primalité

8.3.5 Généralisation : l’algorithme ECPP

Le test n − 1 ne fonctionne qu’à condition de savoir factoriser

n − 1. Ce qui est improbable pour de grands entiers.
Mais la même technique s’applique avec d’autres groupes que
Z/nZ : les courbes elliptiques. On sait en effet qu’une courbe
√
sur F p possède au plus ( p + 1)2 points.
Si on montre qu’une équation
√ de courbe E modulo n possède
un point P d’ordre m > ( 4 n + 1)2 , au sens où
— mP = 0 modulo n
— les coordonnées [ x, y, z] de mq P sont inversibles modulo
n √
alors il ne peut pas exister de premier p < n qui divise n, sans
quoi la courbe réduite aurait un point d’ordre trop élevé.
Désormais, il existe beaucoup de courbes, donc une plus
grande probabilité d’en trouver une dont l’ordre se factorise.
Mieux, on a des techniques (multiplication complexe) pour
partir d’un nombre de points possible fixé, et construire une
courbe dont c’est le cardinal.

67
Chapitre 8. Composition, primalité

68
CHAPITRE 9
Factorisation d’entiers

Les méthodes récentes de factorisation reposent sur le prin-

cipe suivant : si n est divisible par p, comment obtenir une
congruence modulo p qui ne soit pas issue d’une congruence
modulo n ?
Trois idées principales
— utiliser le théorème d’Euler a p−1 = 1 mod p ;
— tirer parti du hasard
— construire patiemment des égalités entre carrés a2 =
b2 mod n.

9.1 Trial division et crible d’Eratosthène

√
Si n est composé, il existe p ≤ n qui divise n. En testant la
divisibilité par tous les entiers
√ successifs on a un algorithme de
factorisation naı̈f en O( n) divisions.
On peut améliorer légèrement en divisant par les seuls
nombres premiers, soit via une base précalculée soit en effec-
p
tuant un crible d’Eratosthène, ce qui ramène à O( log p ) divi-
sions pour trouver le facteur premier p.

69
Chapitre 9. Factorisation d’entiers

9.2 Méthode p − 1 de Pollard

Principe Si p | n, alors pour tout a premier à n on a a p−1 =

1 mod p. C’est aussi vrai si l’exposant est juste un multiple de
p − 1 : si p − 1 | M alors p | pgcd( a M − 1, n).
Or il est facile de trouver un tel multiple M si p − 1 n’a que des
facteurs premiers assez petits.
Définition 9.2.1. Soient a et B deux entiers. On dit que a est B-
friable si tous les facteurs premiers de a sont inférieurs à B
Proposition 9.2.2. Soit n un entier divisible par un facteur premier
p tel que p − 1 soit B-friable. Alors en posant
j k
M = ∏ q f q , où f q = logq (m)
q≤ B

on a pour tout a ∈ (Z/nZ)×

p | pgcd( a M − 1, n).

Concrètement, pour factoriser un entier n, on procède en cal-

culant de proche en proche les a M pour M = M( B) croissant,
jusqu’à ce que l’on obtienne les facteurs premiers de n les plus
friables.
Exemple 9.2.3. Soient n = 8051, pour lequel on choisit de
prendre a = 2 et une borne B = 5. On a

212 < n < 213

38 < n < 39
55 < n < 56
et on calcule successivement
M2 = 212 a2 = 2 M2 ≡ 3844 mod n
8
M3 = M2 × 38 a3 = a32 ≡ 5600 mod n
Le facteur premier p = 97 sort lorsqu’on considère q = 3 : en
effet, p − 1 = 25 × 3 est 3-friable. Si l’on va jusqu’à B = 5,

70
9.2. Méthode p − 1 de Pollard

le facteur ne change pas, et en effet p = 83 est l’autre facteur

premier de n, pour lequel p − 1 = 2 × 41 n’est pas 5-friable. Ce
facteur ne sortira que pour B ≥ 41.
Proposition 9.2.4. Si n a un facteur premier p qui est B-friable, la
méthode l’exhibe avec une complexité de

B
O( log(n) M (n))
log B

opérations binaires, où l’on note M (n) la complexité de la multipli-

cation dans Z/nZ.

Algorithme 9.2.1 méthode p-1 de Pollard

pollard p(n,B=10000,a=3) = {
aM = Mod(a,n);
forprime(p=2,B,
aM=aM^(p^logint(n,p));
g = gcd(lift(aM)-1,n);
if(g>1,break())
);
g;
}

Il est possible que tous les facteurs premiers de n aient même

friabilité p − 1 (cf. M29 TP). Il n’est pas difficile d’adapter.
Une variante consiste à prendre un exposant de la forme M =
B!, qui est aussi multiple de beaucoup de nombres premiers.

Algorithme 9.2.2 méthode p-1, variante factorielle

pollard p(n,B=10000,a=3) = gcd(lift(Mod(a,n)^B!-1),n);

71
Chapitre 9. Factorisation d’entiers

9.3 Méthode ρ de Pollard

Principe On tire parti du phénomène statistique appelé para-

doxe des anniversaires :
Proposition 9.3.1. Soit x1 , . . . xk des éléments tirés selon une loi
uniforme dans un ensemble de cardinal p. Alors pour
p
8p log 2 + 1 + 1 √
k≥ ≈ 1.18 p
2
la probabilité qu’ils soient tous disctincts est inférieure à 1/2.

Démonstration. La probabilité d’être distincts vaut

p ( p − 1) . . . ( p − k + 1) i − pi −1)
− k(k2p
pk
= ∏ (1 − p ) ≤ ∏ e =e

Si donc on tire des éléments xi au hasard modulo n, et si p est le

√
plus petit facteur premier de n, alors en O( p) essais on aura
xi ≡ x j mod p avec xi ̸= xi mod n, d’où le facteur p | pgcd( xi −
x j , n) ̸= n.
Toutefois, il est très coûteux de calculer les pgcd pour tout
couple i, j. Pour accélérer le procédé, l’idée de Pollard est de
ne pas tirer des éléments aléatoires mais de les produire par la
suite récurrente donnée par f : x ↦→ x2 + 1 ; pour x0 ∈ Z/nZ,
on pose xk = f k ( x0 ).
Il se trouve que cette suite se comporte de manière aléatoire, ou
tout au moins conforme au paradoxe des anniversaire. D’autre
part, le fait que l’itération soit polynomiale permet d’utiliser
l’astuce suivante :
Proposition 9.3.2. Soient f ∈ Z[ x ], x0 ∈ Z/nZ et la suite
récurrente xk = f k ( x0 ). Alors s’il existe i < j tel que xi =
x j mod p, il existe k < 2j tel que xk = x2k mod p.

72
9.3. Méthode ρ de Pollard

Démonstration. Modulo p, la suite est périodique de période

j − i à partir du rang i. Quitte à augmenter la période, on peut
supposer j > 2i, alors k = j − i convient.

Remarque 9.3.3. Moralement cela revient à considérer un lièvre

(x2k ) et une tortue (xk ) : à partir du moment où ils courent sur
la même piste circulaire (la boucle du rho), il y a des moments
où ils sont en même temps au même endroit. Il suffit de faire
des pgcd à la suite des instants k (et non plus entre tout couple
i, j).
Exemple 9.3.4. Avec n = 8051, on calcule les suites xk et x2k , en
les considérant d’emblée modulo p = 97.

k 0 1 2 3 4 5 6 7 8
xk 1 2 5 26 95 5 26 95 5
x2k 1 5 95 26 5 95 26
pgcd x 1 x 97 1 1 97

Proposition 9.3.5. Si l’on admet que la suite xk a un comportement

√
aléatoire, alors on trouve p en O( p) itérations, en particulier en
√
O ( 4 n ).

Algorithme 9.3.1 méthode rho de Pollard

pollard rho(n) = {
my(x,y,g);
x = y = g = 1;
while(g==1,
x = (x^2 + 1)
y = (y^2 + 1)
y = (y^2 + 1)
g = gcd(x-y,n);
);
g;
}

Remarque 9.3.6. Quand n est grand, on peut faire une petite

amélioration du code précédent en remarquant qu’à chaque

73
Chapitre 9. Factorisation d’entiers

étape on calcule trois carrés et un pgcd modulo n. Ce dernier est

beaucoup plus coûteux, d’un facteur O(log(n)). L’amélioration
consiste à accumuler un produit P = ∏( xk − x2k ) mod n sur
L itérations k0 ≤ k < k0 + L, et à ne calculer qu’à ce moment
pgcd( P, n), en choisissant L de sorte que le coût du pgcd soit
de l’ordre du coût des 4L multiplications modulo n (3 carrés et
un produit).

Algorithme 9.3.2 méthode rho, variante

pollard rho acc(n,l) = {
my(x,y,g,p,l);
g = 1; if(!l,l = 1+logint(n,2)∖30);
x = y = Mod(1,n);
while(g==1,
p = prod(i=1,l,
x = x^2 + 1;
y = y^2 + 1;
y = y^2 + 1;
x-y);
g = gcd(lift(p),n);
);
g;
}

9.4 Méthode de Fermat

Prenons à nouveau n = 8051. Fermat le factorise de tête en

écrivant

n = 8100 − 49 = 902 − 72 = 97 × 83

Plus
√ généralement, pour tout entier n, on cherche un entier x >
n tel que le reste x2 mod n soit exactement un carré y2 de Z.
Cf. exercice .
En
√ pratique,
on peut aussi parcourir des nombres de la forme
an + b, pour a, b ≥ 1.

74
9.5. Méthodes de cribles algébriques

9.5 Méthodes de cribles algébriques

√ d’un exemple plus retors, avec n = 3239. On a m =

Partons
n = 56, et on calcule successivement

( m + 1)2 = 2 ×5 modn
( m + 2)2 = 53 modn
( m + 3)2 = 2 ×112 modn

À ce stade, on n’a pas encore trouvé de carré. Toutefois, les trois

relations multipliées entre elles forment la relation

((m + 1)(m + 2)(m + 3))2 = (2 × 52 × 11)2 mod n

qui permet de factoriser n.

Exercice : de même, factoriser n = 1649, n = 3247.
L’idée de combiner plusieurs relations factorisées jusqu’à for-
mer un carré fonctionne de manière générale selon les principes
suivants :
— choisir une borne de friabilité B, et numéroter p1 , . . . pk
les premiers inférieurs à B √
√
— parcourir les valeurs x2 − n pour n < x < 2n, à la
recherche de relations B-friables
k
e
( xi )2 ≡ ∏ p j i,j mod n
j =1

que l’on mémorise

— quand on a obtenu k + 1 telles relations, construire la
matrice de parité des exposants du membre de droite

E = (ei,j )i,j mod 2

et déterminer un vecteur du noyau

λ ∈ F2k+1 , λE = 0.

75
Chapitre 9. Factorisation d’entiers

Ce vecteur indique quelles lignes selectionner de sorte

que les exposants de la relation produit soient tous pairs,
c’est-à-dire que l’on ait un carré à droite.
— Calculer
x= ∏ xi
i,λi =1
k ∑i,λ =1 ei,j
i
y= ∏ pj 2

j =1

qui vérifient x2 ≡ y2 mod n

— si x ̸≡ ±y mod n, pgcd( x + y, n) est un facteur non tri-
vial de n.
Remarque 9.5.1.
— le choix de la borne de friabilité est délicat : si elle est trop
petite, il y a peu de relations friables et l’on n’arrive pas
à en trouver ; si elle est trop grande, il est plus facile de
trouver des relations mais il faut en trouver beaucoup,
et le temps mis à tester la friabilité est plus long.
— la phase qui consiste à collecter des relations peut être
l’objet de beaucoup d’améliorations√ : on peut partir de
valeurs xi aléatoires, de la forme an + y ≡ y2 +
2m a y + c a mod n, éliminer a priori de la base les pre-
miers p tels que y2 + 2m a y + c a mod p n’a pas de ra-
cine,. . .
— on peut prendre plus de k + 1 relations, le noyau
sera d’autant plus grand et cela permet de considérer
d’autres vecteurs du noyau dans le cas où on aboutit à
une relation triviale x ≡ ±y mod n.
— il est utile de remarquer que certains premiers, en effet
on connaı̂t par avance les premiers pi qui peuvent di-
viser x2 − n : ce sont ceux pour lesquels n est un carré
modulo pi . De plus dans ce cas x doit être congru à l’une
des deux racines carrées de n modulo pi .
— une amélioration majeure est l’idée de crible : au lieu
d’essayer de factoriser chaque valeur x2 − n par les pre-
miers de la base en jetant toutes celles qui ne sont pas
friables, on procède à l’envers : on fixe un intervalle de

76
9.5. Méthodes de cribles algébriques

valeurs x à cribler, et pour chaque premier p de la base

on ne divise par p que les valeurs x2 − n pour x congru
aux racines x1 et x2 de x2 − n modulo p (que l’on connaı̂t
par avance). Les valeurs complètement factorisées après
passage par tous les premiers de la base fournissent les
relations.
— le calcul d’un vecteur du noyau est une étape qui peut
vite devenir délicate quand la taille de la base aug-
mente : la matrice est de taille k2 , avec k qui peut vite
être de l’ordre du millier, et le calcul de λ est en O(k3 )
opérations par la méthode de Gauss (réduction à une
matrice triangulaire). Toutefois, en pratique la matrice E
est creuse (la densité de coefficients non nuls est faible)
et la méthode de Gauss a tendance à remplir la matrice.
Il est préférable de stocker la matrice sous forme creuse
(on ne mémorise que les emplacements de coefficients
non nuls), et d’adopter des algorithmes de Wiedemann
ou de Lanczos qui exploitent cette propriété.
— avant de calculer le noyau, on peut simplifier la matrice
en enlevant toutes les relations orphelines, c’est-à-dire
des relations qui sont seules à faire intervenir un des
facteurs de la base. On enlève aussi la colonne (nulle)
correspondante.
— d’autres améliorations : autoriser de relations avec un
(ou deux) premiers hors de la base, remplacer les divi-
sions lors de la phase de crible par une simple estimée
de la taille du facteur friable (remplacer une division par
une addition) pour deviner les bons candidats à la friabi-
lité, utiliser sur le même intervalle de valeurs x plusieurs
polynômes de la forme ax2 + bx + c avec n | b2 − 4ac,
choisis pour prendre de petites valeurs. . .

77
Chapitre 9. Factorisation d’entiers

78
CHAPITRE 10
Logarithme discret

Définition 10.0.1. Si A ∈ G = ⟨ g⟩, avec g d’ordre n, on note

Log( A, g) l’unique a ∈ Z/nZ tel que A = g a .

Le calcul de Log( A, g) est difficile. Par énumération il nécessite

O( a) = O(n) multiplications jusqu’à trouver a.

10.1 Baby-step Giant-step

Au lieu de chercher un élément fixé dans une grande liste

d’éléments, on cherche un élément commun à deux listes plus
petites (stratégie meet in the middle, déjà vue dans l’attaque
double DES).
√
On pose B = n , alors par décomposition en base B, il existe
0 ≤ x0 , x1 < B tels que

a = x0 + x1 B

dans ce cas

A = g a ⇔ g x0 = A ( g − B ) x1

de sorte qu’il suffit de trouver une collision en x0 , x1 .

L’algorithme est le suivant
— calculer la liste L des g x0 pour 0 ≤ x0 < B

79
Chapitre 10. Logarithme discret

— poser G = g− B
— pour 0 ≤ x1 < B, dès que AG x1 est dans L et vaut g x0 ,
rendre a = x0 + x1 B.
Pour rendre la recherche rapide, il faut remplacer la liste par
une structure qui rende l’insertion et le test d’appartenance ra-
pides
— une table de hachage (arbre), l’insertion et la recherche
sont en log
— une liste que l’on trie, ce qui permet des recherches di-
chotomiques en log. √
Dans
√ tous les cas, pour B ≈ √ n la complexité est de
O( n log n) opérations et O( n) en espace de stockage
d’éléments.

10.2 Méthode ρ de Pollard

Pour éviter le stockage de la méthode Baby-step Giant-step, on

peut adapter la méthode ρ au logarithme discret, voir TP.

10.3 Décomposition de Pohlig-Hellman

Dès que l’ordre du groupe n’est pas premier, on peut

décomposer un problème de logarithme de la manière suivante
Lemme 10.3.1. Soit G = ⟨ g⟩ un groupe d’ordre n = dm. Alors
pour tout A = g a dans G, on a

a ≡ Loggd ( Ad ) mod m.

De plus, si l’on a calculé a0 = Loggd ( Ad ) ∈ Z/mZ et que l’on écrit

a = a0 + ma1 , alors

a1 = Loggm ( Ag− a0 ) ∈ Z/dZ.

80
10.3. Décomposition de Pohlig-Hellman

Démonstration. On écrit a = a0 + ma1 et Ad = gda0 +na1 =

( g d ) a0 .

On va utiliser ce lemme récursivement pour casser un

problème de logarithme discret jusqu’à des instances de loga-
rithmes discrets dans des groupes de cardinal premier. Il est
commode de décomposer d’abord selon les premiers distincts
pour utiliser la première partie du lemme et un relèvement par
le lemme chinois.

10.3.2 Lemme chinois sur l’ordre du groupe

Si d | n, Z/nZ a un unique sous-groupe d’ordre d qui est en-

gendré par nd (et isomorphe à Z/dZ).
Proposition 10.3.3. Soit G = ⟨ g⟩ un groupe d’ordre n = ∏ mi où
les mi sont deux à deux premiers entre eux.
n
Alors pour tout A ∈ G, si l’on pose Mi = mi on a

Log( A, g) ≡ Log( A Mi , g Mi ) mod mi

où chacun des logarithmes discrets à droite se situe dans un sous-

groupe ⟨ g Mi ⟩ d’ordre mi .
Ainsi,
n
Log( A, g) = ∑ ui mi Log( A Mi , g Mi )
i

où ui = Mi−1 mod mi .

Démonstration. On applique pour chaque i le lemme en

écrivant n = mi Mi , puis on remonte par le lemme chinois.

81
Chapitre 10. Logarithme discret

10.3.4 Décomposition en base p sur la composante

p-primaire

Proposition 10.3.5. Soit G = ⟨ g⟩ un groupe cyclique d’ordre n =

pe et A ∈ G. Alors en décomposant selon la base p
e −1
Log( A, g) = ∑ ai pi
i =0
on a
e −1 e −1
a0 = Log( A p , gp )
i
puis pour 0 ≤ i ≤ e − 2, en posant Ai = g a0 +...ai p on a
récursivement
e − i −2 e −1
ai+1 = Log(( AAi−1 ) p , gp )

Démonstration. On applique le lemme avec pe = p × pe−1 en

écrivant a = a0 + p ã1 . On a bien la formule pour a0 , et ã1 =
Log(( AA0−1 ) p , g p ) est calculé dans ⟨ g p ⟩ d’ordre pe−1 .
On réapplique le lemme en posant ã1 = a1 + p ã2 , etc.

Remarquons que tous les logarithmes sont calculés dans le

e −1
même sous-groupe d’ordre p G p = ⟨ g p ⟩, de sorte que si l’on
fait du Baby-steps giant steps on peut conserver la table des pas
de bébé d’une fois sur l’autre.

10.4 Calcul d’indice

Cette méthode permet de calculer des logarithmes discrets

dans F×
p.

On présente cette méthode à travers l’exemple suivant : soit

p = 101, F×p = ⟨ g ⟩ pour g = 11. On veut calculer Log( A, g )
pour A = 34.

82
10.4. Calcul d’indice

10.4.1 Première étape

On calcule les premières puissances de g, et on essaie de les

décomposer en produit de petits facteurs premiers

g2 = 22 × 5 mod 101
g3 = 2 × 32 mod 101
g4 = −22 mod 101

Arrivé à ce stade, on peut prendre le logarithme de chaque

ligne. En posant x2 = Log(2, g), x3 = Log(3, g) et x5 =
log(5, g) on obtient le système (on utilise que −1 = g50 )

2 = 2x2 + x5 mod 100

3 = x2 + 2x3 mod 100
4 = 50 + 2x2 mod 100

On a 3 équations et 3 inconnues, d’où les valeurs

x2 = −23
x3 = 13
x5 = 48

10.4.2 Deuxième étape

On considère à présent les éléments de la forme Agk , et on es-

saie de les factoriser sur les premiers 2, 3, 5 dont on connaı̂t le
logarithme

Ag = 71 mod 101
Ag2 = 2 × 37 mod 101
Ag3 = 2 × 3 mod 101

Cette dernière relation est la bonne, on en déduit Log(34, g) +

3 = x2 + x3 mod 100, soit Log(34, g) = −13.

83
Chapitre 10. Logarithme discret

10.4.3 Algorithme

L’algorithme général est le suivant : on choisit une borne de

friabilité B, dans la première étape on collecte les relations qui
peuvent s’écrire sous la forme gk = ∏q< B qeq . Dès que l’on a
plus de relations que de premiers q ≤ B, on peut résoudre le
système linéaire

∑ eq Log(q)

k= k
mod p − 1

ce qui donne les logs des petits nombres premiers.

Ensuite, on cherche une relation friable Agk = ∏q qeq de la-
quelle on déduit Log( A).
Remarque 10.4.4. Le choix de B est crucial, trop petit on ne
va pas trouver de relations fiables, trop grand il faudra trouver
beaucoup de relations.
On peut estimer la probabilité qu’une valeur x < p soit B
friable, qui est de l’ordre de

log( p)nB 1
P( B) = prodq< B
nB ! log(q)

où n B est le nombre de premiers q ≤ B.

Pour obtenir n B relations, il faut compter O( Pn(BB) F ( B))
opérations, où F ( B) est le coût d’un test de B-friabilité. En-
suite on résout le système linéaire en O(n3B ) opérations, puis
on cherche une dernière relation. On choisit donc B pour mini-
miser Pn(BB) F ( B) + n3B .

84
CHAPITRE 11
Protocoles cryptographiques

Outre la confidentialité d’échanges, les techniques cryptogra-

phiques fournissent des solutions pour certains problèmes
pratiques, comme l’authentification, la signature. On donne
quelques exemples rapides.

11.1 Fonctions de hachage

On souhaite avoir une notion d’empreinte digitale, c’est-à-dire

d’une information partielle qui, en pratique, caractérise un
tout.
Une fonction de hachage est une fonction qui prend une chaı̂ne
de longueur quelconque et renvoie une empreinte de taille `
fixée

h : (F2 )* → F2`

de sorte que
— le calcul de l’empreinte est très rapide
— le problème du calcul de préimage : ≪ étant donné x ∈
F2` , trouver m tel que x = h(m) ≫ est calculatoirement
infaisable
— le problème de collision : ≪ trouver m ̸= m′ tels que
h(m) = h(m′ ) ≫ est également infaisable en pratique

85
Chapitre 11. Protocoles cryptographiques

Ces conditions impliquent que ` doit valoir au moins de l’ordre

de 128 bits pour rendre impossibles les recherches de colli-
sions avec optimisation temps-mémoire (paradoxe des anni-
versaires).
Exemples : SHA-1, SHA-3, MD5, RC4 (cassé)
On utilise de telles fonctions pour assurer l’intégrité de
données numériques (en particulier lors de téléchargements).

11.1.1 Construction

On peut fabriquer une fonction de hachage à l’aide d’un cryp-

tosystème fonctionnant sur des blocs de taille `, par exemple
en itérant le chiffrement sur le message nul en prenant les blocs
du message comme clefs successives. Si le chiffrement est sûr,
la fonction obtenue l’est également.
Ainsi, le système Unix utilisait DES comme fonction de ha-
chage pour ses mots de passe, ce qui est beaucoup trop faible
de nos jours.
En pratique, on emploie des fonctions construites
spécialement, comme SHA3.

11.2 Signature

La signature d’un document est une empreinte qu’une seule

personne sait produire, mais que chacun peut constater et au-
thentifier. La signature sert à prouver qu’une personne est l’au-
teur, ou a connaissance d’un document (cf. chèque ou recom-
mandé), pour éviter à la fois
— les fausses attributions : prétendre être l’auteur d’un
document
— la répudiation : prétendre ne pas en être l’auteur ou ne
pas en avoir connaissance.

86
11.3. Echange de clefs

Si m est un document électronique, et Alice a mis en place un

cryptosystème asymétrique et choisi une fonction de hachage
publique h, la valeur

s = d(h(m))

est une signature du document m que

— seule Alice peut avoir produite, puisque cela nécessite la
fonction de déchiffrement donc la clef privée
— n’importe qui peut vérifier, en effectuant la vérification
e(s) = h(m)
Exemple 11.2.1. Les pdf créés par le logiciel payant Adobe
Acrobat sont signés, et donnent droit à l’utilisation de certaines
fonctions supplémentaires du logiciel de lecture gratuit Adobe
Reader.
En 2009, la partie chiffrement était solide. Toutefois, l’utilisa-
tion d’une fonction de hachage trop faible, et la prise en compte
d’une partie seulement du document pour calculer le haché
permettait de créer des documents munis d’une fausse signa-
ture, simplement en ajoutant au document des commentaires
qui le rendent compatible avec une signature valide extraite
d’un document authentique.

11.3 Echange de clefs

Pour se mettre d’accord sur une clef secrète pour un chiffre-

ment symétrique, Alice et Bob peuvent peuvent procéder de
la manière suivante, en utilisant un système de type El Gamal
de groupe G = ⟨ g⟩ pour lesquels ils ont des clefs A = g a et
B = gb :
— l’un et/ou l’autre tire une valeur r aléatoire (publique)
— Alice peut calculer la clef k = rB a
— Bob peut calculer la clef k = rAb .
Ce protocole est dû à Diffie et Hellman, il marque la première
irruption d’un mécanisme asymétrique en cryptographie.

87
Chapitre 11. Protocoles cryptographiques

11.4 Authentification

Une entité désire authentifier Alice pour la laisser accéder à des

services. On suppose qu’une authentification initiale a permis
d’initialiser le système de manière sûre, et on s’intéresse aux
authentifications ultérieures.

11.4.1 Mot de passe

C’est la méthode la plus courante, on a initialisé un mot de

passe dans des circonstances où l’identité n’est pas mise en
doute (création de compte, envoi par la poste. . .), et l’utilisateur
entre simplement son mot de passe.
Toutefois, il est inutile et dangereux que l’entité dispose du mot
de passe d’Alice : employés indélicats ou compromission de la
base de donnée risquent de divulguer le mot de passe.
Il suffit de mémoriser le haché du mot de passe, et de vérifier
que les hachés coı̈ncident lors d’une identification. Si la fonc-
tion de hachage est sûre, on ne perd rien en sécurité.
Un autre danger cependant : en pratique, l’entropie des mots
de passe choisis par les humains est très insuffisante (mots du
dictionnaire avec variantes prévisibles). De sorte que munis de
hachés, une attaque par force brute permet de retrouver facile-
ment tous les mots de passe faciles, en comparant aux hachés
classiques.
Cette stratégie fonctionne mal en général pour un mot de passe
donné, mais sur les grandes bases de mots de passe obtenues
lors des piratages récents (Sony, Unix, Apple) cela permet tou-
jours de casser plus de 20mots de passe.
Voir par exemple un logiciel comme ≪ John the ripper ≫

88
11.4. Authentification

Parade : sel et hachage lent

Voir [Link]
how-to-securely-hash-passwords/31846#31846
Une parade consiste à stocker non pas le mot de passe m, mais
un couple de type (r, h(r, m)) où r est une chaı̂ne aléatoire qui
paramètre la fonction de hachage.
De cette manière, le calcul de l’authentification n’est pas très
différent, mais deux mêmes mots de passe n’apparaissent ja-
mais de la même manière dans la base, et une attaque par force
brute se ramène à l’attaque d’un seul mot de passe, beaucoup
plus incertaine et coûteuse.
Par ailleurs, on utilise volontairement une fonction h lente et
coûteuse en mémoire : c’est un inconvénient pour le serveur qui
authentifie des utilisateurs, mais cela handicape encore plus
l’attaquant qui tente une recherche par force brute.

Phishing

Si une fausse entité réussit à se faire passer pour la vraie, Alice

lui fournit son mot de passe. Avec la technique des mots de
passe, il n’y a malheureusement pas de parade. . .

11.4.2 Clef publique/clef privée

Si Alice dispose d’un couple clef publique/clef privée et que

l’entité a noté la clef publique, la procédure suivante permet
d’authentifier Alice
— l’entité envoie une chaı̂ne aléatoire r
— Alice renvoie d(r )
— l’entité vérifie que e(d(r )) = r.
Toutefois, une fausse entité peut utiliser ce protocole pour avoir
accès à la fonction de déchiffrement d’Alice (en envoyant des
chiffrés r bien choisis). Il vaut mieux symétriser l’échange (pour

89
Chapitre 11. Protocoles cryptographiques

qu’Alice vérifie en même temps l’authenticité de l’entité) et

ajouter de l’aléa, de sorte que ni Alice ni l’entité ne choisissent
ce qui va être déchiffré.
On peut procéder par exemple ainsi :
— Alice et l’entité choisissent chacun r a et re aléatoires, et
envoient les hachés h(r a ) et h(re ) ;
— ils envoient ensuite r a et re , et chacun vérifie que cela
correspond aux hachés annoncés ;
— Alice et l’entité calculent d a,e (r a + re ) et l’envoient ;
— Alice et l’entité vérifient chacun que ea,e (d a,e (r a + re )) =
r a + re .
La phase d’envoi des hachés n’est là que pour s’assurer qu’au-
cune des parties ne puisse choisir sa chaı̂ne r a ou re en fonc-
tion de celle de l’autre, soit pour accéder à la fonction de
déchiffrement, soit pour répondre en imitant des échanges es-
pionnés antérieurement (on s’engage par avance sur une valeur
sans pour autant la donner).

11.5 Preuves sans apport d’information

Comme on le voit avec l’authentification par mot de passe, il

est problématique que l’authentification rende nécessaire la di-
vulgation d’une information secrète. Il serait préférable qu’on
puisse vérifier de manière fiable la connaissance d’une telle in-
formation sans que rien n’en soit révélé.
Par exemple, dans un système ElGamal, si quelqu’un veut
vérifier qu’Alice dispose de sa clef privée a = Log( A, g), on
peut procéder ainsi
— Alice tire r au hasard et envoie R = gr
— la personne tire x au hasard et l’envoie à Alice
— Alice envoie y = r + ax
— la personne vérifie l’égalité gy = RA x
Ce faisant, l’entité n’a accès à rien d’autre que des données pu-
bliques, et pourtant seule Alice peut calculer la bonne valeur
y.

90
11.6. Blockchains

11.6 Blockchains

Une blockchain permet à une communauté de certifier des

données sans recourir à une autorité de confiance (état,
banque).
L’objectif est d’inclure les données dans une chaı̂ne d’informa-
tions de sorte que la communauté dans son ensemble ait intérêt
à vérifier la validité des données.
Pour cela, le principe est de répartir l’information dans des
blocs, de sorte que
— il soit très facile de vérifier la validité des blocs
— il soit coûteux de fabriquer un bloc
— la création d’un bloc soit récompensée.
Un bloc est composé :
— d’un lien vers le bloc précédent
— de l’information qu’on veut ajouter à la chaı̂ne
— d’un code de validation
Le code de validation doit être déterminé de sorte que le bloc
soit valide, c’est-à-dire que son haché vérifie une propriété
(commencer par x zéros).
C’est cette étape qui est très coûteuse, puisqu’on ne sait pas
trouver de préimage aux fonctions de hachage on en est réduit
à essayer des codes au hasard jusqu’à ce que l’un convienne.
Voir l’excellente démonstration [?].
La blockchain évolue en parallèle, tout le monde essaie de ra-
jouter des blocs. On risque vite d’avoir plein de blockchains
différentes. Toutefois puisque
— chacun a intérêt à avoir la même blockchain que les
autres
— on privilégie la chaı̂ne la plus longue
— il est très coûteux d’ajouter des blocs
les choses se stabilisent bien en pratique. Quand une entité
réussit à ajouter un bloc, elle le publie et les autres ont intérêt à

91
Chapitre 11. Protocoles cryptographiques

l’adopter et à prolonger la même chaı̂ne plutôt que prendre le

risque de lancer une chaı̂ne concurrente qui sera délaissée.
Le cas intéressant est quand deux propositions de blocs valides
sont publiées à peu près en même temps : la communauté se
scinde temporairement entre ceux qui cherchent à prolonger
l’une et l’autre chaı̂ne. Cette situation ne dure pas : dès l’ajout
du bloc suivant une chaı̂ne aura de l’avance, ce qui va attirer
plus de mineurs et accélérer encore sa progression sur les blocs
suivants. La communauté va privilégier une branche et l’autre
sera abandonnée.
On ne peut donc considérer qu’une transaction est
définitivement adoptée par la blockchain qu’à partir du
moment où elle est à une certaine profondeur (5 ou 6 blocs du
sommet).
Pour la même raison, une fois un bloc ajouté à la chaı̂ne, et
puisque tous les blocs suivants dépendent de son contenu, il
n’est plus possible de le modifier (il faudrait recréer toute la
chaı̂ne de blocs suivants, or elle grandit plus vite qu’on arrive
à la modifier).
Ceci n’est plus vrai si une entité acquiert la majorité de la puis-
sance de calcul (attaque des 51%), dans ce cas elle peut impo-
ser l’adoption de ses blocs puisqu’elle travaille plus vite que le
reste de la communauté, et peut même réécrire la chaı̂ne.

11.7 Partage de secret

Le but est de distribuer une information entre plusieurs per-

sonnes, de manière à ce que ce soit uniquement en se réunissant
qu’elles parviennent à reconstituer l’information.
Par exemple
— l’emplacement du trésor des pirates, l’accès à un trésor
— un testament, nécessitant la réunion des héritiers

92
11.7. Partage de secret

— un coffre à la banque, qui ne s’ouvre qu’en présence

du banquier et du propriétaire. Plus généralement, les
procédure d’authentification à k facteurs.
— la clef d’activation du système DNSSEC, en cas d’at-
taque majeure des noeuds DNS principaux d’internet,
est confiée à la réunion d’au moins 5 parmi 7 personnes.
On pourrait procéder par intersections d’hyperplans dans un
espace affine. Une construction plus élégante est due à Shamir :
— on se place dans un grand corps fini F p
— le secret est un élément s = a0 ∈ F p .
— on tire au hasard a1 , . . . a p−1 ∈ F p et on construit le po-
lynôme A( x ) = ∑ ai xi .
— on fournit à la i-ème personne l’évaluation (i, A(i )),
A (i ) ∈ F p .
Pour reconstituer le secret, tout sous-ensemble de k personnes
réunit k évaluations d’un polynôme de degré k − 1, ce qui per-
met de reconstruire A( x ) par interpolation.
Ce système est satisfaisant car chaque participant reçoit une
quantité d’information égale à celle du secret, et tant que l’on a
réuni moins de k participants on n’a aucune information sur le
secret.

93
Chapitre 11. Protocoles cryptographiques

94
CHAPITRE 12
Réseaux et cryptographie

12.1 Définition

Définition 12.1.1. Un réseau est un sous-groupe de Rn engendré

par une base de Rn .
Exemple 12.1.2.
— le réseau Zn ⊂ Rn . Comme on le verra, il faut avoir
conscience que ce réseau n’est pas du tout le réseau ty-
pique, il est beaucoup trop régulier et symétrique.
— réseau
√ hexagonal Z[ j] ⊂ C = R2
— Z[ 2] ⊂ R n’est pas un réseau (sous-groupe dense de
2

R)
— toute matrice A ∈ Gln (R) définit le réseau AZn en-
gendré par les colonnes de A.
Comme groupe, un réseau est isomorphe à Zn , mais il a une
structure géométrique supplémentaire héritée de l’espace am-
biant Rn : distance, volume.
Définition 12.1.3. Soit V = (v1 , . . . vn ) une base d’un réseau Λ.
Le domaine fondamental relativement à V est l’ensemble
DV = V × [0, 1[n = ∑ xi vi ∈ Rn , 0 ≤ xi < 1

L’espace est pavé par les translatés du domaine par le réseau

Rn =
[
x + Dv
x ∈Λ

95
Chapitre 12. Réseaux et cryptographie

Définition 12.1.4. Soit Λ = AZn ⊂ Rn un réseau. Le volume de

Λ est le volume d’un domaine fondamental

Vol(Λ) = Vol(Rn /Λ) = |det( A)|

En crypto, on s’intéresse surtout aux réseaux entiers, c’est-à-

dire aux sous-groupes de Zn . Dans ce cas, le volume est le car-
dinal du groupe quotient
Zn /Λ.
Une construction courante, le réseau du noyau modulo N
d’une application linéaire :

Λ = { x ∈ Zn , Ax ≡ 0 mod N }

Exemple 12.1.5. Soit p un nombre premier et λ ∈ F×

p , on pose
Λ = {( x, y), x = λy mod p} ⊂ Z2 .
Une base est donnée par les vecteurs ( p, 0) et (λ, 1), le réseau
est de volume p (ce qui correspond au fait qu’une proportion
1/p des vecteurs de Z2 est dans le réseau).

12.2 Courts vecteurs

Trouver le plus petit vecteur d’un réseau est problème diffi-

cile, NP-dur en général [Link]
6876-Fall2015/[Link].
Pourtant, il est facile de démontrer qu’il existe nécessairement
des vecteurs courts
Théorème 12.2.1. Soit Λ ⊂ Rn un réseau, on note Vn le volume de
la boule unité. Si Vn Rn ≥ Vol(Λ), alors Λ contient un vecteur non
nul de norme ≤ 2R.

Démonstration. La projection de la boule de rayon R sur Rn /Λ

ne peut pas être injective, deux vecteurs x, y de même image

96
12.3. Exemples de problèmes résolus à l’aide de vecteurs
courts

fournissent un vecteur x − y du réseau, de norme inférieure à

2R.

Corollaire 12.2.2. En notant ‖v1 ‖ le plus petit vecteur non nul, on

1
Vol(Λ) n

a ‖ v1 ‖ ≤ 2 Vn , où le volume de la boule

n n
2π 2 1 2πe 2
Vn = ∼ √
(n + 1)Γ( n2 ) nπ n

tend vers 0 pour n → ∞.

Exemple 12.2.3. Avec l’exemple précédent, le volume de la
boule est V2 = π, donc il existe un vecteur de norme x2 + y2 ≤
q 2
(2 πp < 2p.

Si p ≡ −1 mod 4, on peut choisir λ tel que λ2 = −1, alors

le vecteur court est de norme x2 + y2 ≡ 0 mod p, on a donc
x2 + y2 = p.

12.3 Exemples de problèmes résolus à

l’aide de vecteurs courts

12.3.1 Approximation rationnelle

a
Une approximation π ≈ b, b ≤ B, correspond à une petite
valeur bπ − a.
On pose le réseau

Algorithme 12.3.1 code gp

A = [ -10^4, round(10^4*Pi) ; 0 , 1 ]

97
Chapitre 12. Réseaux et cryptographie

Algorithme 12.3.2 code gp

qflll(A)

12.3.2 Relations de dépendance linéaires

Algorithme 12.3.3 code gp

P = 1+3*x-7*x^2+3*x^4+x^5
r = polrootsreal(P)[1]

Supposons qu’on ne connaisse pas P( x ), comment retrouver ce

polynôme à partir d’une approximation d’une racine ?

Algorithme 12.3.4 code gp

B=10^3;
A = matconcat([matid(5),0;vector(5,k,round(B*r^(k-1))),round(B*r^5)])

Le réseau obtenu contient déjà de petits vecteurs, car r < 1.

Si on fait le même jeu avec −1/r > 1, on obtient de grandes
valeurs en dernière coordonnée, ce qui force un petit vecteur
(dont on sait qu’il existe) à l’annuler.
On reconnaı̂t bien le polynôme (réciproque) comme plus court
vecteur.

12.3.3 Attaque de Wiener

La relation ed√− kϕ(n) = 1 implique que ed − kn = 1 − k (n −

ϕ(n)) = O(k n), avec k < d.
√
On considère le réseau engendré par v1 = (e,√ n) et
√ v2 =
(n, 0), alors le vecteur w = dv1 − kv2 = (O(k n), d n) est
√ 3
de norme ‖w‖ = O(d n), et le réseau de volume n 2 .
1
Si d = O(n 4 ), alors w est un petit vecteur du réseau.

98
12.4. Bases

Algorithme 12.3.5 code gp

r = -1/r;
B=10^3;
A = matconcat([matid(5),0;vector(5,k,round(B*r^(k-1))),round(B*r^5)])

Algorithme 12.3.6 code gp

qflll(A)

12.4 Bases

L’espace des réseaux de Rn est donc le groupe Gln (R)/Gln (Z)

(bases modulo changement de base).
Définition 12.4.1. Si Λ ⊂ Zn est un réseau entier, la forme normale
de Hermite est une base bien définie du réseau.

On a unicité de cette base, mais d’un point de vue

géométrique elle est catastrophique : le domaine fondamental
est complètement applati, les vecteurs de la base sont gigan-
tesques.
Il existe toujours une base dont le premier vecteur est le plus
court vecteur, et il existe des bases

12.5 SVP, CVP

Définition 12.5.1. On appelle Shortest Vector Problem le problème

de déterminer le plus court vecteur d’un réseau, et Closest Vector
Problem celui de déterminer le vecteur du réseau le plus proche d’un
point de Rn .

Ce sont deux problèmes très durs dès que le réseau n’a pas de
structure particulière et que la dimension augmente.
Une bonne base contient le plus petit vecteur, et

99
Chapitre 12. Réseaux et cryptographie

Algorithme 12.3.7 code gp

gp > lindep([1,Pi,Pi^2,Pi^3],5)
%6 = [19, -15, -16, 6]~
gp > 19 - 15*Pi-16*Pi^2+6*Pi^3
%7 = 9.9860522284574566383655397409785263529 E-5

Pour résoudre le CVP, on a besoin d’une base la plus orthogo-

nale possible.
Soit v1 le plus court vecteur du réseau, alors on peut disposer
des boules de diamètre ‖v1 ‖ aux points du réseau qui sont tan-
gentes : un réseau donne un empilement de sphères.

12.6 Réduction

Définition 12.6.1. Une base d’un réseau est une base en tant que Z-
module. Deux bases d’un réseau diffèrent par un élément de Gln (Z).
Exemple 12.6.2. Le réseau Z2 a pour base v1 = (4, 3) et v2 =
(3, 2).
La réduction consiste à obtenir la base la plus agréable possible
pour un réseau. Une ≪bonne base≫ est
— formées de vecteurs courts
— qui sont aussi orthogonaux que possible, (c’est-à-dire
que les angles sont minorés).
L’intérêt de ce second critère est que les courts vecteurs du
réseau aient de petits coefficients sur la base, et que le domaine
fondamental contienne la plus grande boule possible.
Attention, quand la dimension augmente la géométrie est
pleine de surprises :
— la famille libre des plus courts vecteurs n’est pas tou-
jours une base
— la plus petite base pour l’ordre lexicographique sur les
normes (base de Hermite) est en général loin d’être or-
thogonale.

100
12.6. Réduction

12.6.3 Cas de la dimension 2

Par exemple, pour un réseau de R2 , si l’on prend pour v1 le plus

petit vecteur et qu’on renormalise en posant v1 = (0, 1), v2 est
en dehors du cercle unité, et par translations de v1 on peut le
choisir dans la bande −1/2, 1/2.
Cela signifie que
— le projeté orthogonal
√ √ 2
v⊥ de v2 sur ⟨v1 ⟩⊥ est de norme
supérieure à 23 = 23 ‖v1 ‖
— la composante de v2 sur v1 , c’est-à-dire le coefficient µ
de l’égalité v2 = v2⊥ + µv1 , est inférieure à 1/2.

12.6.4 Réduction de Hermite

En généralisant on obtient la définition suivante

Définition 12.6.5. Une base (α, β)-réduite d’un réseau Λ est une
base v1 , . . . vn telle que pour tout i, si on note vi⊥ la projection de vi
sur ⟨vi+1 , . . . vi+n ⟩⊥ , alors
— vi⊥+1 ≥ α vi⊥
— en écrivant vi = vi⊥ + ∑ j<i µi,j v⊥ j on a µi,j ≤ β.

La traduction en termes de matrices est plus simple à com-

prendre : soit v1 , . . . vn une base et (v1⊥ , . . . v⊥
n ) son orthogona-
lisée de Gram-Schmidt.
En disposant les vecteurs en colonne, le procédé d’ortogonali-
sation de Gram-Schmidt s’écrit
 1 ? ? 
| |
  
| |
 v1 · · · v n  =  v ⊥ · · · v ⊥  .. 
1 n  . ?
| | | | 1

où les coefficients ? de la matrice de droite sont les compo-

⟨vi⊥ ,v j ⟩
santes de projection 2 .
‖vi⊥ ‖2

101
Chapitre 12. Réseaux et cryptographie

Le critère de β-reduction consiste simplement à prendre les co-

efficients |?| ≤ 21 , ce qui est trivial par opérations sur les co-
lonnes.
Par ailleurs, en notant D la matrice diagonale ( vi⊥ )i , la ma-
trice des vi⊥ s’écrit KD, où K ∈ On (R) est la matrice de la base
vi⊥
orthonormale di .

Le critère de réduction α consiste à imposer que la diagonale D

soit ≪pseudo-croissante≫ de raison au moins α.
On obtient donc le théorème de Hermite d’existence d’une base
réduite
Théorème 12.6.6. Soit
  
 1 ? ? 
Tβ =  1 ? , |?| ≤ β
1
 

l’ensemble des matrices triangulaires supérieures bornées par β, et

  
 d1
 

Dα = 
 . ..  , di+1 ≥ αdi , 1 ≤ i < n

 
dn
 

l’ensemble des matrices diagonales α-échelonnées.

√
3
Si α ≤ 2 et β ≥ 21 , alors

Gln (R) ⊂ On (R) Dα Tβ Gln (Z).

En d’autres termes, tout réseau possède une base α, β-réduite.

Démonstration. La démonstration, dans les premiers para-

graphes de [Borel-IntroGroupesArithmetiques], est celle que
l’on va donner de l’algorithme LLL ci-dessous,

102
12.6. Réduction

Une base réduite au sens de Hermite n’est pas unique, mais elle
se calcule en temps polynomial : c’est l’algorithme appelé LLL.
Théorème 12.6.7. Soit V = (v1 , . . . vn ) une base de Rn , on
considère la procédure suivante :
— calculer la base orthogonale v1⊥ , . . . v⊥
n
— ajuster chaque v j par une combinaison entière des vi , i < j
⟨vi⊥ ,v j ⟩
pour que − β < ? = 2 ≤ β
‖vi⊥ ‖
— vérifier pour i = 1, . . . n − 1 que vi⊥+1 ≥ α vi⊥ , sinon
échanger
√
vi et vi+1 et reprendre au début.
3
Si α ≤ 2 − e et β ≥ 12 , cette procédure termine en un nombre
d’opérations polynomial en n, 1e et produit une base α, β réduite.

Démonstration. Il suffit de que l’on réalise un nombre polyno-

mial d’échanges (i, i + 1), on le montre en considérant le vo-
lume du réseau engendré par les i premiers vecteurs v1 , . . . vi .
Après échange des vecteurs i, i + 1, les vecteurs orthogonaux
v1⊥ , . . . vi⊥−1 ne changent pas, tandis que l’on a désormais au
rang i le vecteur ṽi⊥ = vi⊥+1 + ai,i+1 vi⊥ (vi⊥+1 était réduit par rap-
port à l’ancien vi⊥ , ce n’est plus le cas).
Le volume du réseau engendré par les i premiers vecteurs est
∏ j ≤i v ⊥
j . Lors de l’échange, le carré du volume décroı̂t d’un
2
v˜i⊥
2 1
facteur 2 ≤ α + 4 < 1 (on utilise l’orthogonalité pour
‖vi⊥ ‖
développer la norme).
Puisque le réseau est discret, il ne peut y avoir qu’un nombre
logarithmique d’échange sur chaque indice i, d’où la terminai-
son et la complexité.

La traduction matricielle est la suivante

— on part d’une matrice V ∈ Gln (R)

103
Chapitre 12. Réseaux et cryptographie

— calculer l’orthogonalisation V = V ⊥ A, A trian-

gulaire supérieure, ainsi que d = ( vi⊥ ).
— calculer U ∈ Gln (Z) telle que AU ait des coeffi-
cients |?| ≤ β
— si il existe i tel que di+1 ≤ αdi , échanger
les colonnes i et i + 1 de U recommencer en
remplaçant V par VU.
Retourner √la base VU.
Pour α < 23 et β > 12 on a un algorithme de calcul
polynomial.

Démonstration. Le principe : Si v1 , . . . vn est une base, on

considère son orthogonalisée de Gram-Schmidt v1 , . . . vn et on
se ramène en décalant vi d’une combinaison de v j , j < i à des
coordonnées ai , j = ⟨vi , v j ⟩ ≤ β. On vérifie la condition α, s’il
existe i tel que vi + 1 < α ‖vi ‖ on échange les deux vecteurs
et on recommence depuis le début.
Théorème : l’algorithme termine en temps polynomial.

En pratique, rendre l’algorithme efficace est un sujet de re-

cherche complexe.
Théorème 12.6.8. Les bases réduites satisfont
n ( n −1) 1
‖vi ‖ ≤ 2 4(n−i+1) Vol (Λ) n−i+1
en particulier
n −1 1
‖ v1 ‖ ≤ 2 4 Vol (Λ) n

à comparer avec la borne de Minkowski

1
Vol (Λ)

n
‖ w1 ‖ ≤ 2
Vn

Un des buts de la théorie est d’écrire des

104
12.7. Cryptographie et réseaux

12.7 Cryptographie et réseaux

— Les cryptosystèmes construits à partir de réseaux : uti-

lisent en général un problème CVP, facile à résoudre si
on a une bonne base (clef privée) et impossible avec une
mauvaise base (clef publique).
Un message est un petit vecteur. Il est dans le domaine
fondamental d’une bonne base, mais pas dans celui
d’une mauvaise. On chiffre et déchiffre en transmettant
l’image du vecteur dans le domaine fondamental.
— Les cryptosystèmes attaqués via les réseaux : sac à dos,
Coppersmith

12.8 Le cryptosystème Sac à Dos

On appelle sac à dos le problème combinatoire suivant : soit c

un entier, la capacité du sac, et a1 , . . . an des entiers positifs. On
cherche à écrire c = ∑ ei ai pour des coefficients ei ∈ {0, 1}.
C’est-à-dire que l’on veut sélectionner des objets dans un en-
semble qui permettent de remplir exactement le sac-à-dos.
C’est un problème NP-complet.

12.8.1 Cryptosystème de Merkle-Hellman

On prend une suite ai dite supercroissante, c’est-à-dire telle que

pour tout i, ai > ∑ j<i a j .
Dans ce cas le problème de sac-à-dos se résout trivialement par
approche gloutonne (on a mn = 1 ⇔ c ≥ an , puis mn−1 = 1 ⇔
c − mn an ≥ an−1 , etc.)
On mélange cette suite de poids ai comme suit : on choisit un
module N > ∑ ai , un élément aléatoire K ∈ (Z/NZ)× , et on
pose bi = Kai mod N.

105
Chapitre 12. Réseaux et cryptographie

— La clef publique est la suite de poids modifiés bi , de lon-

gueur n.
— On chiffre un message m ∈ {0, 1}n par l’entier c =
∑ m i bi .
— La clef privée est la suite supercroissante ai , et les entiers
N, K.
— Pour déchiffrer, on se ramène au problème facile en po-
sant K −1 c mod N = ∑ mi ai mod N, ce qui permet de re-
trouver les mi .

12.8.2 Attaque LLL

La stratégie habituelle est de trouver le vecteur mi comme vec-

teur court (m0 , . . . mn , 0) du réseau engendré par les colonnes
de
 
1 0 0 0 0
.. 
 0 ...

 0 0 . 
A=  .. .. 
0 0 . 0 . 

0 0 0 1 0
b1 · · · · · · bn −c
Toutefois, il est probable que ce réseau contienne beaucoup
d’autres vecteurs ( x1 , . . . xn , e) avec ∑ xi bi = c + e. Pour ne
sélectionner que des solutions√atteignant l’égalité ∑ xi bi = c
on met un grand poids B ≈ n à la dernière ligne, de sorte
qu’un vecteur ne satisfaisant pas l’égalité est automatiquement
grand.
 
1 0 0 0 0
 .. .. 
 0
 . 0 0 . 
AB =  .. .. 
 0 0 . 0 . 

 0 0 0 1 0 
Bb1 · · · · · · Bbn − Bc
Un autre problème est que contrairement à la solution du sac à
dos, les courts vecteurs s’autorisent à prendre indifféremment

106
12.9. Algorithme de Coppersmith

des coefficients positifs et négatifs.

Une astuce pour privilégier les coefficients 0 et 1 consiste à
considérer le réseau

− 12
 
1 0 0 0
 .. .. 
 0 . 0 0 . 
′
 
AB =   .. .. 
 0 0 . 0 . 

 0 0 0 1 − 12 
Bb1 · · · · · · Bbn − Bc

Le vecteur correspondant à la combinaison de colonnes

(m1 , . . . mn , 1) d désormais pour composantes (m1 − 12 , . . . mn −
1 √
2 , 0) de norme n/2 puisque chaque composante vaut ± 12 .
On obtient un résultat similaire en prenant le réseau

n + 1 −1 −1 −1 −1
 
 .. .. 
 −1 . −1 −1 . 
′
 
AB =   .. .. 
 − 1 − 1 . 0 . 

 −1 −1 −1 n + 1 −1 
Bb1 · · · · · · Bbn − Bc

et une constante B > n.

On appelle densité du problème la quantité

N
d=
log2 bn

12.9 Algorithme de Coppersmith

Cet algorithme permet de déterminer les ≪petites racines≫ de

polynômes de ≪petit degré≫ modulo un entier n non premier.
Remarque 12.9.1.

107
Chapitre 12. Réseaux et cryptographie

— Il est facile de trouver les racines modulo p d’un po-

lynôme, en calculant d’abord f 0 = pgcd( f , x p − x ) pour
isoler le facteur scindé modulo p, puis si ce facteur est de
degré > 1 on le décompose en calculant pgcd( f 0 , ( x +
p −1
a) 2 − 1) pour des valeurs aléatoires de a, ce qui sépare
les racines x telles que x + a est un carré (technique de
Cantor-Zassenhaus).
— Tout algorithme permettant de trouver une racine d’un
polynôme modulo n permet de factoriser n (on obtient
en particulier les racines carrées).
La première étape est de montrer qu’il est facile de calculer les
petites racines de polynômes à petits coefficients, puisque ce
sont en réalité des racines dans Z.
Lemme 12.9.2. Soit f ( x ) ∈ Z[ x ] de degré n, si
— f ( x0 ) ≡ 0 mod bm avec | x0 | ≤ X
m
— ‖ f ( xX )‖2 < √b
(n)
alors f ( x0 ) = 0 dans Z.

Démonstration. On applique
√ Cauchy-Schwartz | f ( x0 )| =
∑ ai x0i ≤ ∑ ai X i ≤ n ‖ f ( xX )‖2 < n donc la congruence
à 0 est en réalité une égalité.

Soient maintenant f ( x ) un polynôme dont on sait qu’il a une

racine f ( x0 ) ≡ 0 mod b, où x ≤ X et b est un diviseur de N,
avec b ≥ N β .
b et x0 sont les inconnues, tandis que les paramètres X, N, β
sont connus. Il suffit de déterminer x0 , puisqu’on retrouve en-
suite b en calculant pgcd( f ( x0 ), N ).
On se ramène au lemme en déterminant un polynôme g( x )
dont x0 est racine, et qui a de petits coefficients : la stratégie
est de construire un réseau de tels polynômes pour obtenir une
combinaison linéaire petite.

108
12.10. L’attaque ROCA

j
Si f ( x0 ) ≡ 0 mod b, alors N i x0 f ( x0 )k ≡ 0 mod bi+k , de sorte
que les polynômes gi,j ( x ) = N m−i x j f i ( x ) vérifient gi,j ( x0 ) ≡
0 mod bm , ainsi que toute combinaison linéaire.
On considère le réseau engendré par les coefficients des
bm
gi,j ( xX ), s’il possède un vecteur de norme ‖ g‖2 ≤ √ n
, on a
gagné. On choisit X le plus grand possible pour que les bornes
LLL permettent d’obtenir un tel g.
Théorème 12.9.3. Soit N un entier composé possédant un diviseur
b ≥ N β . Soit f ( x ) ∈ Z[ x ] un polynôme unitaire de degré δ. Alors
on peut trouver toutes les solutions x0 de l’équation f ( x ) ≡ 0 mod b
telles que

1 β2 − e
| x0 | ≤ Nδ
2

en temps polynomial en log( N ), δ, 1e .

Démonstration. voir May [MayRSA].

12.10 L’attaque ROCA

Autrement dit, ≪Coppersmith, le retour≫, 2016-2017.

La société Infineon est un poids lourd des semiconducteurs em-
barqués. Elle commercialise des solutions cryptographiques,
par exemple des cartes d’identité numériques sécurisées. À ce
titre, elle a sa propre bibliothèque de cryptographie RSA, très
largement utilisée dans ce contexte.
En 2016 des analystes ont repéré des anomalies statistiques
sur les clefs publiques commercialisées par cette société et
découvert une faille majeure permettant de factoriser les clefs
publiques.

109
Chapitre 12. Réseaux et cryptographie

La seule publication du fait que les clefs n’étaient pas robustes

a permis à d’autres cryptographes de découvrir la faille et re-
constituer l’attaque en quelques jours.

12.10.1 Reconstitution

Quand on génère des premiers RSA, la stratégie est de tirer des

entiers au hasard et de tester leur composition. Pour gagner du
temps, on peut se restreindre à tirer des entiers impairs, puis
non divisibles par 3, etc.
Une stratégie acceptable est de tirer au hasard des entiers ai ̸=
0 mod pi et d’imposer que p soit congru à ai modulo pi , ie à une
valeur A modulo M = ∏ pi .
En effet, le choix a priori de congruences indépendantes ne mo-
difie par la distribution finale, si l’on choisit ces congruences de
manière uniforme et indépendante pour chaque choix de pre-
mier.
En revanche, des versions erronées de cette stratégie seraient
de
— conserver la valeur A entre tirages de premiers distincts
— choisir A directement modulo M par une méthode qui
n’assure pas une distribution uniforme sur (Z/MZ)× .
En observant les clefs Infineon, les cryptographes se sont ren-
dus compte qu’elles n’étaient pas du tout distribuées uni-
formément modulo les petits premiers, ce qui correspond à la
seconde erreur.
La démarche adoptée par les programmeurs d’Infineon est la
suivante : ils prennent un très grand produit de premiers suc-
cessifs M, et cherchent p congru à A = e a mod M où e =
65537 = 216 + 1 est l’exposant de chiffrement, et a est un ex-
posant tiré aléatoirement avant le choix de p.
De cette manière on évite de considérer les entiers divisibles
par de petits nombres premiers, ainsi que ceux qui sont congrus
à 1 modulo e.

110
12.10. L’attaque ROCA

Concrètement, pour un premier p = kM + (e a mod M ) de 256

bits, le module M est de 219 bits (produit des 39 premiers
inférieurs à 167), ainsi que l’exposant a, et le multiplicateur k
de 37 bits.
On a bien l’impression que le double choix de k et a se fait dans
un espace de 219 + 37 = 256 bits, mais en réalité le sous-groupe
⟨e⟩ mod M engendré par e est de taille au plus ppcm p≤167 ( p −
1) ≈ 261 dans (Z/MZ)× qui n’est pas du tout cyclique. On
choisit donc p dans un sous-ensemble minuscule.

√ connaı̂t a c’est facile, on connaı̂t

Comment factoriser ? si l’on
alors p mod M avec M > N, ce qui permet d’appliquer l’at-
taque de Coppersmith sur les bits de poids faible de p.
On ne connaı̂t pas a, et l’attaque sur a est de type force brute,
mais avec quelques astuce.
D’abord l’espace de recherche (60 bits) est grand,
√mais puis-
qu’on peut appliquer Coppersmith tant que M > N, on peut
artificiellement prendre pour M un produit minimal de pre-
mier, ce qui diminue la taille du groupe ⟨e mod M⟩.
Par exemple, M′ = ∏ p≤103 p a plus de 128 bits, et e est d’ordre
λ < 239 modulo M′ . Cela vaut aussi
√ la peine de chercher un
sous-produit différent ∏i∈ I pi > N qui minimise l’ordre du
groupe ppcmi∈ I ( pi − 1).
Ensuite, puisque les deux facteurs p ≡ e a mod M′ et q ≡
eb mod M′ sont construits de la même manière, il suffit de
déterminer a ou b modulo λ, sachant que l’on connaı̂t la somme
a + b puisque N ≡ e a+b mod M′ . L’intervalle [ a+2 b , a+b2+λ ]
contient a ou b.
[Link] media/public/papers/
nemec roca ccs17 [Link]

111
Chapitre 12. Réseaux et cryptographie

112
CHAPITRE 13
Codes linéaires

Remarque 13.0.1. On peut se passer de linéarité pour beaucoup

d’énoncés, mais tous nos codes seront linéaires.

13.1 Premiers exemples

code de parité (claviers) : soit ( x1 , . . . x7 ) ∈ F72 , on ajoute un 8è

bit de sorte que ∑ xi = 0. On peut détecter une erreur.
code par triple vérification : à ( x1 , x2 , x3 ) on ajoute les bits ( x2 +
x3 , x1 + x3 , x1 + x2 ). On peut à présent corriger une erreur.

13.2 Définition

On considère l’alphabet Fq , et on se place dans l’espace vecto-

riel Fnq des mots de longueur n.
Définition 13.2.1. Un code linéaire C de longueur n est un sous-
espace vectoriel de Fnq . Si C est de dimension k, on dit que C est un
[n, k]-code.
Exemple 13.2.2.
— le code C1 = {( x1 , . . . x7 , x8 ), ∑ xi = 0} ∈ F82 est un [8, 7]-
code.

113
Chapitre 13. Codes linéaires

— le code C2 = {( x1 , x2 , x3 , x2 + x3 , x1 + x3 , x1 + x2 )} ∈ F62
est un [6, 3]-code.

13.3 Distance

Définition 13.3.1. Pour x, y ∈ Fnq , on pose

d( x, y) = #{i, xi ̸= yi }

le nombre de composantes par lesquelles x et y diffèrent. C’est une

distance sur Fnq , appelée distance de Hamming.

On corrige au plus proche voisin pour la distance de Hamming.

Soit c ∈ C un mot de code transmis, et y le mot reçu. On note
c′ ∈ C le mot de code distinct de c le plus proche de y. Alors
— si d(c′ , y) > 0, on peut détecter l’erreur (il y a
nécessairement eu une erreur puisqu’on n’obtient pas
un mot de code)
— si d(c′ , y) > d(c, y), la correction au plus proche est cor-
recte (on retourne vers c et non pas vers un autre mot
c′ ).
Définition 13.3.2. On appelle distance minimale de C l’entier

d(C ) = min d(c, c′ ), c ̸= c′ ∈ C

En particulier, on a le lien suivant entre distance minimale et

capacité de correction.
Proposition 13.3.3.
— Si d(C ) ≥ t + 1, on peut détecter jusqu’à t erreurs
— Si d(C ) ≥ 2t + 1, on peut corriger jusqu’à t erreurs.

Démonstration. Par inégalité triangulaire, d(c′ , y) ≥ d(c, c′ ) −

d(c, y), or d(c, c′ ) ≥ d(C ) et d(c, y) ≤ t.
Dans le premier cas on a bien d(c′ , y) ≥ d(C ) − t > 0.

114
13.4. Poids

Dans le second, d(c′ , y) − d(c, y) ≥ d(C ) − 2t > 0.

Un code de longueur n, dimension k et distance minimale d est

appelé un [n, k, d]-code.
Exemple 13.3.4.
— C1 est un [8, 7, 2]-code.
— C2 est un [6, 3, 3]-code.

13.4 Poids

Pour x ∈ Fnq , on définit le poids de x

w( x ) = #{i, xi ̸= 0} = d( x, 0)

alors pour tous x ̸= y on a

d( x, y) = w( x − y).

En particulier, si C est un code linéaire, il est stable par

différence donc

d(C ) = min {w(c)}

c∈C,c̸=0

115
Chapitre 13. Codes linéaires

116
CHAPITRE 14
Représentations matricielles

Soit C un [n, k]-code. On a deux manières de représenter le

sous-espace vectoriel C
— via une base formée de k vecteurs
— via un système de n − k équations linéaires
Dans tout ce qui suit, on représente les vecteurs en ligne.
Définition 14.0.1. On appelle matrice génératrice de C une matrice
G ∈ Mk,n (Fq ) dont les lignes forment une base de C.
n o
En d’autres termes, C = Fkq G = mG, m ∈ Fkq .

Définition 14.0.2. On appelle matrice vérificatrice de C une matrice

V ∈ Mn−k,n (Fq ) telle que C = ker(V ).

En d’autres termes, c ∈ C si et seulement si V t c = 0.

117
Chapitre 14. Représentations matricielles

14.1 Exemples

Pour le code de parité C1 , on obtient G1 en prenant l’image de

la base canonique.
 
1 0 0 0 0 0 0 1
0 1 0 0 0 0 0 1
 
0 0 1 0 0 0 0 1
 
G1 = 0 0 0 1 0 0 0 1
0 0 0 0 1 0 0 1
 
0 0 0 0 0 1 0 1
0 0 0 0 0 0 1 1

V1 est la matrice de l’équation ∑ xi = 0 qui définit x8

V1 = 1 1 1 1 1 1 1 1

Le code par triple vérification C2 est défini par les équations

x4 = x2 + x3 , x5 = x1 + x3 , x6 = x1 + x2 , d’où la matrice
vérificatrice V2
 
0 1 1 1 0 0
V2 = 1 0 1 0 1 0
1 1 0 0 0 1

tandis qu’une génératrice est

 
1 0 0 0 1 1
G2 = 0 1 0 1 0 1
0 0 1 1 1 0

14.2 Formes systématiques

Une matrice génératrice de la forme

G = ( Ik A) , A ∈ Mk,n−k (Fq )

118
14.3. Vérificatrice et distance minimale

est dite sous forme systématique : cela correspond au fait que

le code consiste à concaténer des bits de contrôle au message
initial.
Proposition 14.2.1. Si G = ( Ik A) est génératrice du [ N, k]-code C,
alors

V = −t AIn−k

est vérificatrice de C

Démonstration. en effet elle est de rang n − k et vérifie G t V = 0.

Proposition 14.2.2. Quitte à changer l’ordre des indices, on peut

toujours déterminer une matrice génératrice sous forme systématique.

Démonstration. On réalise un pivot de Gauss sur les lignes, en

s’autorisant à décaler les colonnes.
Géométriquement, cela correspond au fait qu’il existe un
supplémentaire F de C engendré par des vecteurs de la base
canonique qu’on peut renuméroter en−k+1 , . . . en , auquel cas C
est engendré par les projetés de e1 , . . . ek parallèlement à F.

14.3 Vérificatrice et distance minimale

Proposition 14.3.1. Soit C un code de matrice vérificatrice V, et soit

d > 0 minimal tel qu’il existe d colonnes de V liées. Alors d(C ) = d.

Démonstration. C’est une reformulation : ( x1 , . . . xn ) ∈ C ssi

Vx = ∑ xi Vi = 0, donc C a un mot de poids d s’il existe d
colonnes liées.

119
Chapitre 14. Représentations matricielles

Remarque 14.3.2. Comme tout ensemble de plus de n − k co-

lonnes est nécessairement lié dans Fnq −k , on retrouve en parti-
culier la borne de Singleton.

120
CHAPITRE 15
Bornes, décodage

15.1 Bornes simples

On ne peut pas espérer construire des codes qui transmettent

efficacement l’information tout en permettant de corriger un
nombre arbitraire d’erreurs.
Les deux bornes élémentaires suivantes donnent des limites
précises à ce qu’on peut espérer.
Proposition 15.1.1. Soit C un [n, k, d]-code, alors d ≤ n − k + 1.

Démonstration. Si l’on oublie d − 1 coordonnées, on obtient

une projection de C sur Fnq −d+1 qui est injective (sinon deux
mots seraient à distance ≤ d − 1), donc la dimension de l’espace
de départ vérifie k ≤ n − d + 1.

On appelle
— taux d’information le quotient τI = k/n (proportion
d’un mot codant effectivement l’information, le reste est
de la redondance)
— taux de correction le quotient τC = d/n.
L’inégalité de Singleton se lit

1
τI + τC ≤ 1 + .
n

121
Chapitre 15. Bornes, décodage

Par exemple, le code par triple répétition a un taux d’informa-

tion τI = 3/6 = 0.5, et un taux de correction τC = 0.5.
Proposition 15.1.2. Si C est un [n, k]-code t-correcteur sur Fq , on
a
t
n
#B(0, t) = ∑ ( q − 1)i ≤ q n − k
i =0
i

Démonstration. Si C est t-correcteur les boules centrées en

chaque mot sont disjointes, on évalue leur cardinal.

Définition 15.1.3. Soit C un [n, k, d] code.

— si C atteint l’égalité de Singleton d = n − k + 1, on dit que C
est MDS (maximum distance separable).
— si C atteint l’égalité de Hamming (où d = 2t + 1), on dit que
C est (t-correcteur) parfait.

15.2 Bons codes

15.2.1 Codes parfaits

On construira les codes de Hamming Hr (q), qui sont des [qr −

1, qr − r − 1, 3] codes pour r ≥ 2. Ils ne sont pas MDS pour
r > 2. En revanche, ils sont parfaits.
On construira aussi les codes de Golay G11 , un [11, 6, 5]-code
sur F3 , et G23 , un [23, 12, 7]-code sur F2 . Ils sont parfaits, res-
pectivement 2 et 3-correcteurs (mais pas MDS).
Mais la recherche de codes parfaits s’avère peu fructueuse
Théorème 15.2.2. Les seuls codes parfaits sont les codes de Ham-
ming Hr (q) et les deux codes de Golay G11 et G23 .

122
15.3. Décodage des codes linéaires

15.2.3 Codes MDS

De ce côté là, il y en a beaucoup.

Mentionnons la construction suivante (codes de Goppa) : on
prend n éléments distincts a1 , . . . an ∈ Fq , et pour k < n on
considère le morphisme d’évaluation

(Fq [ x ])deg<k → Fnq

φ:
P( x ) ↦ → ( P ( a1 ), . . . P ( a n )

Il est injectif, et C = Im(φ) est un [n, k]-code.

En outre, un polynôme de degré < k a au plus k − 1 racines,
donc les mots c ∈ C ont un poids w(c) ≥ n − (k − 1) = n − k +
1.
La borne de Singleton donne l’inégalité inverse, donc la dis-
tance est exactement n − k + 1 et C est un code MDS.
En pratique, on prend n = q (le plus grand possible).
Remarque 15.2.4. Si on prend n − 1 points les éléments de
F×
q , on obtient les codes de Reed-Solomon, que l’on verra aussi
comme codes cycliques.

15.3 Décodage des codes linéaires

15.3.1 Effacements

S’il n’y a pas eu d’erreur, et que C est un code de distance d,

on peut décoder un mot en oubliant d − 1 coordonnées, par in-
version d’un mineur de la matrice génératrice (ils sont en effet
tous inversibles tant qu’on sélectionne moins de d colonnes).

123
Chapitre 15. Bornes, décodage

15.3.2 Erreurs : le syndrome

Si C est un [n, k]-code linéaire de matrice vérificatrice V, et si

x ∈ Fnq , on appelle syndrome de x le vecteur

s( x ) = V t x = (∑ xi Vi ) ∈ Fnq −k
i

où l’on note Vi la colonne i de V.

Proposition 15.3.3. Le syndrome s( x ) est nul si et seulement si
x ∈ C.

Soit C un [n, k, d]-code, et c ∈ C un mot de code émis.

On note y = c + e le mot reçu, e étant l’erreur de transmission,
que l’on suppose de poids w(e) = t < 2d .
Proposition 15.3.4. On a s(y) = s(e), le syndrome ne dépend que
de l’erreur.
En outre, s(e) = ∑ ei Vi est une combinaison de t colonnes de V,
— les indices des colonnes sont les indices des positions erronées
— les coefficients des colonnes sont les coefficients du vecteur
d’erreur e.

Ainsi, le syndrome permet de retrouver l’erreur de transmis-

sion
Remarque 15.3.5. Rappelons que la distance minimale d de C
est le plus petit nombre de colonnes de V formant une famille
liée. On ne peut avoir s(e) = s(e′ ) pour e ̸= e′ de poids ≤ t tant
que 2t < d.
On retrouve le fait que C est t-correcteur.
Remarque 15.3.6. Toute famille de plus de n − k + 1 vecteurs
étant liée dans Fnq −k , on a d ≤ n − k + 1, c’est la borne de Sin-
gleton.

124
15.3. Décodage des codes linéaires

15.3.7 Algorithme

Si C est t-correcteur, n
alors le syndromeoest injectif sur la boule
de rayon t, B(0, t) = e ∈ Fnq , w(e) ≤ t .

Si l’on précalcule une table des syndromes s(e) pour tous les
mots e de poids w(e) ≤ t, alors quel que soit le syndrome s(y),
on trouve e de poids w(e) ≤ t tel que s(y − e) = 0 ⇔ y − e ∈ C.
L’algorithme est le suivant
— on calcule le syndrome s(y) ;
— on détermine via la table l’erreur e telle que s(e) = s(y).
— le mot corrigé est c = y − e ∈ C.
Par rapport à un code quelconque, la linéarité a permis cette
phase de précalcul des syndromes, au lieu de devoir parcourir
une boule de rayon t pour chaque mot reçu.

125
Chapitre 15. Bornes, décodage

126
CHAPITRE 16
Constructions

16.1 Codes de Hamming

Ce sont les codes 1-correcteurs parfaits.

Principe : s’il y a une erreur en position i, le syndrome est (pro-
portionnel à) la i-ième colonne de la matrice vérificatrice. Un
code est 1-correcteur si les syndromes sont linéairement dis-
tincts, donc si la matrice vérificatrice est formée de colonnes
linéairement toutes distinctes. Le code de Hamming s’obtient
en prenant les matrices vérificatrices les plus grandes satisfai-
sant cette propriété, c’est-à-dire formées de tous les vecteurs
non nuls à proportionnalité près.
Définition 16.1.1. Soit r ≥ 2, et soit Vr une matrice r × 2r − 1 dont
les colonnes sont tous les vecteurs non nuls de F2r . On appelle code de
Hamming Hr (F2 ) le code de matrice vérificatrice Vr .
Proposition 16.1.2. Hr est un [2r − 1, 2r − r − 1, 3] code linéaire.
C’est un code 1-correcteur parfait.

Démonstration. La distance est au moins 3 car les colonnes

de Vr sont non proportionelles. En outre, on vérifie l’égalité
de Hamming : avec n = 2r − 1 et k = 2n − r − 1, on a
r r
#B(0, 1)#C = (1 + n)(2k ) = 2r 22 −r−1 = 22 −1 = 2n .

127
Chapitre 16. Constructions

Le décodage est particulièrement simple : pour une erreur, le

syndrome est une colonne de Vr , qui indique le bit erroné.
Plus généralement, pour tout corps fini Fq , on construit le code
de Hamming Hr (Fq ) via sa matrice vérificatrice, dont les co-
lonnes forment un ensemble maximal de vecteurs non nuls et
qr −1
deux à deux non colinéaires de Frq . Il y a n = q−1 tels vecteurs,
d’où un code [n, k, 3], qui est à nouveau parfait.
On a en fait la caractérisation :
Théorème 16.1.3. Soit C un code linéaire 1-correcteur parfait sur
Fq . Alors C est un code de Hamming Hr .

Démonstration. En notant #C = qk , on pose r = n − k et

qr −1
on a par égalité de Hamming n = q−1 . Si le code est 1-
correcteur, les colonnes de sa vérificatrices sont non colinéaires,
d’où l’équivalence à Hr .

16.2 Opérations sur les codes

16.2.1 Équivalence

En agissant sur les lignes de la matrice génératrice, on ne

change pas l’espace que ces lignes engendrent : on garde le
même code.
Proposition 16.2.2. Soit C un [n, k]-code, et G une matrice
génératrice de C. Alors les matrices génératrices de C sont exacte-
ment les matrices de la forme AG, pour A ∈ Glk (Fq ).

En revanche, on doit s’interdire de faire des opérations sur les

colonnes, ce qui change la base de l’espace Fnq ambiant, et donc
la distance de Hamming.

128
16.2. Opérations sur les codes

Toutefois, cette distance est préservée si on permute les coor-

données par un élément de Sn . On dira que deux codes sont
équivalents s’ils se déduisent l’un de l’autre par une telle per-
mutation des indices.
On a vu que tout code est équivalent à un code sous forme
systématique.

16.2.3 Codes étendu, raccourci, sous-code pair

L’image d’un code par une application linéaire reste un code,

la somme ou l’intersection de deux codes également.
Soit C un [n, k ]-code sur Fq .
Définition 16.2.4.
— Le sous-code pair de C est le code C0 = {c ∈ C, ∑ ci = 0}. Si
C ̸= C ∘ , C ∘ est un [n, k − 1] code
— Le code étendu est le code

C = ( x1 , . . . xn , xn+1 ), ( x1 . . . xn ) ∈ C, ∑ xi = 0

c’est un [n + 1, k ]-code.
— Le code raccourci en la position n est le code
{(c1 , . . . cn−1 , cn ) t.q. (c1 , . . . cn−1 , 0) ∈ C } (attention,
ce n’est pas l’image de la projection, c’est la projection du
noyau)
Proposition 16.2.5. Si q = 2 et C ∘ ̸= C, C ∘ est un [n, k − 1, d]
code pour d pair, et un [n, k − 1, d + 1] code pour d impair.

Démonstration. On a d(C ) ≤ d(C0 ) ≤ d(C ) + 1. On regarde un

mot de poids minimal.

Pour la dimension du sous-code pair, on utilise ce lemme qu’on

va réutiliser dans le prochain paragraphe

129
Chapitre 16. Constructions

Lemme 16.2.6. Soit E un Fq espace-vectoriel de dimension n, et

φ : E → Fq une forme linéaire. Alors
— soit φ est nulle et dim ker(φ) = n
— soit φ est surjective et dim ker(φ) = n − 1.

16.2.7 Code orthogonal

On considère le ≪produit scalaire usuel≫ x, y ↦→ ⟨ x, y⟩ = x t y =

∑ xi yi qui est une forme bilinéaire symétrique non-dégénérée
sur Fnq .
C’est-à-dire que l’on a les formules
— ⟨ x + y, z⟩ = ⟨ x, z⟩ + ⟨y, z⟩
— ⟨ x, y⟩ = ⟨y, x ⟩
— ⟨ ax, y⟩ = a⟨y, x ⟩
— ∀y, ⟨ x, y⟩ = 0 ⇒ x = 0
Remarque 16.2.8. Ce n’est pas un produit scalaire, l’axiome
de définition ⟨ x, x ⟩ = 0 ⇒ x = 0 est en général faux, et la
positivité ⟨ x, x ⟩ ≥ 0 n’a pas de sens sur Fq .
Définition 16.2.9. Si C est un [n, k]-code, on définit son orthogonal
n o
C ⊥ = x ∈ Fnq , ∀c ∈ C, ⟨ x, y⟩ = 0

c’est un code (sous-espace vectoriel) de dimension n − k.

Démonstration. En effet, si g1 , . . . gk forme une base de C, C ⊥

est l’intersection des noyaux des k formes linéaires x ↦→ ⟨ x, gi ⟩
qui sont indépendantes puisque le produit est non dégénéré.
En d’autres termes, c’est le noyau de l’application surjective
Fq → Fkq
n

x ↦→ ⟨ x, g1 ⟩, . . . ⟨ x, gk ⟩

Ainsi, C ⊥ est un [n, n − k]-code, et on a

c ∈ C ⇔ ∀ x ∈ C ⊥ , ⟨ x, c⟩ = 0

130
16.2. Opérations sur les codes

Remarque 16.2.10. Une matrice vérificatrice d’un code est

génératrice de son orthogonal, et vice-versa.
Attention, à la différence des espaces euclidiens (vrai produit
scalaire), on n’a pas de décomposition Fnq = C ⊕ C ⊥ , bien au
contraire on a la possibilité suivante :
Définition 16.2.11. Soit C un [n, k ]-code, on dit que C est auto-
orthogonal si C = C ⊥ . Cela impose que n = 2k soit pair.

Le cas des codes MDS est particulièrement intéressant :

Proposition 16.2.12. L’orthogonal d’un code MDS est MDS.

Démonstration. Soit G une matrice génératrice d’un [n, k, n −

k + 1] code. Par hypothèse, les mots de codes xG ont au plus k −
1 coordonnées nulles, donc les lignes de toute matrice extraite
k × k de G sont libres, donc la même chose est vraie de leurs
colonnes, donc toute famille de k colonnes de G est libre. Or
G est la matrice vérificatrice de l’orthogonal, qui est donc de
distance ≥ k + 1 = n − (n − k) + 1.

16.2.13 Sommes de codes

C’est une manière pratique de construire des codes de grande

distance, reposant sur le lemme suivant
Proposition 16.2.14. Soit C1 et C2 des codes de paramètres
[n, k1 , d1 ] et [n, k2 , d2 ]. Alors le code

C1 ? C2 = {(c1 , c1 + c2 ), (c1 , c2 ) ∈ C1 × C2 }

est un [2n, k1 + k2 , min(2d1 , d2 )] code.

Démonstration. Soit c = (c1 , c1 + c2 ) un mot non nul. Si c2 = 0,

w(c) = 2w(c1 ) ≥ 2d1 . Si c2 ̸= 0, w(m) = w(c1 ) + w(c1 + c2 ) ≥
w(c1 ) + w(c2 ) − w(c1 ) = w(c2 ) ≥ d2 (inégalité triangulaire

131
Chapitre 16. Constructions

w( a + b) ≥ w( a) − w(b), qui correspond au fait que pour an-

nuler une coordonnée de c2 il faut qu’elle soit non nulle sur c1 ).
Et il existe des mots de poids 2d1 et d2 .

Ainsi, à partir des codes pleins [n, n, 1] et de répétition [n, 1, n]

on peut construire des codes intéressants, comme les codes
[32, 6, 16] (grande distance) ou [32, 16, 8] (taux d’information
raisonnable).

132
CHAPITRE 17
Codes cycliques

17.1 Rappels sur les corps finis

— Pour tout nombre premier p, et tout entier n ≥ 1 il existe

un unique corps fini de cardinal q = pn , le corps des
n
racines de x p − x. On le note Fq .
— On peut le construire comme extension algébrique de F p
par un polynôme irréductible de degré n, et deux telles
constructions sont isomorphes.
— Le groupe multiplicatif F*q est cyclique.
— L’application x ↦→ x p est F p -linéaire, on l’appelle mor-
phisme de Frobenius.
n
— x p − x est scindé sur Fq , et se factorise sur F p en produit
de tous les irréductibles de degré d | n.

17.2 Codes cycliques

Note : Attention : à partir de ce chapitre, on va noter les indices

en partant de 0, comme en programmation. Les mots de code
de Fnq seront de la forme (c0 , . . . cn−1 ).

133
Chapitre 17. Codes cycliques

Définition 17.2.1. Le groupe des automorphismes de C est le sous-

groupe de Sn des permutations d’indices qui stabilisent C.

σ ∈ Aut(C ) ⇔ ∀(c0 , . . . cn−1 ) ∈ C, ( xσ(0) , . . . xσ(n−1) ) ∈ C

Définition 17.2.2. C est un code cyclique si le n-cycle σ =

(0, 2, . . . n − 1) appartient à Aut(C ), c’est-à-dire si

c = ( c 0 . . . c n −1 ) ∈ C ⇒ σ ( c ) = ( c n −1 , c 0 , . . . c n −2 ) ∈ C

(tout décalage circulaire reste dans le code)

Exemple 17.2.3. pour c = (1, 0, 0, 1, 0, 1), le décalé σ(c) est
(1, 1, 0, 0, 1, 0).

17.2.4 Formalisation algébrique

On identifie Fnq au quotient Fq [ x ]/( x n − 1), par

n −1
c( x ) = ∑ ci xi ↦→ (c0 , . . . cn−1 ) ∈ Fnq .
i =0

Par cette identification, une multiplication donne un décalage

n
x × c( x ) ≡ ∑ c i −1 x i ↦ → ( c n −1 , c 0 , . . . c n −2 ) = σ ( c )
i =1

de sorte qu’un code C est cyclique s’il correspond

— à un sous-espace vectoriel de Fq [ x ]/( x n − 1) (code)
— qui est stable par multiplication par x (cyclique)
c’est-à-dire un idéal de Fq [ x ]/( x n − 1).
Proposition 17.2.5. Les idéaux de Fq [ x ]/( x n − 1) sont les quo-
tients des idéaux de Fq [ x ] qui contiennent x n − 1. Ils sont de la forme
⟨ g( x )⟩, où g( x ) est un diviseur unitaire de x n − 1.
Exemple 17.2.6. On sait que g( x ) = x3 + x + 1 divise x7 − 1
sur F2 . Le code de Hamming H1 = ⟨ x3 + x + 1⟩ a pour matrice

134
17.2. Codes cycliques

génératrice
 
1 1 0 1 0 0 0
0 1 1 0 1 0 0
 
0 0 1 1 0 1 0
0 0 0 1 1 0 1

on voit bien le caractère cyclique sur les premiers vecteurs.

Un décalage supplémentaire donne la combinaison des trois
premières lignes, et en effet l’égalité x4 g( x ) = g( x ) + xg( x ) +
g2 g( x ) correspond à l’égalité g( x )( x4 + x2 + x + 1) ≡ 0 mod
x7 − 1, avec x4 + x2 + x + 1 = ( x + 1)( x3 + x2 + 1).
Théorème 17.2.7. On a équivalence entre
— code cyclique de Fnq
— idéal de Fq [ x ]/( x n − 1)
— diviseur unitaire de x n − 1.
Exemple 17.2.8. Puisque x7 − 1 = ( x + 1)( x3 + x + 1)( x3 + x2 +
1) est la factorisation en irréductibles sur F2 , il existe 23 = 8
codes cycliques de longueur 7 sur F2 .
Ce sont
— ⟨1⟩ = F2 [ x ]/( x7 − 1) = E, le code plein [7, 7, 1] ;
— ⟨ x + 1⟩ = {m( x ), m(1) = 0} = E0 , le code de parité
[7, 6, 2] ;
— ⟨ x3 + x + 1⟩ = H1 , un code de Hamming [7, 4, 3] ;
— ⟨ x3 + x2 + 1⟩ = H2 , également de Hamming ;
— ⟨( x + 1)( x3 + x + 1)⟩ = H10 , un code [7, 3, 4] ;
— ⟨( x + 1)( x3 + x2 + 1)⟩ = H20 , idem ;
— ⟨( x3 + x + 1)( x3 + x2 + 1)⟩ = ⟨ x6 + x5 + · · · + x + 1⟩, le
code de répétition [7, 1, 7] ;
— ⟨ x7 + 1⟩ = {0}, le code nul [7, 0, 0].

135
Chapitre 17. Codes cycliques

^
17.2.9 Polynomes générateurs et vérificateurs

On n’a plus besoin de matrices pour les codes cycliques, la

donnée du générateur de l’idéal suffit.
Définition 17.2.10. Soit C un code cyclique de longueur n.
— On appelle polynôme générateur de C l’unique polynôme uni-
taire g( x ) | x n − 1 qui engendre l’idéal C.
— C est de dimension n − deg( g).
— m( x ) ∈ C ssi g( x ) | m( x ) mod x n − 1.

On peut donc vérifier très simplement l’appartenance d’un mot

au code, en calculant le reste d’une division.
Remarque 17.2.11. Si C est cyclique de longueur n et de
générateur g( x ), tous les polynômes de la forme a( x ) g( x ) sont
également générateurs de l’idéal C ⊂ Fq [ x ]/x n − 1 dès que
a( x ) est inversible modulo x n − 1.
Le polynôme générateur est unique quand on impose le fait de
diviser x n − 1. C’est aussi le polynôme unitaire de plus petit
degré dans C.
Une autre manière de vérifier l’appartenance au code.
Définition 17.2.12. Soit C un code cyclique de longueur n et de
polynôme générateur g( x ). On appelle polynôme vérificateur de C le
polynôme h( x ) tel que g( x )h( x ) = x n − 1.
On a alors

m( x ) ∈ C ⇔ m( x )h( x ) ≡ 0 mod x n − 1.

17.2.13 Code pair

Soit c( x ) = (c0 , . . . cn−1 ) un mot de code. Il est pair si ∑ ci = 0,

c’est-à-dire si c(1) = 0.
Proposition 17.2.14. Un code ⟨ g( x )⟩ est pair si et seulement si
g(1) = 0, si et seulement si x − 1 | g( x ).

136
17.2. Codes cycliques

17.2.15 Code orthogonal

Proposition 17.2.16. Soit la factorisation x n − 1 = g( x )h( x ), avec

deg(h) = k ; on note

h̃( x ) = x k h(1/x ) = ∑ hi x k −i
i

le polynôme réciproque de h( x ).
Alors les codes engendrés par g( x ) et h̃( x ) sont duaux.
En particulier, la matrice génératrice liée à h̃( x ) est une matrice
vérificatrice du code engendré par g( x ).

Démonstration. Le produit scalaire ⟨ g( x ), h̃( x )⟩ = ∑i gi hk−i

est le coefficient de degré k du produit g( x )h( x ), qui est donc
nul. Plus généralement, pour tout décalage e mod n, le pro-
duit ⟨ x e g( x ), x f h̃( x )⟩ = ∑i gi+e hk+e+ f −(i+e) est le coefficient de
degré k + e + f du produit x e g( x ) x f h̃( x ) ≡ 0 mod x n − 1, qui
est également nul. Ce qui conclut.

137
Chapitre 17. Codes cycliques

138
CHAPITRE 18
Distance prescrite, codes BCH

^
18.1 Polynome générateur et racines

On suppose que n est premier à q, et on note α une racine n-

ième primitive de l’unité dans une extension de Fq .
Alors les racines de x n − 1 sont les puissances de α, donc les
racines du polynôme générateur g( x ) sont aussi des puissances
de α.
On a donc une dernière manière de décrire un code cyclique :
k
n les racines α de og( x ), c’est-à-dire par l’ensemble Ig =
par
k ∈ Z/nZ, g(αk ) = 0 .

Cet ensemble n’est pas quelconque : il est stable par l’action du

Frobenius.
Lemme 18.1.1. Soit g( x ) ∈ Fq [ x ]. Alors g(αk ) = 0 ⇒ g(αqk ) =
0.
En particulier, Ig est stable par la multiplication par q.

La réciproque est vraie (un polynôme fixé par le Frobenius est

à coefficient dans Fq ).
Lemme 18.1.2. Soit I ⊂ Z/nZ une partie stable par multiplication
par q, alors g( x ) = ∏k∈ I ( x − αk ) est un polynôme à coefficients dans
Fq qui divise x n − 1.

139
Chapitre 18. Distance prescrite, codes BCH

On a donc une autre manière de chercher les codes cycliques :

déterminer les parties q-stables.
Exemple 18.1.3. Les 3-orbites modulo 8 et les facteurs de X 8 − 1
associés sont

or- polynôme identification

bite
{0} Φ1 = X − 1
{1, 3} P( X ) facteur irréductible de Φ8
{2, 6} Φ4 = X 2 + diviseur de X 4 − 1 mais pas de X 2 −
1 1
{4} Φ2 = X + 1 facteur de X 2 − 1 mais pas de X − 1
{5, 7} Q( X ) facteur irréductible de Φ8

L’orbite {4} correspond à Φ2 = X + 1, et {2, 6} à Φ4 = X 2 + 1.

Les orbites {1, 3} et {5, 7} correspondent aux deux facteurs
irréductibles de Φ8 , soient X 2 − X − 1 et X 2 + X − 1.

18.2 La borne BCH

Théorème 18.2.1. Soit C un code cyclique de longueur n sur Fq ,

engendré par le polynôme g( x ) | x n − 1.
Si g s’annule en r − 1 puissances consécutives de α

g ( α a +1 ) = g ( α a +2 ) = . . . g ( α a +r −1 ) = 0

alors d(C ) ≥ r.

Démonstration. Soit α la racine n-ième permettant d’écrire la

correspondance C − I. Puisque les racines du générateur sont
les αi , i ∈ I, on a
n o
C = m( x ), ∀i ∈ I, m(αi ) = 0

140
18.2. La borne BCH

−1 dj
Soit donc m de poids w(m) ≤ r − 1, on écrit m( x ) = ∑rj= 1 mj x
et l’on a pour 1 ≤ i ≤ r − 1 des équations

r −1
∑ m j αdj (a+i) = 0.
j =1

Ainsi, le vecteur M = (m j αd j a ) est dans le noyau de la matrice

(αd j i ), qui est une matrice de Vandermonde de déterminant non
nul puisque les αd j sont deux-à-deux distincts. Ainsi, M est nul
et m( x ) est le mot nul.

Remarque 18.2.2. Si on ne connaı̂t pas les déterminants

de Vandermonde, il s’agit du déterminant de l’application
d’évaluation des polynômes de degré < r en les points αd j , qui
est bien injective (pas plus de racines que le degré).
Définition 18.2.3. On appelle code BCH de distance prescrite
δ le code engendré par le produit des polynômes minimaux de
α, α2 , . . . αδ−1 .

Il se peut qu’il ait distance strictement supérieure à δ.

Exemple 18.2.4. Pour n = 7 et q = 2, on considère le polynôme
g( x ) = x3 + x + 1. En notant α = x mod g ∈ F8 (qui est une
racine 7-ième de l’unité), g s’annule en α, α2 et α4 . Donc d’après
la proposition la distance est supérieure à 3. Comme g est de
poids 3 on a égalité.
On obient un [7, 4, 3] code : c’est un code de Hamming.
Exemple 18.2.5. On reprend l’exemple sur les facteurs de X 8 −
1 modulo 3.
Notons P( X ) = X 2 − X − 1 et prenons pour α une racine de P
(α3 est donc l’autre racine, tandis que α5 et α7 sont les racines
de Q( X ) = X 2 + X − 1).
Alors en prenant ce α pour expliciter la correspondance, la par-
tie I = {1, 3, 2, 6} contient 3 éléments consécutifs et correspond

141
Chapitre 18. Distance prescrite, codes BCH

au code engendré par P( X )Φ4 ( X ) = ( X 2 − X − 1)( X 2 + 1) =

X 4 − X 3 − X − 1.
C’est un [8, 4]-code de distance d ≥ 4. De plus, le générateur est
de poids 4 donc c’est un [8, 4, 4]-code.
Exemple 18.2.6. Sur F3 , le minimal P( x ) d’une racine 11-ième
de l’unité α s’annule aussi en α3 , α9 , α5 , α4 . Il est de degré 5. Le
minimal de α−1 est P̃( x ).
Ainsi x11 − 1 = ( x − 1) P( x ) P̃( x ), avec P, Q irréductibles de
degré 5. On note G11 = ⟨ P⟩, c’est un code cyclique de distance
au moins 4.
Puisque P( x ) P̃( x ) = Φ11 ( x ), on obtient le diagramme de codes
cycliques suivant.

Voir l’exercice pour finir la démonstration que d( G11 ) = 5.

142
18.3. Code de Reed-Solomon

18.3 Code de Reed-Solomon

Dans le cas où k = Fq , c’est-à-dire si Fq contient les racines

n-ièmes de l’unité, à toute partie I de cardinal n − k corres-
pond un [n, k, n − k + 1]-code. Il n’est pas nécessaire que les
éléments soient consécutifs pour calculer la distance, en effet
un polynôme qui s’annule en n − k points On peut aussi ca-
ractériser les mots de codes par le fait matrice vérificatrice via
les racines de g, si l’on se met dans un corps de décomposition
de g.

18.4 Digression : une interprétation harmo-

nique

On considère le groupe cyclique F×q = ⟨ α ⟩ des racines n-ièmes

de l’unité, pour n = q − 1.
Pour X ⊂ Z/nZ on note L( X ) = f : X → Fq l’espace des

fonctions définies sur X, autrement dit les mots de longueur n

à support dans X. L(Z/nZ) = Fnq est l’espace total.
Alors on a une application de ≪transformée de Fourier≫
L(Z/nZ) → L(Z/nZ)
f ↦→ fˆ
où l’on pose
fˆ(i ) = ∑ αij f ( j).
j

Cette application est bijective, et anti-involutive

b̂f (i ) = − f (−i )

en utilisant
(
n ≡ −1 si i + j = 0 mod n
∑ α (i + j ) k = 0 sinon
k

143
Chapitre 18. Distance prescrite, codes BCH

Le code de Goppa obtenu par évaluation des polynômes de

degré < k en 1, . . . αn−1 est alors

. . . k − 1})
Gk = L({0,\

Le code de Reed-Solomon des mots s’annulant en 1, . . . αn−k est

l’image réciproque
n o
Sk = f , fˆ ∈ L({n − k, . . . n})

soit par inversion on a l’égalité

n o
Sk = fˆ, f ∈ L({0, . . . k }) = Gk

Le principe d’incertitude qui affirme qu’on ne peut être localisé

à la fois en position et en fréquence se traduit par le fait que f
et fˆ ne peuvent tous deux être de petit poids. C’est une situa-
tion idéale pour le codage : la transformée de Fourier répartit
l’information sur toutes les positions.
Les inégalités d’incertitude générales sont trop faibles, mais on
obtient une situation très favorable si l’ordre n est premier (ce
qui boucle joliment ce chapitre avec l’arithmétique).
Proposition 18.4.1. Soit n = 2 p − 1 un nombre premier de Mer-
senne, et f ∈ G (Z/nZ). Alors la somme des poids de f et fˆ est
supérieure à n + 1.

Démonstration. Un théorème de Tao (2005) donne la conclu-

sion sur le support de f et fˆ pour L(Z/nZ) quand n est pre-
mier. Dans le cadre étudié ici, n | q − 1 s’obtient en particulier
pour les nombres premiers de Mersenne.

144
CHAPITRE 19
Décodage des codes BCH

19.1 Approximants de Padé

19.1.1 Introduction : fractions continues

Pour représenter une valeur numérique, on passe par des ap-

proximations rationnelles. On peut
— écrire un développement binaire ou décimal

π ≈ 3.1415926535...

ce qui correspond à prendre des fractions de

dénominateur fixé 10n
31415926535
π≈
1010
— autoriser des dénominateurs quelconques, par exemple
(
π ≈ 227 = 3.142...
π ≈ 315
113 = 3.1415922...
Cette représentation est souvent beaucoup plus économique,
car il existe des fractions qui approximent très bien la valeur.
C’est également très utile dans le cas où on cherche à approcher
une grandeur en minimisant le dénominateur :

145
Chapitre 19. Décodage des codes BCH

— en horlogerie, les rapports se traduisent en engrenages,

on veut minimisant le nombre de dents
— en musique, pour mettre une quinte juste et une octave
dans une gamme tempérée on doit exprimer le rapport
de fréquences α = log(3)/ log(2) comme multiple d’un
intervalle de base. On obtient
— α ≈ 85 : gamme à 5 tons
19
— α ≈ 12 : 12 demi-tons de la gamme tempérée usuelle
84
— α ≈ 53 : 53 commas du piano
Avec des fractions quelconques le travail arithmétique sur les
expressions devient compliqué (additionner des fractions, les
dénominateurs explosent..).
Pour calculer une réduite sous forme de fraction, on a deux
techniques très simples :
— l’algorithme des fractions continues, à partir d’un
développement décimal
— la simplification des fractions par l’algorithme d’Eu-
clide.
Partons de l’approximation π ≈ 314 100 , et cherchons à remplacer
cette fraction par une autre fraction beaucoup plus simple.
Une relation de Bezout entre 314 et 100 donne

314 × 7 − 100 × 22 = −2

d’où
314 22 2
− =−
100 7 700
22 314
La fraction 7 est une excellente approximation de 100 , et donc
de π.
3141592 v
Plus généralement, on cherche 106
− u = e, on écrit l’algo-
rithme d’Euclide

3141592uk + 106 vk = rk

On obtient les lignes :

146
19.1. Approximants de Padé

Algorithme 19.1.1 code gp

A = [3141592,1,0;10^6,0,1]

Algorithme 19.1.2 code gp

A=[0,1;1,-(A[1,1]∖A[2,1])]*A

[141592 1 -3]
[8856 -7 22]
[8752 106 -333]
[104 -113 355]
[ 16 9598 -30153]

La ligne la plus intéressante est celle pour laquelle tous les

termes sont à peu près de la même taille

−3141592 × 113 + 106 × 355 = 104

3141592 355 104
Qui donne 106
− 113 = 113×106
.

On en déduit, puisque π − 3141592

106
≤ 10−6 , que

355 2
π− ≤ 6.
113 10

C’est une excellente approximation, le dénominateur a moitié

moins de chiffres que le dénominateur initial 106 .
De manière générale, cette technique permet
— en partant de 2n chiffres d’une valeur α
— d’obtenir une fraction dont le dénominateur a moins de
n chiffres
— et qui approxime α à 10−n .

147
Chapitre 19. Décodage des codes BCH

^
19.1.2 Le cas des polynomes

Théorème 19.1.3. Soit A ∈ Fq [ x ] un polynôme de degré n + 1, et

B ∈ Fq [ x ] de degré ≤ n. Alors pour tout 1 ≤ k ≤ n, il existe deux
polynômes R, V ̸= 0, 0 tels que deg( R) ≤ k, deg(V ) ≤ n − k, et

BV ≡ R mod A.

De plus, le quotient R/V est unique.

Démonstration. Existence : les coefficients de V et R sont so-

lution d’un système linéaire à n + 1 équations et (n − k + 1) +
(k + 1) = n + 2 inconnues, il y a donc une solution non nulle.
Unicité : si R, V et R′ , V ′ sont deux solutions, alors BVV ′ −
BV ′ V = RV ′ − R′ V = 0 mod A, avec deg( A) = n + 1 et
deg( RV ′ − R′ V ) ≤ n, donc RV ′ = RV et la fraction est bien
unique.

Le couple ( R, V ) est appelé (k, n − k)-approximant de Padé de

B modulo A.
On peut le déterminer en O(n3 ) opérations en résolvant le
système linéaire qui le définit. Une meilleure méthode consiste
à l’obtenir lors de l’algorithme d’Euclide étendu.
Proposition 19.1.4. Soient A et B comme ci-dessus. On effectue
l’algorithme d’Euclide étendu

AUj + BVj = R j

Alors il existe j tel que deg(Vj ) ≤ n − k et deg( R j ) ≤ k.

Démonstration. La suite deg( R j ) est décroissante. Soit donc

j l’indice tel que deg( R j−1 ) > k ≥ deg( R j ). Alors d’après le
lemme ci-dessous, on a deg(Vj ) < n + 1 − k, d’où le résultat.

148
19.2. Décodage des codes BCH

Lemme 19.1.5. Au cours de l’algorithme d’Euclide étendu étendu,

on a

degA = degVj + degR j−1 .

Démonstration. On a A = R0 et puisque la suite degRk est

strictement décroissante degRk−1 = degQk + degRk , d’où

degA = degQ1 + . . . degQk−1 + degRk−1 .

De même, V0 = 0, V1 = 1, puis la suite degVk est strictement

croissante et degQk + degVk = degVk+1 , d’où

degVk = degQk1 + . . . Q1 .

Ce qui conclut.

19.2 Décodage des codes BCH

Soit C un code BCH de distance prévue δ = 2t + 1, et α tel que

c( x ) ∈ C ⇔ ∀0 ≤ i < 2t, c(α a+i ) = 0

Soit c( x ) le mot transmis, et y( x ) = c( x ) + e( x ) le mot reçu, où

l’on écrit e( x ) = ∑i∈T ei xi , avec #T ≤ t.
On définit alors le polynôme syndrome

2t−1
S( x ) = ∑ y (α a+l ) x l
l =0

ainsi que le polynôme localisateur de l’erreur

E( x ) = ∏ (1 − α i x )
i∈T

149
Chapitre 19. Décodage des codes BCH

Si l’on calcule S( x ) en fonction de l’erreur, on a

2t−1
S( x ) = ∑ e (α a+l ) x l
l =0
2t−1
= ∑ ∑ ei α i ( a + l ) x l
l =0 i ∈ T
2t−1
= ∑ ei αia ∑ (αi x)l
i∈T l =0
1 − (αi x )2t
= ∑ ei αia
i∈T 1 − αi x

On note

R( x ) = ∑ ei αia ∏ (1 − α j x)
i∈T j ∈ T ∖i

de sorte que S, E et R satisfont l’équation de Padé

S( x ) E( x ) ≡ R( x ) mod x2t .

Par hypothèse, les degrés satisfont les conditions, de sorte que

la solution est unique.
Les racines de E( X ) donnent les indices des erreurs, dont on
peut déterminer la valeur via la formule

R (α−k )
ek = − .
E′ (α−k )

Démonstration. On vérifie simplement : pour k ∈ T

R (α−k ) = ∑ ei α i ∏ (1 − α j − k )
i∈T j ∈ T ∖i

= ek α k
∏ (1 − α j − k )
j∈ T ∖k

150
19.3. Décodage des codes de Reed-Solomon

et
E′ (α−k ) = ∑ − α i ∏ (1 − α j − k )
i∈T j ∈ T ∖i

= −α k
∏ (1 − α j − k )
j∈ T ∖k

19.3 Décodage des codes de Reed-

Solomon

C’est un cas particulier, les calculs se font dans Fq ce qui est

agréable.
On peut également poser directement le problème du décodage
sur la présentation en termes d’évaluation :
Soient a1 , . . . an dans Fq , et C le code d’évaluation aux points ai .
Soit c( x ) de degré < k le mot envoyé, et y( x ) de degré < n
le mot reçu. On pose T = {i, y( ai ) ̸= c( ai )}, et on pose e( x ) =
∏i∈T ( x − ai ), de sorte que

∀i, c( ai )e( ai ) = y( ai )e( ai ).

Si l’on définit r ( x ) = c( x )e( x ) et A( x ) = ∏1≤i≤n ( x − ai ), on a

donc la relation

y( x )e( x ) ≡ r ( x ) mod A( x ),

où
deg(y( x )) < n
deg(e( x )) ≤ t
deg(r ( x )) < k + t
deg( A( x )) = n
On résout donc par approximation de Padé.

151

Vous aimerez peut-être aussi

Introduction à la Cryptographie
Pas encore d'évaluation
Introduction à la Cryptographie
109 pages
Sécurité et Cryptographie en Master CCA
Pas encore d'évaluation
Sécurité et Cryptographie en Master CCA
109 pages
Principes de la sécurité informatique
Pas encore d'évaluation
Principes de la sécurité informatique
36 pages
Chapitre 1
Pas encore d'évaluation
Chapitre 1
17 pages
Introduction à la cryptographie moderne
Pas encore d'évaluation
Introduction à la cryptographie moderne
25 pages
Introduction à la cryptographie moderne
Pas encore d'évaluation
Introduction à la cryptographie moderne
76 pages
Histoire et principes de la cryptologie
Pas encore d'évaluation
Histoire et principes de la cryptologie
76 pages
Introduction à la cryptographie moderne
Pas encore d'évaluation
Introduction à la cryptographie moderne
38 pages
Introduction à la cryptographie moderne
0% (1)
Introduction à la cryptographie moderne
68 pages
Introduction à la cryptographie moderne
100% (1)
Introduction à la cryptographie moderne
68 pages
Chaos et Sécurisation des Signaux Audio
Pas encore d'évaluation
Chaos et Sécurisation des Signaux Audio
25 pages
Cours - Crypto - Cryptis - Cours - Crypto - Cryptis
Pas encore d'évaluation
Cours - Crypto - Cryptis - Cours - Crypto - Cryptis
272 pages
Introduction à la Cryptologie
Pas encore d'évaluation
Introduction à la Cryptologie
38 pages
01-Chiffrement 1 Symetrique
Pas encore d'évaluation
01-Chiffrement 1 Symetrique
40 pages
Introduction à la Cryptographie Moderne
Pas encore d'évaluation
Introduction à la Cryptographie Moderne
126 pages
Mathématiques et Cryptographie au Cameroun
Pas encore d'évaluation
Mathématiques et Cryptographie au Cameroun
35 pages
Cryptographie : Chiffrement Asymétrique
Pas encore d'évaluation
Cryptographie : Chiffrement Asymétrique
34 pages
Introduction à la Cryptographie
Pas encore d'évaluation
Introduction à la Cryptographie
59 pages
Introduction à la Cryptologie 2024
Pas encore d'évaluation
Introduction à la Cryptologie 2024
50 pages
Crypto Martin
Pas encore d'évaluation
Crypto Martin
342 pages
Cryptographie Appliquée et Sécurité
Pas encore d'évaluation
Cryptographie Appliquée et Sécurité
115 pages
Initiation à la Cryptographie
Pas encore d'évaluation
Initiation à la Cryptographie
39 pages
Sécurité des Usages TIC et Cryptographie
Pas encore d'évaluation
Sécurité des Usages TIC et Cryptographie
272 pages
Cryptographie et Sécurité des Données
Pas encore d'évaluation
Cryptographie et Sécurité des Données
30 pages
Introduction à la Cryptographie et Sécurité
Pas encore d'évaluation
Introduction à la Cryptographie et Sécurité
39 pages
Introduction à la cryptographie moderne
Pas encore d'évaluation
Introduction à la cryptographie moderne
28 pages
Introduction à la Cryptographie
100% (1)
Introduction à la Cryptographie
9 pages
Cours sur la Cryptographie et Cipher Mining
Pas encore d'évaluation
Cours sur la Cryptographie et Cipher Mining
50 pages
Introduction à la Cryptographie
Pas encore d'évaluation
Introduction à la Cryptographie
9 pages
Chapitre 2 - Cryptographie
Pas encore d'évaluation
Chapitre 2 - Cryptographie
65 pages
Introduction à la cryptographie moderne
Pas encore d'évaluation
Introduction à la cryptographie moderne
40 pages
Protocoles historiques de cryptographie
Pas encore d'évaluation
Protocoles historiques de cryptographie
8 pages
La Mise en Œuvre Des Mesures de Sécurité
Pas encore d'évaluation
La Mise en Œuvre Des Mesures de Sécurité
25 pages
Introduction à la Cryptographie Sécurisée
Pas encore d'évaluation
Introduction à la Cryptographie Sécurisée
11 pages
A10 Partie 02 Cryptographie TH Exo Corr 21 22
Pas encore d'évaluation
A10 Partie 02 Cryptographie TH Exo Corr 21 22
62 pages
Introduction à la cryptographie moderne
Pas encore d'évaluation
Introduction à la cryptographie moderne
259 pages
Introduction à la cryptographie moderne
Pas encore d'évaluation
Introduction à la cryptographie moderne
36 pages
Introduction à la cryptographie
Pas encore d'évaluation
Introduction à la cryptographie
169 pages
Tutoriel Cryptographie
Pas encore d'évaluation
Tutoriel Cryptographie
48 pages
Introduction à la Cryptographie
Pas encore d'évaluation
Introduction à la Cryptographie
79 pages
Introduction à la cryptographie et ses techniques
Pas encore d'évaluation
Introduction à la cryptographie et ses techniques
11 pages
Cryptographie et Chiffrement Hybride
Pas encore d'évaluation
Cryptographie et Chiffrement Hybride
153 pages
Introduction à la cryptographie
Pas encore d'évaluation
Introduction à la cryptographie
32 pages
Introduction à la Cryptographie
Pas encore d'évaluation
Introduction à la Cryptographie
44 pages
Cryptage : Méthodes et Sécurité
Pas encore d'évaluation
Cryptage : Méthodes et Sécurité
23 pages
Cryptographie : Chiffrement et Sécurité
Pas encore d'évaluation
Cryptographie : Chiffrement et Sécurité
7 pages
Introduction à la cryptographie moderne
Pas encore d'évaluation
Introduction à la cryptographie moderne
126 pages
Introduction à la Cryptographie et ses Méthodes
Pas encore d'évaluation
Introduction à la Cryptographie et ses Méthodes
12 pages
Chiffrement et codage de l'information
Pas encore d'évaluation
Chiffrement et codage de l'information
124 pages
Cryptologie Et Securite Informatique
Pas encore d'évaluation
Cryptologie Et Securite Informatique
5 pages
Introduction à la cryptographie
Pas encore d'évaluation
Introduction à la cryptographie
72 pages
Introduction à la cryptographie
Pas encore d'évaluation
Introduction à la cryptographie
87 pages
Cours Crypto
Pas encore d'évaluation
Cours Crypto
108 pages
Introduction à la cryptographie moderne
Pas encore d'évaluation
Introduction à la cryptographie moderne
35 pages
Concepts Clés de la Cryptographie Moderne
Pas encore d'évaluation
Concepts Clés de la Cryptographie Moderne
3 pages
Cryptographie et cybersécurité : Guide complet
Pas encore d'évaluation
Cryptographie et cybersécurité : Guide complet
27 pages
Introduction à la Cryptographie et Sécurité
Pas encore d'évaluation
Introduction à la Cryptographie et Sécurité
13 pages
Introduction à la cryptologie et sécurité
Pas encore d'évaluation
Introduction à la cryptologie et sécurité
63 pages
Cryptographie et protection des données
Pas encore d'évaluation
Cryptographie et protection des données
6 pages
Apprentissage du français en République Dominicaine
Pas encore d'évaluation
Apprentissage du français en République Dominicaine
7 pages
Résumé du Conto da Ilha de Saramago
Pas encore d'évaluation
Résumé du Conto da Ilha de Saramago
11 pages
GMAO pour le barrage de Dahmouni
Pas encore d'évaluation
GMAO pour le barrage de Dahmouni
86 pages
Protocole Informatique WAIS IV
Pas encore d'évaluation
Protocole Informatique WAIS IV
3 pages
Modélisation d'une éolienne domestique
100% (1)
Modélisation d'une éolienne domestique
61 pages
Vademécum de Phytothérapie 2023
Pas encore d'évaluation
Vademécum de Phytothérapie 2023
5 pages
Poème "Les Sirènes" d'Albert Samain
Pas encore d'évaluation
Poème "Les Sirènes" d'Albert Samain
2 pages
Agriculture et Pêche au Gabon : Enjeux Économiques
100% (1)
Agriculture et Pêche au Gabon : Enjeux Économiques
3 pages
Conditions d'utilisation de 1xBet
Pas encore d'évaluation
Conditions d'utilisation de 1xBet
1 page
Démarrage Direct d'un Moteur Monophasé
Pas encore d'évaluation
Démarrage Direct d'un Moteur Monophasé
10 pages
Régulation Thermostatique: Tirage au Vide Unique
Pas encore d'évaluation
Régulation Thermostatique: Tirage au Vide Unique
4 pages
Mise en Place des Paliers de Jeu
Pas encore d'évaluation
Mise en Place des Paliers de Jeu
34 pages
Proyecto 153
Pas encore d'évaluation
Proyecto 153
108 pages
Rapport de stage en fabrication mécanique
Pas encore d'évaluation
Rapport de stage en fabrication mécanique
21 pages
Exercices de vocabulaire urbain et social
Pas encore d'évaluation
Exercices de vocabulaire urbain et social
3 pages
Fondements de la théorie du consommateur
Pas encore d'évaluation
Fondements de la théorie du consommateur
15 pages
Résolution de problèmes au cycle 2
Pas encore d'évaluation
Résolution de problèmes au cycle 2
15 pages
Gestion efficace des conflits en équipe
Pas encore d'évaluation
Gestion efficace des conflits en équipe
54 pages
Examen de TD sur les TIC et Marketing
Pas encore d'évaluation
Examen de TD sur les TIC et Marketing
4 pages
La Méthodologie Directe en Enseignement des Langues
Pas encore d'évaluation
La Méthodologie Directe en Enseignement des Langues
4 pages
Comprendre Économie et Finance
100% (5)
Comprendre Économie et Finance
206 pages
Guide Financements Humanitaires 2025
Pas encore d'évaluation
Guide Financements Humanitaires 2025
61 pages
Bougies Bipolaires 2
Pas encore d'évaluation
Bougies Bipolaires 2
16 pages
L - Estime de Soi - S - Aimer Pour Mieux Vivre Avec Les Autres
100% (12)
L - Estime de Soi - S - Aimer Pour Mieux Vivre Avec Les Autres
146 pages
Mécanismes et Robotique en Ingénierie
Pas encore d'évaluation
Mécanismes et Robotique en Ingénierie
25 pages
Configurer Réponse Automatique Outlook
Pas encore d'évaluation
Configurer Réponse Automatique Outlook
6 pages
Gestion des documents multimédias expliquée
Pas encore d'évaluation
Gestion des documents multimédias expliquée
6 pages
Fiche descriptive MLS - Duplex à vendre
Pas encore d'évaluation
Fiche descriptive MLS - Duplex à vendre
4 pages
Surveillance des ressources en eau en Algérie
100% (3)
Surveillance des ressources en eau en Algérie
33 pages
Comparaison Art Moyen-Âge et Renaissance
100% (1)
Comparaison Art Moyen-Âge et Renaissance
5 pages