Univ. Lille 1 - Master Info 2011-2012Principes et Algorithmes de Cryptographie

Structures algébriques et algorithmes

Table des matières

1 Entiers et opérations sur les entiers 2

1.1 Taille d'un entier . . . . . . . . . . . 21.2 Les entiers dans l'ordinateur . . . . . 31.3 Arithmétique sur les entiers . . . . . 3

1.3.1 L'addition . . . . . . . . . . . 31.3.2 La multiplication . . . . . . . 4

1.4 Nombres premiers . . . . . . . . . . 41.5 Nombre de nombres premiers . . . . 4

1.5.1 Tests de primalité . . . . . . 5

2 Groupes 6

2.1 Structure de groupe . . . . . . . . . 62.2 Groupes �nis et carrés latins . . . . 72.3 Théorème de Lagrange . . . . . . . . 82.4 Groupes cycliques . . . . . . . . . . 92.5 Exponentiation . . . . . . . . . . . . 10

3 Anneaux 11

3.1 Structure d'anneau . . . . . . . . . . 113.2 Algorithme d'Euclide . . . . . . . . . 12

3.2.1 Algorithme classique . . . . . 12

3.2.2 Algorithme binaire . . . . . . 123.2.3 Algorithme d'Euclide étendu 123.2.4 Inverse modulaire . . . . . . . 14

3.3 Racines carrées modulo n . . . . . . 153.3.1 Cas n premier . . . . . . . . . 153.3.2 Cas n produit de deux

nombres premiers . . . . . . 16

4 Corps 16

4.1 Structure de corps . . . . . . . . . . 164.2 Propriétés des corps . . . . . . . . . 164.3 Corps �nis . . . . . . . . . . . . . . . 164.4 Construction de corps �nis . . . . . . 17

4.4.1 Existence de corps �nis nonpremiers . . . . . . . . . . . . 17

4.4.2 Corps à 4 éléments . . . . . . 174.5 Corps �nis à q = pn éléments . . . . 18

4.5.1 Polynômes irréductibles . . . 184.5.2 Application à la construction

de corps �nis . . . . . . . . . 18

Bibliographie Notes de cours établies à partir des ouvrages suivants

1. Cours d'algèbre. Primalité, divisibilité, codes de Michel Demazure, Cassini, 1997.

2. The art of computer programming, vol 2, seminumerical algorithms de Donald E. Knuth, AddisonWesley, 3ème édition, 1998.

3. A course in computational algebraic number theory de Henri Cohen, Springer, 4ème édition, 2000.

4. Modern Computer Algebra de Joachim von zur Gathen et Jürgen Gerhard, Cambridge universitypress, 1999.

5. Handbook of applied cryptography de Alfred Menezes & al., CRC Press, 1996. Disponible par internetà l'adresse http://www.cacr.math.uwaterloo.ca/hac/.

NOTES DE COURS ENCORE INACHEVEES :� Theorème chinois des restes

1

1 Entiers et opérations sur les entiers

1.1 Taille d'un entier

Il existe plusieurs notations possibles pour les nombres entiers. En particulier, dans la numération deposition, les entiers peuvent être représentés par des mots �nis sur un alphabet dont les symboles sontusuellement appelés chi�res. Ainsi le nombre entier qui donne la valeur (arrondie à l'entier inférieur) decent euros en francs français se note 657 en base 10. Ce mot de trois lettres (ou chi�res) qui dénote l'entier657 signi�e que cet entier est égal à

657 = 6× 102 + 5× 101 + 7× 100,

c'est à dire une somme de puissances de 10 consécutives coe�cientées par des nombres compris entre 0et 9 = 10− 1.

On comprend alors que par le même procédé, on peut écrire cet entier dans d'autres bases B au moinségales à 2. Par exemple en base 2, puisque l'on a

657 = 1× 29 + 0× 28 + 1× 27 + 0× 26 + 0× 25 + 1× 24 + 0× 23 + 0× 22 + 0× 21 + 1× 20,

le nombre 657 peut s'écrire en base 2 avec le mot de dix chi�res binaires 1010010001.Nous voyons donc que selon la base de numération choisie le mot dénotant 657 peut être plus ou moins

long. Et même pour une base �xée la longueur n'est pas unique, puisque on peut toujours pré�xer unmot dénotant un entier par un mot de la forme 0k. Par exemple en base 10, les mots 657, 0657, 00657,. . . dénotent tous le même entier. Lorsque l'écriture ne comprend pas de 0 en tête, on parle d'écriturestandard.

Nous donnons donc la dé�nition suivante de la taille d'un entier.

Dé�nition 1.1. La taille d'un entier n > 0 en base B ≥ 2, notée |n|B, est la longueur du plus petit motle dénotant dans cette base. Autrement dit, c'est le nombre de chi�res nécessaires pour l'écriture standardde l'entier n en base B, c'est-à-dire sans zéros super�us à gauche.

Par exemple, |657|10 = 3 et |657|2 = 10.Une expression de la taille d'un entier est donnée par le thérorème qui suit.

Théorème 1.1.

|n|B = blogB nc+ 1.

Dans ce théorème, la notation bxc désigna la partie entière du réel x, c'est�à�dire le plus grandnombre entier inférieur ou égal à x, et la notation logB x désigne le logarithme en base B de x, c'est�à�dire logB x = ln x

lnB .La formule exacte de l'expression de la taille d'un entier donnée par le théorème 1.1 peut se simpli�er

par l'approximation|n|B ≈ logB n,

approximation d'autant plus valable que l'entier n est grand.La taille d'un entier croît donc logarithmiquement en fonction de sa valeur, et comme la croissance des

fonctions logarithmiques est assez lente, cela explique la capacité de la numération de position à dénoterde très grands nombres entiers.

Corollaire 1.1.|n|B|n|B′

≈ lnB′

lnB= logB B

′.

Ainsi pour de très grands entiers, le rapport des tailles dans deux bases di�érentes est approximati-vement constant. Dans le cas des bases B = 10 et B′ = 2 ce rapport est

log10 2 ≈ 0.3010299957,

autrement dit la taille de l'écriture en base 10 d'un entier est approximativement égale à 30% de celle enbase 2.

2

1.2 Les entiers dans l'ordinateur

Il faut distinguer entre les entiers machine qui sont ceux représentables dans un registre du processeur,et les autres qui ne le sont pas, souvent nommés entiers multiprécision.

Les registres des processeurs ont une taille �xée (couramment 32 ou 64 bits sur les PC actuels). Lesentiers machine sont donc les entiers représentables par des mots binaires d'une taille �xée n, c'est�à�direles entiers de l'intervalle [[0, 2n− 1]] dans leur version non signée, ou les entiers de [[−2n−1, 2n−1− 1]] dansleur version signée.

Non signés Signéstaille min max min max

n = 32 bits 0 232 − 1 ≈ 4× 109 −231 ≈ −2× 109 231 − 1 ≈ 2× 109

n = 64 bits 0 264 − 1 ≈ 18× 1018 −263 ≈ −9× 1018 263 − 1 ≈ 9× 1018

Table 1 � Entiers machine

L'arithmétique sur les entiers machine est e�ectuée par l'unité arithmétique et logique du processeur.Si on souhaite travailler avec des entiers dépassant les limites des entiers machine, et c'est le plus sou-

vent le cas en cryptographique, il faut utiliser une représentation en multiprécision. Plusieurs réalisationssont possibles.

Par exemple, la bibliothèque GMP 1 de programmation de calculs en multiprécision, implémente lesentiers multiprécision sous forme de tableaux dynamiques de mots machines considérés comme des chi�resde la base B = 2n (avec n = 32 ou 64), avec un champ supplémentaire pour indiquer le nombre N demots utilisés et le signe s de l'entier représenté. Autrement dit l'entier

a = (−1)s∑

0≤i≤N

ai ·Bi

est représenté par le signe s et l'entier N ainsi qu'un tableau des entiers machine a0, a1,. . . aN .Bien évidemment, pour les entiers multiprécision, il faut programmer les opérations arithmétiques de

base (addition, multiplication, . . . ), et c'est ce que fait la bibliothèque GMP.

1.3 Arithmétique sur les entiers

1.3.1 L'addition

Algorithme 1 Addition de deux entiers multiprecision de même signe

Entrée: a = (−1)s∑

0≤i≤N ai ·Bi et b = (−1)s∑

0≤i≤N bi ·Bi deux entiers de même signe s.Sortie: c = (−1)s

∑0≤i≤N+1 ci ·Bi tel que c = a+ b.

1: γ0 ← 02: pour i = 0 . . . N faire

3: ci ← ai + bi + γi, γi+1 ← 04: si ci ≥ B alors

5: ci ← ci − b, γi+1 ← 16: �n si

7: �n pour

8: cN+1 ← γN+1

9: retourner (−1)s∑

0≤i≤N+1 ci ·Bi

Les opérations d'addition et de soustraction apparaissant aux lignes 3 et 5 de l'algorithme 1 sont desopérations sur les entiers machine.

Le nombre d'opérations sur les entiers machine requis dans l'addition de deux entiers multiprécisionde taille N par l'algorithme 1 est en O(N). Cet algorithme est donc linéaire en la taille des entiers ajoutés.

On peut facilement adapter l'algorithme 1 en un algorithme d'addition de deux polynômes A(X) =∑0≤i≤N aiX

i et B(X) =∑

0≤i≤N biXi. L'algorithme est alors plus simple car il est inutile de gérer les

retenues comme dans le cas des entiers.L'addition de la ligne 2 de l'algorithme 2 peut être une addition de deux entiers, deux rationnels, deux

réels, deux complexes selon l'espace des coe�cients des polynômes considérés.

1. GNU Multiple Precision, http://gmplib.org/

3

Algorithme 2 Addition de deux polynômes

Entrée: A(X) =∑

0≤i≤N aiXi et B(X) =

∑0≤i≤N biX

i deux polynômes de degré ≤ NSortie: C(X) =

∑0≤i≤N ciX

i avec C = A+B.1: pour i = 0 . . . N faire

2: ci ← ai + bi3: �n pour

4: retourner∑

0≤i≤N ciXi

1.3.2 La multiplication

Algorithme 3 Multiplication de deux entiers multiprécision

Entrée: a = (−1)s∑

0≤i≤N ai ·Bi et b = (−1)s∑

0≤i≤M bi ·Bi deux entiers.Sortie: c = ab.1: pour i = 0 . . . N faire

2: ci ← 03: pour j = 0 . . .M faire

4: p← ai × bj . p s'écrit p = p1 ·B + p0 avec 0 ≤ pi < B5: ci ← ci + p0 ·Bi+j + p1 ·Bi+j+1

6: �n pour

7: �n pour

8: retourner (−1)s+t∑

0≤i≤N ci ·Bi.

Le nombre d'opérations (additions et multiplications) sur les entiers machines dans le calcul du produitde deux entiers de taille N et M est en O(NM). Cet algorithme est donc quadratique en la taille desentiers multipliés.

1.4 Nombres premiers

Les nombres premiers sont les nombres qui sont divisibles par exactement deux nombres : eux-mêmeset 1 2.

L'intérêt essentiel des nombres premiers réside dans le théorème fondamental de l'arithmétique.

Théorème 1.2. Théorème fondamental de l'arithmétiqueTout nombre entier non nul possède une unique décomposition en facteurs premiers.

2 3 5 7 11 13 17 19 23 29 31 37 41 43 4753 59 61 67 71 73 79 83 89 97 101 103 107 109 113127 131 137 139 149 151 157 163 167 173 179 181 191 193 197199 211 223 227 229 233 239 241 251 257 263 269 271 277 281283 293 307 311 313 317 331 337 347 349 353 359 367 373 379383 389 397 401 409 419 421 431 433 439 443 449 457 461 463467 479 487 491 499 503 509 521 523 541 547 557 563 569 571577 587 593 599 601 607 613 617 619 631 641 643 647 653 659661 673 677 683 691 701 709 719 727 733 739 743 751 757 761769 773 787 797 809 811 821 823 827 829 839 853 857 859 863877 881 883 887 907 911 919 929 937 941 947 953 967 971 977983 991 997

Table 2 � Liste des nombres premiers inférieurs à 1000.

1.5 Nombre de nombres premiers

Théorème 1.3. 1. Il existe une in�nité de nombres premiers (Euclide).

2. On se place ici dans l'ensemble N des entiers naturels. La notion de nombres premiers peut être étendue à l'ensemble

Z des entiers relatifs, et ce sont alors les nombres ayant exactement 4 diviseurs.

4

2. Le nombre π(n) de nombres premiers inférieurs ou égaux à n est une fonction croissante avec néquivalente à l'in�ni

π(n) ∼ n

lnn

(Hadamard, de la Vallée Poussin, �n XIXème).

3. Plus précisément, on a pour tout entier n ≥ 59

n

ln(n)

(1 +

1

2 ln(n)

)< π(n) <

n

ln(n)

(1 +

3

2 ln(n)

).

4. Lorsque t est un entier au moins égal à 3, le nombre πt de nombres premiers de taille t bits estminoré par

πt = π(2t)− π(2t−1) >2t−2

(t− 1) ln(2).

1.5.1 Tests de primalité

Il existe plusieurs algorithmes pour tester la primalité d'un nombre entier.L'un des tests les plus simples est la recherche du plus petit diviseur de l'entier n à tester, en sachant

que n est premier si et seulement s'il n'admet aucun diviseur compris entre 2 et√n. L'algorithme 4

e�ectue Coût de l'algorithme 4 dans le pire des cas : O(√n) divisions. Autrement dit, pour tester un

Algorithme 4 Test par recherche du plus petit diviseurEntrée: n un entier au moins égal à 3.Sortie: déterminer si n est premier.1: k ← 22: tant que k ne divise pas n et k ≤

√n faire

3: k ← k + 14: �n tant que

5: si k divise n alors

6: retourner NON7: sinon

8: retourner OUI9: �n si

entier de taille t bits : O(2t/2) divisions. Soit un algorithme exponentiel en la taille de l'entier à tester.

Un théorème dû à Miller

Théorème 1.4. Théorème de MillerSoit n > 1 un entier impair. On pose n − 1 = 2su avec u impair. S'il existe un entier 1 < a < n

tel que au 6= 1 (mod n) et a2iu 6= −1 (mod n) pour i ∈ [[0, s − 1]], alors n est composé, et l'entier a est

appelé témoin de non primalité de n.

De plus, si n est un entier impair composé, au moins les trois quarts des entiers a compris entre 1 etn sont des témoins de non primalité de n.

Analyse du test de Miller-Rabin

1. Algorithme probabiliste� toujours correct si réponse négative ;� possibilité d'erreur si réponse positive ;� réponse toujours correcte si n est premier ;� possibilité d'erreur si n est composé, mais probabilité d'erreur < 1

4 .

2. Complexité algorithmique (dans le pire des cas) :� deux calculs de pgcd (cf algo 8 page 12) ;� une exponentiation modulaire (cf algo 7 page 10 ;� s élévations au carré.Algorithme cubique en nombre d'opérations sur les bits.

5

Algorithme 5 Test de non primalité de Miller-RabinEntrée: n un entier impair au moins égal à 3.Sortie: déterminer si n est premier.1: choisir au hasard a ∈ [[2, n− 2]]2: calculer g = pgcd(a, n)3: si g > 1 alors

4: retourner NON5: �n si

6: calculer u et s tels que n− 1 = 2s × u avec u impair7: b0 ← au (mod n)8: si b0 = 1 alors

9: retourner (probablement) OUI10: �n si

11: pour 1 ≤ i ≤ s faire12: bi ← b2i−1 (mod n)13: �n pour

14: si bs = 1 alors

15: j ← min{0 ≤ i | bi+1 = 1}16: sinon

17: retourner NON18: �n si

19: g ← pgcd(bj + 1, n)20: si g = 1 ou g = n alors

21: retourner (probablement) OUI22: sinon

23: retourner NON24: �n si

2 Groupes

2.1 Structure de groupe

Dé�nition 2.1. Un groupe est un ensemble G muni d'une opération interne, notée ci-dessous ?, tel queles propriétés suivantes sont satisfaites :

associativité l'opération ? est associative

∀a, b, c ∈ G (a ? b) ? c = a ? (b ? c) ;

élément neutre l'opération ? possède un élément neutre e

∃e ∈ G ∀a ∈ G a ? e = e ? a = a ;

inverse tout élément possède un inverse (à gauche et à droite)

∀a ∈ G ∃b ∈ G a ? b = b ? a = e.

Le groupe est dit commutatif ou abélien si en plus, l'opération ? est commutative, c'est-à-dire si

∀a, b ∈ G a ? b = b ? a.

Exemples

1. Les ensembles usuels de nombres signés entiers Z, rationnels Q, réels R, complexes C munis del'opération d'addition usuelle (+) sont des groupes commutatifs in�nis.

2. Les ensembles de nombres entiers modulaires (Z/nZ) muni de l'addition modulo n sont des groupescommutatifs �nis.

3. Si on enlève 0, les ensembles K\{0}, avec K = Q, ou R, ou C sont des groupes commutatifs in�nispour la multiplication usuelle (×).

4. Les ensembles R[X] des polynômes à coe�cients dans R, R étant un anneau (cf la section 3), parexemple l'un des ensembles de nombres cités ci-dessus, muni de l'addition usuelle des polynômessont des groupes commutatifs in�nis.

6

5. L'ensemble Sn des permutations des entiers de 1 à n, muni de l'opération (◦) de composition estun groupe �ni non commutatif.

Contre-exemples

1. L'ensemble N des entiers naturels muni de l'addition usuelle n'est pas un groupe : hormis 0, élémentneutre pour l'addition, aucun entier ne possède d'inverse pour l'addition (il manque les nombresnégatifs).

2. De même, l'ensemble A∗ des mots sur un alphabet A, muni de l'opération de concaténation n'estpas un groupe : hormis le mot vide, élément neutre pour la concaténation, aucun mot ne possèded'inverse pour la concaténation.

3. Les ensembles de nombres signés munis de l'opération de multiplication usuelle (×) ne sont pasdes groupes : le nombre 0 interdit l'existence d'un élément neutre. Même si on enlève le nombre 0de ces ensembles la structure n'est pas toujours celle d'un groupe. Par exemple, Z \ {0} n'est pasun groupe puisque en dehors de 1 et −1 aucun entier n'admet d'inverse pour la multiplication. Enrevanche, Q \ {0}, R \ {0} et C \ {0} sont des groupes multiplicatifs (in�nis et commutatifs).

4. Les ensembles Z/nZ\{0} munis de la multiplication modulo n ne sont pas des groupes. En revancheles ensembles Z/nZ∗ des éléments inversibles pour la multiplication modulo n sont des groupes �nisayant ϕ(n) éléments, où ϕ désigne la fonction indicatrice d'Euler dé�nie pour n ≥ 2 par

ϕ(n) = n∏p|n

(1− 1

p)

p parcourant les nombres premiers divisant n. Une autre expression possible pour ϕ s'obtient àpartir de la décomposition en facteurs premiers de n =

∏ri=1 p

sii par

ϕ

(r∏

i=1

psii

)=

r∏i=1

(psii − psi−1i ).

Remarque Lorqu'un ensemble est muni d'une opération interne qui ne satisfait que les deux premièrespropriétés (associativité et existence d'un élément neutre), la structure algébrique qui en résulte estnommée monoïde. L'ensemble des entiers naturels munis de l'addition, et l'ensemble des mots sur unalphabet muni de la concaténation sont des monoïdes.

Notation additive ou multiplicative ? Deux opérations courantes notées + (addition) et × ou bien· (multiplication) apparaissent fréquemment (sur les nombres, sur les polynômes, . . . ). Le tableau 3compare les notations lorque l'opération est additive ou multiplicative.

Notation additive Notation multiplicativeCombinaison de deux éléments a, b ∈ G a+ b a× b ou a · b ou ab

Composée m-ième d'un élément a ∈ G (m ∈ N \ {0}) ma = a+ . . .+ a︸ ︷︷ ︸m fois a

am = a · . . . · a︸ ︷︷ ︸m fois a

Élément neutre (m = 0) 0a = 0 a0 = 1Inverse (m = −1) −a a−1

Composée −m-ième d'un élément a ∈ G (m ∈ N) (−m)a = m(−a) a−m = (a−1)m

m, p ∈ Z, a ∈ G (m+ p)a = ma+ pa am+p = am · apm, p ∈ Z, a ∈ G (mp)a = m(pa) amp = (am)p

Table 3 � Notations additives et multiplicatives

Dans toute la suite, pour désigner l'opération interne d'un groupe nous utiliserons la notation multi-plicative.

2.2 Groupes �nis et carrés latins

Théorème 2.1. Soit G un groupe �ni d'ordre n et a un élément de G. Les applications

ga : G −→ Gx 7−→ a · x

7

etda : G −→ G

x 7−→ x · a

sont des bijections.

Une conséquence de ce théorème est que si l'opération de groupe est représentée par un tableau à deuxentrées x et y, éléments du groupe, donnant l'élément x · y, alors toutes les lignes de ce tableau, ainsi quetoutes les colonnes contiennent chaque élément du groupe une et une seule fois. Autrement dit, ce tableauest un carré latin. Les deux tableaux présentés en 4 montrent deux carrés latins d'ordre 4 représentantsle groupe additif des entiers modulo 4 et le groupe multiplicatif des entiers non nuls modulo 5.

+ 0 1 2 30 0 1 2 31 1 2 3 02 2 3 0 13 3 0 1 2

× 1 2 3 41 1 2 3 42 2 4 1 33 3 1 4 24 4 3 2 1

Table 4 � Tables des groupes (Z/4Z,+) et (Z/5Z \ {0},×)

Si on assure la correspondance 0 7→ a, 1 7→ b, 2 7→ c et 3 7→ d dans le premier tableau et lacorrepsondance 1 7→ a, 2 7→ b, 3 7→ d et 4 7→ c dans le second, alors les deux tableaux de 4 sont identiquesaprès permutation des deux dernières lignes et des deux dernières colonnes de l'un ou l'autre des deuxtableaux. Les deux groupes (Z/4Z,+) et (Z/5Z \ {0},×) sont isomorphes.

Il n'existe que deux carrés latins d'ordre 4 non identiques à permutation près des lignes et des colonnes,et à nommage près des éléments : celui des deux groupes présentés dans 4 et celui présenté dans 5. Cesecond carré latin est celui correspondant au groupe produit (Z/2Z× Z/2Z,+) dans lequel les élémentssont des couples de deux entiers modulo 2 (autrement dit des mots de deux bits), et l'addition estl'addition modulo 2 composante par composante (autrement dit le ou-exclusif bit à bit).

a b c db a d cc d a bd c b a

Table 5 � Second carré latin d'ordre 4

Une question naturelle qui se pose est celle de savoir si à tout carré latin il correspond un groupe �ni.La réponse est positive pour les carré latins jusqu'à l'ordre 4 : il existe un seul carré latin d'ordre 1, 2et 3 qui donnent les tables des groupes additifs Z/1Z, Z/2Z et Z/3Z, et nous venons de voir qu'il existedeux carré latins d'ordre 4 donnant chacun la table de groupes �nis d'ordre 4. Il existe aussi deux carréslatins d'ordre 5 que la table 6 montre. Le carré de gauche peut être vu comme la table d'addition modulo5 et correspond donc à la table d'un groupe. En revanche celui de droite ne peut pas être la table d'ungroupe �ni, puisqu'alors l'opération ne serait pas associative. La réponse à la question initiale est doncnégative.

a b c d eb c d e ac d e a bd e a b ce a b c d

a b c d eb d a e cc e d b ad a e c be c b a d

Table 6 � Les deux carrés latins d'ordre 5

2.3 Théorème de Lagrange

Lorsqu'un groupe est �ni, le nombre de ses éléments est appelé ordre du groupe.

8

Théorème 2.2. (Lagrange) Soit G un groupe �ni d'ordre n, d'élément neutre 1. Alors quelque soitl'élément a ∈ G, il existe un entier m > 0 tel que

am = 1.

De plus, le plus petit entier non nul m satisfaisant cette relation divise n.

Dé�nition 2.2. Pour un élément a d'un groupe �ni, le plus petit entier m satisfaisant am = 1 est appeléordre de cet élément.

Corollaire 2.1. Pour tout élément a d'un groupe �ni d'ordre n, on a

an = 1.

Corollaire 2.2. L'inverse d'un élément a d'un groupe �ni d'ordre n est égal à

a−1 = an−1.

Remarque : Deux cas particuliers du corollaire 2.1 sont le (petit) théorème de Fermat et le théorèmed'Euler rappelés ci-dessous.

Théorème 2.3. (Fermat) Soit n un nombre premier. Alors pour tout entier a non divisible par n on a

an−1 (mod n) = 1.

Théorème 2.4. (Euler) Soit n ≥ 2 un entier. Pour tout entier a premier avec n on a

aϕ(n) (mod n) = 1.

2.4 Groupes cycliques

Dé�nition 2.3. Un groupe cyclique est un groupe �ni G dans lequel existe un élément a de même ordreque l'ordre n du groupe, c'est à dire un groupe dont les éléments sont de la forme ai avec a ∈ G et0 ≤ i < n.

Un élément d'ordre n est appelé générateur du groupe cyclique.

Théorème 2.5. Le nombre de générateurs d'un groupe cyclique d'ordre n est égal à ϕ(n).

Exemples :

1. Les groupes additifs Z/nZ sont cycliques d'ordre n, et tout entier premier avec n est un générateur.

2. Lorsque n est un nombre premier, Z/nZ \ {0} est un groupe cyclique d'ordre n− 1.

Tous les groupes �nis ne sont pas cycliques. En e�et, il existe des groupes �nis non commutatifs(cf 2.1), et les groupes cycliques sont tous commutatifs. Mais il existe aussi des groupes �nis commutatifsnon cycliques, comme par exemple le groupe d'ordre 4 (Z/2Z × Z/2Z,+) que nous avons vu dans lapartie 2.2 et dont tous les éléments non nuls sont d'ordre 2.

Dans un groupe cyclique, une fois �xé un générateur a, l'opération de ce groupe revient à une additionmodulo l'ordre du groupe. En e�et, pour deux éléments quelconques du groupe x = ai et y = aj , on a

x · y = ai · aj = a(i+j) (mod m).

Du point de vue de l'informaticien, il est donc toujours possible de représenter les éléments d'ungroupe cyclique d'ordre m par les entiers compris entre 0 et m−1 et d'implanter l'opération de ce groupepar une addition modulo m.

Étant donné un groupe cyclique G d'ordre n, il est possible de trouver un générateur par une méthodeprobabiliste, si on dispose d'un générateur aléatoire d'éléments de G. Le principe consiste à tirer unélément au hasard dans G, et de véri�er qu'il est bien générateur de G. Pour cette véri�cation, il su�tde s'assurer que pour aucun diviseur de n, l'élement choisi au hasard n'a pour ordre ce diviseur. Ceci estfacilement faisable dès lors que l'on connaît la décomposition en facteurs premiers de n. L'algorithme 6suit ce principe.

Les calculs de puissances à faire à la ligne 2 peuvent être e�cacement e�ectués grâce à l'algorithmed'exponentiation rapide 7 décrit page 10.

9

Algorithme 6 Trouver un générateur d'un groupe cyclique

Entrée: G un groupe cyclique d'ordre n, et n =∏k

i=1 peii .

Sortie: g un générateur de G.1: choisir un élément g ∈ G au hasard2: pour chaque facteur premier pi de n, véri�er que gn/pi 6= 1.3: si c'est le cas alors4: retourner g5: sinon

6: revenir en [1]7: �n si

L'algorithme 6 est e�cace puisque pour chaque élément g choisi au hasard dans G, la probabilité qu'ilsoit un générateur est égale à ϕ(n)

n , et comme pour tout entier n ≥ 5, on a

ϕ(n) >n

ln lnn,

cette probabilité est supérieure à 1ln lnn , ce qui signi�e qu'en moyenne, ln lnn tirages aléatoires d'éléments

de G su�sent pour trouver un générateur.

2.5 Exponentiation

L'exponentiation dans un groupe multiplicatif (ou la multiplication par un entier dans un groupeadditif) est une opération fréquente en arithmétique, et en cryptographie (cf protocole d'échange declés de Di�e-Hellman, cryptosystème RSA, cryptosystème de El Gamal,. . . ). Il est donc utile qu'on s'yattarde un peu.

Le problème de l'exponentiation est celui du calcul e�ectif et e�cace de am lorsque a est un élémentd'un groupe (ou d'un monoïde), et m un entier relatif quelconque.

Bien entendu il est toujours possible de calculer am en suivant la dé�nition am = a · . . . ·a, c'est-à-direen e�ectuant m − 1 multiplications d'éléments de G. Cependant, cette méthode devient impensable enpratique dès lors que m devient grand, ce qui est souvent le cas en cryptographie.

Il nous faut donc un algorithme d'exponentiation plus rapide. L'algorithme 7 répond e�cacement ànotre problème. Sa description suppose donnés la représentation des éléments du groupe, et en particulierde son élément neutre 1, ainsi que l'implantation des opérations de multiplication et d'élévation au carrédans ce groupe (cette dernière opération pouvant toujours être réalisée grâce à la première).

Algorithme 7 Exponentiation dans un groupeEntrée: a ∈ G un élément d'un groupe d'ordre n dont l'élément neutre est noté 1, m ∈ ZSortie: c = am

1: r ← 12: si m = 0 alors

3: retourner r4: sinon

5: si m < 0 alors

6: s← a−1, k ← −m7: sinon

8: s← a, k ← m9: �n si

10: �n si

11: tant que k > 1 faire

12: si k est impair alors13: r ← r · s14: �n si

15: s← s2

16: k ← k ÷ 217: �n tant que

18: r ← r · s19: retourner r

10

En fait, si on n'utilise que des exposants positifs (m > 0), cet algorithme ne s'applique pas uniquementau calcul de la puissance d'un élément d'un groupe, puisque qu'alors on n'a pas besoin de calculer d'inversede a (ligne 6). En particulier, on peut l'appliquer pour le calcul de am lorsque a est dans (Z,×) ou dans(Z/nZ×).

Le tableau 7 montre les di�érentes étapes de cet algorithme appliqué à a = 2 ∈ N etm = 13 (la colonnei indique les numéros des étapes de la boucle tantque, et dans la colonne de la variable k l'écriture binaireest inscrite entre parenthèses).

i r s k1 2 13 (1101)

1 2 4 6 (110)2 2 16 3 (11)3 32 256 1 (1)

8192

213 = 8192.

Table 7 � Calcul de 213 par l'algorithme 7

On peut véri�er que ce calcul a nécessité trois élévations au carré (ligne 15) et trois multiplications(lignes 13 et 18), soit six multiplications en tout si l'élévation au carré est accomplie par une multiplication.

De manière générale, le nombre d'opérations dans G e�ectuées pour calculer am, m > 0, avec cetalgorithme est lié à la représentation binaire de l'entier m. En particulier il e�ectue |m|2 − 1 élévationsau carré auxquelles il faut ajouter une multiplication pour chaque bit de m valant 1. Par exemple, pourm = 13 dont l'écriture binaire est 1101, on retrouve les |m|2 − 1 = 3 élévations au carré et les troismultiplications correspondant aux trois bits valant 1. Ainsi le nombre d'opérations dans G est comprisentre |m|2 et 2|m|2 − 1, et comme on a |m|2 = blog2mc+ 1, cet algorithme est en O(logm).

Remarque Dans un groupe �ni d'ordre n, le calcul de l'inverse (ligne 6 de l'algorithme 7) d'un élémenta peut toujours se faire par le calcul de an−1. Ainsi le calcul de l'inverse se ramène à un calcul d'expo-nentiation. Toutefois, dans certaines structures il existe d'autres méthodes de calcul d'un inverse (cf lecalcul d'inverse dans la section 3.2.4 par exemple).

3 Anneaux

3.1 Structure d'anneau

Dé�nition 3.1. Un anneau est un ensemble A muni de deux opérations internes, notées usuellement +et × (ou ·), tel que les propriétés suivantes soient satisfaites :

groupe additif A muni de l'opération + est un groupe commutatif ;

mutiplication associative l'opération × est associative

∀a, b, c ∈ A (a× b)× c = a× (b× c) ;

élément neutre multiplicatif l'opération × possède un élément neutre

∃e ∈ A ∀a ∈ A a× e = e× a = a ;

distributivité l'opération × est distributive par rapport à +

∀a, b, c ∈ A a× (b+ c) = a× b+ a× c, et (b+ c)× a = b× a+ c× a.

L'anneau est dit commutatif si en plus l'opération × l'est.

On note usuellement 0 et 1 les éléments neutres pour l'addition et pour la multiplication.

11

Exemples

1. Z muni de l'addition et de la multiplication usuelle des entiers est un anneau commutatif.

2. De même pour Q, R et C.3. Z/nZ muni de l'addition et de la multiplication modulo n des entiers est un anneau commutatif.

4. L'ensemble R[X] des polynômes à coe�cients dans un anneau R, muni de l'addition et de lamultiplication usuelle des polynômes est un anneau commutatif.

5. L'ensembleMn(R) des matrices carrées d'ordre n à coe�cients dans un anneau Rmuni de l'additionet de la multiplication usuelle est un anneau non commutatif.

3.2 Algorithme d'Euclide

3.2.1 Algorithme classique

L'algorithme d'Euclide � classique � permet de calculer le pgcd de deux entiers, ou de deux polynômes.Il consiste essentiellement à e�ectuer des divisions euclidiennes jusqu'à obtenir un reste nul.

L'algorithme 8 permet de calculer le pgcd de deux entiers positifs. Pour des entiers de signe quelconque,il su�t de remarquer que

pgcd(a, b) = pgcd(|a|, |b|).

Algorithme 8 Algorithme d'Euclide pour calculer le pgcd de deux entiers a et bEntrée: a et b deux entiers positifsSortie: d = pgcd(a, b)1: Soient a1 ← a et b1 ← b2: tant que b1 6= 0 faire

3: Calculer le quotient q et le reste r dans la division euclidienne de a1 par b14: a1 ← b15: b1 ← r6: �n tant que

7: retourner a1

Le tableau 8 montre les di�érentes étapes de l'exécution de l'algorithme 8 sur les entiers a = 651 etb = 69.

i q r a1 b1651 69

1 9 30 69 302 2 9 30 93 3 3 9 34 3 0 3 0

pgcd(651,69) = 3

Table 8 � Calcul de pgcd(651, 69) par l'algorithme 8

3.2.2 Algorithme binaire

L'algorithme binaire de calcul du pgcd est particulièrement bien adapté lorsque les entiers sont repré-sentés en binaire, car aucune division n'est e�ectuée, les seules divisions par deux étant réalisées par desimples décalages à droite.

Le tableau 9 montre une trace de l'exécution de l'algorithme 9 sur les entiers a = 1200 et b = 1152.

3.2.3 Algorithme d'Euclide étendu

Le théorème de Bézout stipule que le pgcd de tout couple de nombres entiers peut toujours s'exprimercomme une combinaison linéaire à coe�cients entiers de ces deux nombres.

12

Algorithme 9 Algorithme binaire de calcul du pgcdEntrée: a et b deux entiers positifsSortie: d = pgcd(a, b)1: Soient a1 ← a, b1 ← b et p← 12: tant que a1 et b1 sont tous deux pairs faire3: a1 ← a1 ÷ 2, b1 ← b1 ÷ 2 et p← 2p4: �n tant que

5: tant que a1 6= 0 faire

6: tant que a1 pair faire7: a1 ← a1 ÷ 28: �n tant que

9: tant que b1 pair faire10: b1 ← b1 ÷ 211: �n tant que

12: si a1 ≥ b1 alors13: a1 ← (a1 − b1)÷ 214: sinon

15: t← (b1 − a1)÷ 216: b1 ← a117: a1 ← t18: �n si

19: �n tant que

20: retourner p ∗ b1

a1 b1 p1200 1152 1600 576 2300 288 4150 144 875 72 1633 9 1612 9 163 3 160 3 16

pgcd(1200,1152) = 48

Table 9 � Calcul de pgcd(1200, 1152) par l'algorithme 9

Théorème 3.1. BezoutPour tout couple de nombres entiers a et b, il existe deux entiers u et v tels que

pgcd(a, b) = au+ bv.

De tels entiers u et v sont appelés coe�cients de Bezout.

Par exemple, pour le couple (a, b) = (651, 69), on peut prendre (u, v) = (30,−283). En e�et, on a bien

pgcd(651, 69) = 3 = 651× 30− 69× 283.

On peut adapter l'algorithme d'Euclide de calcul du pgcd pour calculer les coe�cients de Bezoutd'un couple d'entiers. L'algorithme d'Euclide étendu 10 calcule ces coe�cients pour un couple d'entierspositifs.

Le tableau 10 montre une trace de l'exécution de l'algorithme 10 sur les entiers a = 651 et b = 69.

Remarque : Les coe�cients de Bezout ne sont pas uniques. Par exemple, on a pu voir que

pgcd(651, 69) = 651× 30− 69× 283

= 651× 7− 69× 66.

13

Algorithme 10 Algorithme d'Euclide étenduEntrée: a, b deux entiers positifsSortie: d = pgcd(a, b) et u, v coe�cients de Bezout tels que d = au+ bv1: a1 ← a, b1 ← b2: u1 ← 0, u2 ← 1, v1 ← 1, v2 ← 03: tant que b1 6= 0 faire

4: Calculer q, r tels que a1 = b1q + r avec 0 ≤ r < b15: x← u2 − qu1, y ← v2 − qv16: a1 ← b1, b1 ← r7: u2 ← u1, u1 ← x8: v2 ← v1, v1 ← x9: �n tant que

10: retourner d = a1, u = u2, v = v2

i q r u1 u2 v1 v2 a b0 0 1 1 0 651 691 9 30 1 0 -9 1 69 302 2 9 -2 1 19 -9 30 93 3 3 7 -2 -66 19 9 34 3 0 -23 7 217 -66 3 0

3 = 651× 7 + 69×−66

Table 10 � Calcul des coe�cients de Bezout de a = 651 et b = 69 par l'algorithme 10

3.2.4 Inverse modulaire

Un entier a est inversible modulo un entier n si est seulement si a et n sont premiers entre eux,c'est�à�dire si leur pgcd vaut 1.

Dans ce cas les coe�cients de Bezout u et v fournissent la relation

pgcd(a, n) = 1 = nu+ av.

Si on la considère modulo n cette relation donne l'égalité

1 = av (mod n),

ce qui revient à dire que la réduction modulo n du coe�cient v est l'inverse de a dans l'anneau Z/nZ,

a−1 (mod n) = v (mod n).

Pour calculer l'inverse modulo n d'un entier a premier avec n, il su�t de calculer le coe�cient de adans une relation de Bezout et réduire ce coe�cient modulo n. C'est ce que fait l'algorithme 11.

Algorithme 11 Calcul de l'inverse d'un entier inversible modulo un autreEntrée: a ≥ 1, n ≥ 2 deux entiers premiers entre euxSortie: a−1 (mod n) (entier compris entre 1 et n− 1)a1 ← a, b1 ← bv1 ← 1, v2 ← 0tant que b1 6= 0 faire

Calculer q, r tels que a1 = b1q + r avec 0 ≤ r < b1x← u2 − qu1, y ← v2 − qv1aa1 ← b1, b1 ← rv2 ← v2, v1 ← x

�n tant que

retourner v2 (mod n)

Le tableau 11 montre une trace de l'exécution de l'algorithme 10 sur les entiers a = 217 et n = 23.

14

i q r v1 v2 a1 b10 1 0 23 2171 0 23 0 1 217 232 9 10 1 0 23 103 2 3 -2 1 10 34 3 1 7 -2 3 15 3 0 -23 7 1 0

a−1 mod 23 = 7 mod 23 = 7.

Table 11 � Calcul de 217−1 (mod 23) par l'algorithme 11

k 0 1 2 3 4 5 6 7 8 9 10k (mod 11) 0 1 4 9 5 3 3 5 9 4 1

k 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14k (mod 11) 0 1 4 9 1 10 6 4 4 6 10 1 9 4 1

Table 12 � Carrés modulo 11 et modulo 15

3.3 Racines carrées modulo n

Observons les carrés modulo 11 et modulo 15 (cf tables 12).Nous constatons que modulo 11, seuls les nombres 0, 1, 3, 4, 5 et 9 sont des carrés parfaits, et qu'hormis

0, les autres sont carrés de deux nombres. Et modulo 15, seuls 0, 1, 4, 6, 9 et 10 sont des carrés parfaitset que 0 est le carré d'un seul nombre, 6, 9 et 10 sont carrés de deux nombres, et 1 et 4 sont carrés dequatre nombres.

Donc une équation du type

x2 = a (mod n), (1)

dans laquelle n est un entier naturel �xé, a un entier compris entre 0 et n − 1 et x l'inconnue, peutavoir 0, 1 ou plusieurs solutions.

Les questions qui se posent au sujet de l'équation 1 sont

1. comment connaître l'existence d'une solution ?

2. si elle admet des solutions combien en admet-elle ?

3. comment les calculer ?

Nous allons répondre à ces questions d'abord dans le cas où n est un nombre premier, puis ensuitedans le cas particulier où n est le produit de deux nombres premiers impairs.

3.3.1 Cas n = p premier

On considère ici l'équation (1) dans le cas où n est un nombre premier p qu'on supposera impair, lecas p = 2 étant trivial.

Nombre de solutions : Comme l'ensemble Z/pZ des entiers modulo p est un corps lorsque p est unnombre premier (cf section 4), le nombre de solutions que peut avoir une telle équation ne peut pasdépasser deux.

En fait seul dans le cas a = 0 l'équation (1) admet une seule solution. En e�et lorsque a 6= 0, si onvéri�e facilement que si l'équation admet une solution r, alors elle admet aussi n − r pour solution, etcomme p est impair, r et p− r sont de parités di�érentes et donc di�érents.

Donc l'équation 1 avec a 6= 0 possède 0 ou 2 solutions.Lorsqu'elle en possède deux, on dit que l'entier a est un résidu quadratique modulo p.

Décision : Comment décider si un entier a est un résidu quadratique ?Une conséquence du théorème de Lagrange (cf 2.2) est qu'un entier a est un résidu quadratique modulo

un nombre premier p si et seulement si on a

ap−12 (mod p) = 1.

Comme le calcul d'une exponentiation modulaire peut se faire e�cacement grâce à l'algorithme 7, on endéduit un algorithme de décision (cf algo 12)

15

Algorithme 12 Algorithme de décision d'existence d'une racine carrée modulo un nombre premierEntrée: p un nombre premier, a un entier compris entre 1 et p− 1.Sortie: Vrai si a est un résidu quadratique modulo p, Faux dans le cas contraire.s← a

p−12 (mod p)

si s = 1 alors

retourner Vraisinon

retourner Faux�n si

Exemples : Prenons p = 11.

1. Pour a = 9, on a a5 (mod 11) = 1, et donc 9 est un résidu quadratique modulo 11.

2. Pour a = 6, on a a5 (mod p) = 10, et donc 6 n'est pas un résidu quadratique modulo 11.

Calcul des solutions : Nous allons limiter le calcul des solutions dans le cas où p (mod 4) = 3 3.On suppose que a est un résidu quadratique modulo p. Dans ce cas, on peut véri�er que le nombre r

dé�ni parr = a

p+14 (mod p)

est une racine carrée de a. En e�et

r2 = ap+12 = a× a

p−12 = a.

On en déduit donc l'algorithme 13 de calcul des racines de l'équation (1).

Algorithme 13 Calcul de racines carrées modulo un nombre premierEntrée: p un nombre premier congru à 3 modulo 4, et a un résidu quadratique modulo pSortie: les solutions de l'équation x2 = a (mod p)

r ← ap+14 (mod p)

retourner r et p− r

Exemple : Avec p = 11 qui est bien congru à 3 modulo 4, et a = 9, on a

a3 (mod p) = 3,

et donc 3 et 11− 3 = 8 sont les deux solutions de l'équation (1).

3.3.2 Cas n produit de deux nombres premiers

4 Corps

4.1 Structure de corps

Dé�nition 4.1. Un corps est un ensemble K muni de deux opérations internes notées + et × tel que

1. (K,+,×) est un anneau ;

2. tout élément non nul de K possède un inverse pour la multiplication, autrement dit (K \ {0},×)est un groupe.

Exemples

1. Q, R et C munis de l'addition et la multiplication usuelles sont des corps in�nis commutatifs.

2. Si p est un nombre premier Z/pZmuni de l'addition et de la multiplication modulo p est un corps �nicommutatif. On note Fp le corps des entiers modulo p. Ces corps sont appelés corps �nis premiers.

3. Il existe des méthodes de calcul des solutions dans les autres cas un peu plus complexe, mais qui ne nous intéressent

pas.

16

4.2 Propriétés des corps

1. L'élément neutre de l'addition est un élément absorbant pour la multiplication, c'est�à�dire

∀a ∈ K a× 0 = 0× a = 0.

2. Dans un corps, on aa× a′ = 0⇐⇒ a = 0 ou a′ = 0.

Autrement dit, il n'existe pas de diviseurs de 0.

4.3 Corps �nis

Voici quelques propriétés supplémentaires des corps �nis.

1. L'ordre de l'élément neutre de la multiplication 1 dans le groupe additif (K,+) d'un corps �ni Kest un nombre premier. Ce nombre est appelé caractéristique du corps.

2. Le groupe multiplicatif d'un corps �ni est cyclique.

4.4 Construction de corps �nis

4.4.1 Existence de corps �nis non premiers

Les seuls corps �nis que l'on connaît à ce stade sont les corps premiers Fp = Z/pZ avec p premier.Existe-t-il d'autres corps �nis dont le cardinal n'est pas premier ? Nous allons voir que oui mais pas

pour n'importe quel cardinal.

4.4.2 Corps à 4 éléments

Cherchons un corps à quatre éléments K = {0,1, a, b}. Considérons l'ordre m de 1 dans le groupeadditif (K,+). Comme ce groupe est d'ordre 4, m divise nécessairement 4. Donc m = 1, ou 2, ou 4. Deplus, on sait que l'ordre de 1 est un nombre premier. Par conséquent m = 2 et pour tout élément x ∈ K,x + x = 0. En se souvenant que la table d'addition forme un carré latin nous n'avons plus le choix etnous obtenons celle représentée par le tableau 13. Il ressort de cette table d'addition que b = 1 + a (et de

+ 0 1 a b

0 0 1 a b1 1 0 b aa a b 0 1b b a 1 0

Table 13 � Table d'addition du corps à 4 éléments

manière symétrique a = b+ 1).Voyons maintenant la multiplication. Comme 0 est un élément absorbant pour la multiplication, 1

est un élément neutre, et que l'ensemble des éléments non nuls forme un groupe multiplicatif, c'est-à-direque la table de multiplication sans la ligne et colonne correspondant à 0 est un carré latin 3× 3, il n'y aqu'une seule possibilité de remplir cette table (cf 14).

× 0 1 a 1 + a

0 0 0 0 01 0 1 a 1 + aa 0 a 1 + a 1

1 + a 0 1 + a 1 a

Table 14 � Table de multiplication du corps à 4 éléments

Nous avons muni l'ensemble K d'une opération de groupe additif et d'une multiplication tel que leséléments non nuls de K forme aussi un groupe. Il reste à véri�er que la multiplication est distributive parrapport à l'addition, ce que nous laissons à titre d'exercice.

17

Nous avons donc obtenu un corps à quatre éléments F4 = {0,1, a, 1 + a}.On peut remarquer que a2 = 1 + a ou encore a2 − a − 1 = a2 + a + 1 = 0 (souvenons nous qu'en

caractéristique deux, 1 = −1). Autrement dit dans le corps F4, a est une racine du polynôme P (X) =X2 +X + 1 ∈ F2[X] (qui n'en a pas dans F2).

Si on observe bien les éléments de F4 et l'arithmétique obtenue, on peut voir F4 comme l'ensemble despolynômes à coe�cients dans F2 de degré au plus 1. L'addition dans ce corps n'est alors rien d'autre quel'addition usuelle des polynômes et la multiplication dans ce corps rien d'autre que la multiplication despolynômes modulo le polynôme P (X) = X2 + X + 1, la réduction modulo P (X) revenant à considérerque X2 = X + 1.

Remarques : Cette situation est tout à fait analogue à celle utilisée pour dé�nir le corps C des nombrescomplexes, dans lequel on exprime souvent les nombres complexes sous forme algébrique z = a+ ib, aveca, b ∈ R, forme qui exprime les nombres complexes sous forme polynomiale de degré au plus 1 en i. Laforme algébrique de la somme de deux nombres complexes est dé�nie comme la somme des polynômesen i les représentants, et celle du produit par multiplication polynomiale réduite modulo le polynômei2 + 1 = 0 (i2).

Choix du polynôme : Pour dé�nir le corps F4, aurait-on pu choisir un autre polynôme ? Pour l'ad-dition peu importe le choix du polynôme. En revanche, le polynôme in�ue sur la multiplication. Parexemple, aurait-on pu choisir Q(X) = X2 +X ?

La réponse est négative, parce qu'alors on aurait

a(1 + a) = a+ a2 = 0,

et on aurait deux éléments non nuls de K dont le produit est nul, ce qui est impossible dans un corps.L'existence de diviseurs de zéro provient du fait que le polynôme Q(X) = X(1+X) n'est pas irréductibledans F2[X].

4.5 Corps �nis à q = pn éléments

4.5.1 Polynômes irréductibles

Dé�nition 4.2. Soit K un corps, et P (X) ∈ K[X] un polynôme. Le polynôme P est irréductible s'il nepeut pas se mettre sous la forme d'un produit de deux polynômes de degré au moins égal à 1.

Les polynômes irréductibles sont aux polynômes ce que sont les nombres premiers aux nombres entiers.On peut en particulier montrer que tout polynôme se décompose de manière unique (à l'ordre près desfacteurs et à un coe�cient multiplicatif constant près) en un produit de polynômes irréductibles.

Exemples :

1. P (X) = X2 + 1 est irréductible dans R[X].

2. En revanche, P (X) = X2 + 1 n'est pas irréductible dans F2[X].

3. Les polynômes de degré 3 irréductibles dans F2[X] sont X3 +X2 + 1 et X3 +X + 1.

4. De manière générale, tout polynôme de degré 1 est irréductible dans K[X] et ceci quelque soit lecorps, �ni ou non.

Quels sont les polynômes irréductibles ? Combien y en a-t-il ? Comment les reconnaître ? La réponseest facile pour les corps des réels et des complexes.

1. Dans R[X] les polynômes irréductibles sont tous les polynômes de degré 1 et les polynômes de degré2 dont le discriminant (le fameux ∆ = b2 − 4ac) est négatif.

2. Dans C[X] les polynômes irréductibles sont tous les polynômes de degré 1 et eux seulement.

Dans le cas des corps �nis, on admettra le théorème suivant qui donne l'existence de polynômesirréductibles de tout degré.

Théorème 4.1. Soit p un nombre premier. Pour tout entier n ≥ 1 il existe un polynôme irréductible àcoe�cients dans Fp de degré n.

Le théorème suivant donne une condition nécessaire et su�sante pour qu'un polynôme à coe�cientdans un corps �ni soit irréductible.

18

Théorème 4.2. Soit Fq un corps à q Un polynôme P ∈ Fq[X] de degré n ≥ 1 est irréductible si etseulement si

1. P divise le polynôme Xqn −X,

2. et pgcd(Xqn/t −X,P ) = 1 pour tout diviseur premier t de n.

Dès lors que l'on connaît les diviseurs premiers du degré n (ce qui est équivalent à connaître lafactorisation de n) ce théorème donne un algorithme de décision d'irréductibilité d'un polynôme. C'estl'algorithme 14.

Algorithme 14 Test d'irréductibilité d'un polynômeEntrée: P (X) ∈ Fq[X] polynôme de degré n ≥ 1.Sortie: décision sur l'irréductibilité de P .1: A← Xqn (mod P (X))2: si A 6= X alors

3: conclure que P est réductible.4: �n si

5: pour chaque facteur premier t de n faire

6: si pgcd(xqn/t − x, P ) 6= 1 alors

7: conclure que P est réductible.8: �n si

9: �n pour

10: conclure que P est irréductible.

4.5.2 Application à la construction de corps �nis

Théorème 4.3. Soit n ≥ 1 un entier, p un nombre premier et P (X) un polynôme de degré n irréductibledans Fp[X]. Alors l'ensemble Fp[X]/(P (X)) des polynômes à coe�cients dans Fp de degré strictementplus petit que n, muni de l'addition usuelle et de la multiplication modulo P (X) est un coprs �ni à q = pn

éléments.

Ce théorème est analogue au fait que les entiers considérés modulo un nombre premier forment uncorps.

Corollaire 4.1. Soit p un nombre premier. Pour tout entier n ≥ 1 il existe un corps �ni à qn éléments.

Liste des algorithmes

1 Addition de deux entiers multiprecision de même signe . . . . . . . . . . . . . . . . . . . . 32 Addition de deux polynômes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Multiplication de deux entiers multiprécision . . . . . . . . . . . . . . . . . . . . . . . . . 44 Test par recherche du plus petit diviseur . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 Test de non primalité de Miller-Rabin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 Trouver un générateur d'un groupe cyclique . . . . . . . . . . . . . . . . . . . . . . . . . . 107 Exponentiation dans un groupe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 Algorithme d'Euclide pour calculer le pgcd de deux entiers a et b . . . . . . . . . . . . . . 129 Algorithme binaire de calcul du pgcd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1310 Algorithme d'Euclide étendu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1411 Calcul de l'inverse d'un entier inversible modulo un autre . . . . . . . . . . . . . . . . . . 1412 Algorithme de décision d'existence d'une racine carrée modulo un nombre premier . . . . 1613 Calcul de racines carrées modulo un nombre premier . . . . . . . . . . . . . . . . . . . . . 1614 Test d'irréductibilité d'un polynôme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

(version du 5 avril 2012.)

19