summaryrefslogtreecommitdiffstats
path: root/chapitres/corps-finis.tex
blob: 72b88291216a021092530b8e37e6844c12d8efe8 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
\ifx\danslelivre\undefined
\documentclass[9pt]{../configuration/smfart}
\input{../configuration/commun}
\input{../configuration/smf}
\input{../configuration/adresse}
\input{../configuration/gadgets}
\input{../configuration/francais}
\input{../configuration/numerotation}
\input{../configuration/formules}
\input{../configuration/encoredesmacros}

\usepackage{stmaryrd}
\usepackage{wasysym}
\usepackage{graphics}
\usepackage[usenames,dvipsnames]{xcolor}

\usepackage{srcltx}

\title{Corps finis}

\externaldocument{extensions-algebriques}
\externaldocument{algo-corps-finis}
\externaldocument{correspondance-galois}

\begin{document}
\maketitle
\tableofcontents
\else
\chapter{Corps finis}
\fi

\section{Propriétés élémentaires}

\subsection{Caractéristique}

Soit $k$ un corps.  Le noyau de l'unique morphisme d'anneaux $𝐙→k$ est
un idéal premier de $𝐙$.  On rappelle que la \emph{caractéristique} de
$k$ désigne le générateur positif ou nul de cet idéal : on le note
$\car k$.  C'est un nombre premier (souvent noté $p$) ou bien $0$.
Lorsque $\car k$ est un nombre premier $p>0$, l'image de $\ZZ\to k$
est isomorphe à $\ZZ/p\ZZ$.

Pour tout nombre premier $p$, on note $𝐅_p$ le quotient $𝐙/p𝐙$.  C'est
un corps (car c'est un anneau intègre fini) de caractéristique $p$ à
$p$ éléments.  Pour tout corps $k$ de caractéristique $p$, l'image de
$\ZZ \to k$ est un sous-corps de $k$ isomorphe à $\FF_p$, qui est le
plus petit sous-corps de $k$ (car les sous-corps de $k$ sont eux aussi
de caractéristique $p$) et que l'on appelle \emph{corps premier}
de $k$.

On appelle par ailleurs \emph{exposant caractéristique} \index{exposant
caractéristique} de $k$ l'entier valant $1$ si $\car k= 0$ et valant $\car k$ sinon.

\begin{lemme2}\label{structures-sur-corps-premier}
Soit $p$ un nombre premier.

Un groupe abélien $M$ peut être munie d'une structure d'espace
vectoriel sur le corps $\FF_p$ exactement lorsque tout élément $x\in
M$ vérifie $px = 0$, auquel cas cette structure de $\FF_p$-espace
vectoriel est unique.

Un anneau $A$ non nécessairement commutatif peut-être muni d'une
structure de $𝐅_p$-algèbre non nécessairement commutative si et
seulement si l'image de $p$ dans $A$ par le morphisme canonique (et
unique) $𝐙→A$ est nulle.  Cette structure est alors unique.
\end{lemme2}
\begin{proof}
Pour ce qui est de la première affirmation, tout $\FF_p$-espace
vectoriel doit manifestement vérifier $px = 0$ pour tout $x$, et si un
groupe abélien $M$ vérifie cette condition, on peut alors poser $\bar
k\cdot x = k x$, pour tous $k \in \ZZ$, dont on note $\bar k \in
\FF_p$ la classe modulo $p$, et tout $x \in M$, ce qui définit une
structure de $\FF_p$ espace vectoriel sur $M$, qui était la seule
possible car $\bar k = k\cdot \bar 1$ dans $\FF_p$.

En particulier, toute $\FF_p$-algèbre non nécessairement
commutative $A$ doit vérifier $p 1_A = 0$, c'est-à-dire que l'image de
$p$ par le morphisme $\ZZ \to A$ est nulle ; et si cette condition est
satisfaite dans un anneau non nécessairement commutatif $A$ alors $p x
= p 1_A x = 0$ pour tout $x \in A$ donc on vient de voir qu'il y a une
unique façon de mettre sur $A$ une structure de $\FF_p$-espace
vectoriel, qui est clairement une structure de $\FF_p$-algèbre non
nécessairement commutative.
\end{proof}

\begin{lemme2}\label{anneaux-a-p-elements}
Soit $A$ un anneau non nécessairement commutatif ayant $p$ éléments,
où $p$ est un nombre premier.  Alors il existe un unique isomorphisme
entre $\FF_p$ et $A$.
\end{lemme2}
\begin{proof}
L'image du morphisme d'anneaux $\ZZ \to A$ est un sous-anneau de $A$
dont le cardinal doit diviser $p$ ; comme $0_A \neq 1_A$ (sans quoi
$A$ serait l'anneau nul, qui a un seul élément, ce qui n'est pas le
cas), ce cardinal est $p$, c'est-à-dire que $\ZZ \to A$ est surjectif.
Il définit donc un isomorphisme $\ZZ/n\ZZ \buildrel\sim\over\to A$
avec $n$ le générateur positif de son noyau, et en comparant les
cardinaux on voit que $n=p$, de sorte qu'on a un isomorphisme $\FF_p
\buildrel\sim\over\to A$, qui était visiblement le seul possible.
\end{proof}

On peut donc parler \emph{du} corps fini ayant $p$ éléments, et il n'y
a pas de problème à identifier $\FF_p$ au corps premier de n'importe
quel corps de caractéristique $p$.

\begin{proposition2}
Soit $F$ un corps fini.  Alors, la caractéristique de $F$ est un
nombre premier $p>0$ et le cardinal de $F$ est une puissance de $p$.
\end{proposition2}
\begin{démo}[Démonstration de la proposition]
Le morphisme $𝐙→F$ n'est pas injectif car $F$ est fini donc
$\car(F)≠0$.  D'autre part, si $p=\car(F)$, le
lemme \ref{structures-sur-corps-premier} assure que $F$ un
$\FF_p$-espace vectoriel (de façon unique).  Si $r=\dim_{\FF_p}(F)$
(nécessairement finie), on a $\# F=p^r$.
\end{démo}

Il est fréquent, lorsqu'on a affaire à un corps fini, de noter $p$ sa
caractéristique et $q$ son nombre d'éléments (qui en est donc une
puissance), à tel point que ces notations sont parfois utilisées, si
cela ne cause pas de confusion, sans avoir été introduites.  En
particulier, une expression telle que « soit $F$ un corps fini de
  cardinal $p^r$ » sous-entendra toujours que $p$ est un nombre
premier et $r>0$ un entier naturel non nul.

\begin{remarque2}
On peut montrer que tout corps gauche fini est commutatif (théorème de
Wedderburn ; nous en donnerons une démonstration en \ref{Wedderburn}),
ou même que toute algèbre à division alternative mais non
nécessairement associative est un corps fini.
\end{remarque2}

\subsection{Le morphisme de Frobenius}

\begin{proposition2}[petit théorème de Fermat]\label{petit-theoreme-fermat}
Soit $F$ un corps fini ayant $q$ éléments.  Alors tout élément $x$
de $F$ vérifie $x^q = x$.  Plus précisément, les racines du polynôme
$X^q-X$ dans $F$ sont tous les éléments de $F$, chacun avec
multiplicité $1$ : on a
\[
X^q - X = \prod_{a \in F} (X-a)
\]
\end{proposition2}
\begin{proof}
Le groupe multiplicatif $F^×$ des inversibles de $F$ est
d'ordre $q-1$, donc si $x \neq 0$ on a $x^{q-1} = 1$ donc $x^q = x$ ;
le cas $x=0$ est trivial.  Pour ce qui est de la seconde affirmation,
on vient de montrer que $\prod_{a \in F} (X-a)$ divise $X^q-X$, et
comme ces deux polynômes sont unitaires et de même degré, ils sont
égaux.
\end{proof}

\begin{corollaire2}\label{unicite-corps-q-elements-pour-inclusion}
Si $K$ est un corps de caractéristique $p>0$, alors pour toute
puissance $q = p^r$ de $p$, il existe au plus un sous-corps de $K$
ayant $q$ éléments.
\end{corollaire2}
\begin{proof}
Si $F$ est un sous-corps de $K$ à $q$ éléments, alors la
proposition \ref{petit-theoreme-fermat} montre que $F$ est exactement
l'ensemble des racines de $X^q-X$ (dans $F$ donc dans $K$), ce qui
prouve l'unicité.
\end{proof}

Autrement dit, un corps à $q$ éléments est unique comme sous-corps de
n'importe quel sur-corps.  On va voir
en \ref{existence-et-unicite-corps finis} qu'il est également unique à
isomorphisme près (mais pas à isomorphisme unique près).

\begin{proposition2}\label{morphisme-de-frobenius}
Soient $p$ un nombre premier et $A$ une $𝐅_p$-algèbre.  L'application
$\Frob|_A\colon A→A$ donnée par $a↦a^p$ est un \emph{endomorphisme} de $A$.
\end{proposition2}
\begin{démo}
Seule l'identité $\Frob|_A(x+y)=\Frob|_A(x)+\Frob|_A(y)$ n'est pas
évidente.  Elle résulte de la formule du binôme de Newton et de la
congruence $\frac{p!}{i!(p-i)!}≡0\pmod{p}$ pour tout $0<i<p$.
\end{démo}

Ce morphisme est le \emph{Frobenius}\index{Frobenius} de $A$ (ou
\emph{Frobenius absolu}), souvent noté $\Frob|_A$ (ou parfois
$\Frob_A$) ou simplement $\Frob$.  Lorsque cela ne semble pas prêter à
confusion, on notera $A^p⊆A$ son image.

Lorsque $k$ est un corps, $\Frob|_k$ est injectif puisque son noyau
est nul ; par conséquent, lorsque $F$ est un corps fini, $\Frob|_F$
est bijectif, et on en déduit que les corps finis sont parfaits
(\refext{Alg}{corps-parfait}).  En fait, puisque $\Frob^r(x) =
x^{p^r}$, lorsque $F$ est un corps fini ayant $q = p^r$ éléments, la
proposition \ref{petit-theoreme-fermat} se traduit par $(\Frob|_F)^r =
\Id_F$ (on verra plus loin que l'ordre de $\Frob|_F$ est
exactement $r$).

\begin{lemme2}\label{sous-corps-a-q-elements}
Soient $p$ un nombre premier et $q=p^r$ une puissance de $p$.  Soit
$K$ un corps de caractéristique $p$ sur lequel le polynôme $X^q-X$ est
scindé.  Alors l'ensemble $\Fix(\Frob^r_K)$ des racines du polynômes
$X^q-X$ dans $K$ est un sous-corps de $K$ à $q$ éléments (dont on a vu
l'unicité en \ref{unicite-corps-q-elements-pour-inclusion}).
\end{lemme2}
\begin{proof}
L'ensemble des racines de $X^q-X$ est un sous-corps de $K$ puisque
c'est l'ensemble $\Fix(\Frob^r_K)$ des points fixes du morphisme de
corps $\Frob^r_K$.  Comme la dérivée du polynôme $X^q-X$ est $-1$, les
racines de ce polynôme sont toutes simples et il y en a, dans $K$ où
il est supposé scindé, exactement $q$ : ainsi, $\Fix(\Frob^r_K)$ est
bien un sous-corps de $K$ à $q$ éléments.
\end{proof}

\begin{proposition2}\label{existence-et-unicite-corps finis}
Soit $q=p^r$ une puissance d'un nombre premier.  Il existe un corps à
$q$ éléments, unique à isomorphisme près.  Un tel corps est un corps
de décomposition (\refext{Alg}{décomposition}) du polynôme
$X^q-X∈𝐅_p[X]$.
\end{proposition2}
\begin{proof}
L'existence se déduit du lemme \ref{sous-corps-a-q-elements} appliqué
à une clôture algébrique $K$ de $\FF_p$ ou simplement à un corps de
décomposition sur $\FF_p$ de $X^q-X$.  L'unicité se déduit de même :
tout corps fini $F$ à $q$ éléments se plonge dans la clôture
algébrique de $\FF_p$ (car $F$ est algébrique sur $\FF_p$) ou
simplement dans un corps de décomposition sur $\FF_p$ de $X^q-X$ (car
$F$ est engendré par les racines de ce polynôme) et la
proposition \ref{unicite-corps-q-elements-pour-inclusion} montre alors
l'unicité de $F$ dans ce sur-corps qui ne dépendait pas de $F$.  La
dernière affirmation est claire compte tenu
de \ref{unicite-corps-q-elements-pour-inclusion}.
\end{proof}

(On verra en \refext{ACF}{remarque-isomorphisme-explicite-corps-finis} une
façon d'obtenir un isomorphisme explicite entre des présentations
différentes d'un même corps fini.)

Dès lors que $q$ est une puissance stricte d'un nombre premier,
l'isomorphisme n'est plus unique puisque $\Frob\colon x \mapsto x^p$
constitue sur un corps fini à $q$ éléments un automorphisme différent
de l'identité.

On se permettra pourtant de noter, lorsque $q = p^r$ est une puissance
d'un nombre premier, par $\FF_q$ le corps fini à $q$ éléments,
celui-ci étant défini à isomorphisme non unique près ; ou encore, si
un corps contient un sous-corps ayant $q$ éléments (nécessairement
unique en tant que sous-corps, comme on l'a expliqué), on notera
$\FF_q$ ce sous-corps.

Si $q = p^r$, on notera par ailleurs $\Frob_q = (\Frob)^r \colon x
\mapsto x^q$ l'élévation à la puissance $q$ dans n'importe quel corps
de caractéristique $p$ : si le corps en question contient $\FF_q$,
alors $\FF_q$ est exactement l'ensemble des points fixes de $\Frob_q$,
et le morphisme $\Frob_q$, non content d'être $\FF_p$-linéaire, est en
fait $\FF_q$-linéaire.  Plus généralement, on définit $\Frob_q =
(\Frob)^r \colon x \mapsto x^q$ dans n'importe quelle $\FF_q$-algèbre.

\subsubsection{} Les trois lemmes suivants, qui doivent être considérés
comme un tout, ont pour vocation à clarifier le comportement des
polynômes $X^q - X$ lorsque $q$ est remplacé par une certaine
puissance de lui-même.

\begin{lemme2}\label{lemme-divisibilite-x-q-r-x}
Soient $m$ et $n$ deux entiers naturels non nuls tels que $m|n$.
Alors :
\begin{itemize}
\item pour tout entier $q>1$, l'entier $q^m-1$ divise $q^n-1$,
\item le polynôme $X^m-1$ divise $X^n-1$ (dans $\ZZ[X]$ ou, par
conséquent, $A[X]$ pour n'importe quel anneau $A$),
\item pour tout entier $q>1$, le polynôme $X^{q^m}-X$ divise
$X^{q^n}-X$ (de même).
\end{itemize}
\end{lemme2}
\begin{proof}
Le premier point découle de ce que $q^n-1 = (q^m-1)(q^{n-m} + q^{n-2m}
+ \cdots + q^{2m} + q^m + 1)$, comme on le voit en dévelopant.  Le
second découle de même de ce que $X^n-1 = (X^m-1)(X^{n-m} + X^{n-2m}
+ \cdots + X^{2m} + X^m + 1)$.  Le troisième point découle des deux
premiers : puisque $q^m-1$ divise $q^n-1$, le polynôme $X^{q^m-1} - 1$
divise $X^{q^n-1} - 1$, et par conséquent $X^{q^m} - X$ divise
$X^{q^n} - X$.
\end{proof}

\begin{lemme2}\label{lemme-non-divisibilite-x-q-r-x}
Soient $m$ et $n$ deux entiers naturels non nuls et $r$ le reste de la
division euclidienne de $m$ par $n$ ; on suppose $r>0$.  Alors :
\begin{itemize}
\item pour tout entier $q>1$, le reste de la division euclidienne de
$q^m-1$ par $q^n-1$ est $q^r-1$,
\item il existe $g$ dans $\ZZ[X]$ tel que $X^m-1 = (X^n-1) g + (X^r-1)$,
\item pour tout entier $q>1$, il existe $g$ dans $\ZZ[X]$ tel que
$X^{q^m}-X = (X^{q^n}-X) g + (X^{q^r}-X)$.
\end{itemize}
\end{lemme2}
\begin{proof}
Écrivons $m = kn+r$ : le lemme \ref{lemme-divisibilite-x-q-r-x} montre
que $q^{kn} \equiv 1 \pmod{q^n-1}$, et par conséquent $q^m - 1 \equiv
q^r -1 \pmod{q^n-1}$ ; puisque $0 < q^r - 1 < q^n - 1$, on a le
premier point annoncé.  Le second est rigoureusement analogue.  Le
troisième découle des deux premiers : puisque $q^r - 1$ est le reste
de la division euclidienne de $q^m - 1$ par $q^n - 1$, on peut écrire
$X^{q^m-1} - 1 = (X^{q^n-1}-1) g + (X^{q^r-1}-1)$, donc $X^{q^m} - X
= (X^{q^n}-X) g + (X^{q^r}-X)$.
\end{proof}

\begin{lemme2}\label{lemme-pgcd-x-q-r-x}
Soient $m$ et $n$ deux entiers naturels non nuls et $d$ leur pgcd.
Alors :
\begin{itemize}
\item pour tout entier $q>1$, les entiers $q^m-1$ et $q^n-1$ ont pour
pgcd $q^d-1$ (concrètement, il existe $u,v$ entiers tels que $(q^m-1)u
+ (q^n-1)v = q^d-1$),
\item les polynômes $X^m-1$ et $X^n-1$ de $\ZZ[X]$ engendrent l'idéal
$(X^d-1)$ de $\ZZ[X]$ (concrètement, il existe $u,v$ de $\ZZ[X]$ tels
que $(X^m-1)u + (X^n-1)v = X^d-1$),
\item pour tout entier $q>1$, les polynômes $X^{q^m}-X$ et $X^{q^n}-X$
de $\ZZ[X]$ engendrent l'idéal $(X^{q^d}-X)$ de $\ZZ[X]$
(concrètement, il existe $u,v$ de $\ZZ[X]$ tels que $(X^{q^m}-X) u +
(X^{q^n}-X) v = X^{q^d}-X$.
\end{itemize}
\end{lemme2}
\begin{proof}
Avant toute chose, \ref{lemme-divisibilite-x-q-r-x} assure bien que
$q^d-1$ divise $q^m-1$ et $q^n-1$, que $X^d-1$ divise bien $X^m-1$ et
$X^n-1$, et que $X^{q^d}-X$ divise bien $X^{q^m}-X$ et $X^{q^n}-X$.
(Ceci justifie notamment que dire « il existe $u,v$ de $\ZZ[X]$ tels
que $(X^m-1)u + (X^n-1)v = X^d-1$ » traduise bien le fait que $X^m-1$
et $X^n-1$ engendrent l'idéal $(X^d-1)$, et pas un idéal plus gros, et
de même pour les autres points.)

Montrons le premier point par récurrence sur $n$.  Si $n=d$, tout est
clair.  Sinon, soit $r$ le reste de la division euclidienne de $m$
par $n$, qui vérifie bien sûr $r>0$.  Alors le reste de la division
euclidienne de $q^m-1$ par $q^n-1$ vaut $q^r-1$
d'après \ref{lemme-non-divisibilite-x-q-r-x}.  Par conséquent,
$\pgcd(q^m-1,q^n-1) = \pgcd(q^n-1,q^r-1)$.  Comme $n$ et $r$ sont
premiers entre eux, l'hypothèse de récurrence permet de conclure que
ceci vaut $q^d-1$, ce qu'on voulait prouver.

Montrons le second point par récurrence sur $n$.  Si $n=d$, tout est
clair.  Sinon, soit $r$ le reste de la division euclidienne de $m$
par $n$, qui vérifie bien sûr $r>0$.  Alors on peut écrire $X^m-1 =
(X^n-1) g + (X^r-1)$ d'après \ref{lemme-non-divisibilite-x-q-r-x}.
Comme $n$ et $r$ sont premiers entre eux, l'hypothèse de récurrence
permet de trouver une écriture $X^d-1 = (X^n-1)u + (X^r-1)v$ ; en
remplaçant $X^r-1$ par $X^m-1 - (X^n-1) g$, on trouve bien une
écriture $X^d-1 = (X^m-1)u' + (X^n-1)v'$ comme souhaitée.

Le troisième point se démontre encore par récurrence sur $n$.
Si $n=d$, tout est clair.  Sinon, soit $r$ le reste de la division
euclidienne de $m$ par $n$, qui vérifie bien sûr $r>0$.  Alors on peut
écrire $X^{q^m}-X = (X^{q^n}-X) g + (X^{q^r}-X)$
d'après \ref{lemme-non-divisibilite-x-q-r-x}.  Comme $n$ et $r$ sont
premiers entre eux, l'hypothèse de récurrence permet de trouver une
écriture $X^{q^d}-X = (X^{q^n}-X)u + (X^{q^r}-X)v$ ; en remplaçant
$X^{q^r}-X$ par $X^{q^m}-X - (X^{q^n}-X) g$, on trouve bien une
écriture $X^{q^d}-X = (X^{q^m}-X)u' + (X^{q^n}-X)v'$ comme souhaitée.
\end{proof}

\begin{proposition2}\label{inclusions-corps-finis}
Si $q = p^r$ et $q' = p^{\prime r'}$, on a $\FF_q \subseteq \FF_{q'}$
(au sens où $\FF_{q'}$ contient un sous-corps à $q$ éléments, qui est
alors unique et isomorphe à $\FF_q$) si et seulement si $p = p'$ et
$r|r'$.  Le degré de l'extension $\FF_{q'} \bo \FF_q$ est alors $r'/r$.

Si $q = p^r$ et $q' = p^{r'}$ avec $\pgcd(r,r') = r_0$, alors $\FF_q
\cap \FF_{q'} = \FF_{q_0}$ où $q_0 = p^{r_0}$ dans n'importe quel
corps contenant des sous-corps ayant $q$ et $q'$ éléments.
\end{proposition2}
\begin{proof}
Si $\FF_q \subseteq \FF_{q'}$ où $q = p^r$ et $q' = p^{\prime r'}$, on
doit nécessairement avoir $p = p'$ car ce sont les caractéristiques de
ces deux corps.  Par ailleurs, $\FF_{q'}$ est un espace vectoriel de
dimension finie sur $\FF_q$, donc en notant $s$ sa dimension, on a $q'
= q^s$, c'est-à-dire $r' = rs$ et $r|r'$ comme annoncé.

Réciproquement, si $p = p'$ et $r|r'$, alors $q' = q^s$ où $s = r'/r$
est entier, donc le lemme \ref{lemme-divisibilite-x-q-r-x} montre que
$X^{q'} - X$ est multiple de $X^q - X$ (dans $\ZZ[X]$ et en
particulier dans $\FF_{q'}[X]$), et comme $X^{q'}-X$ est scindé sur
$\FF_{q'}$, le polynôme $X^q-X$ l'est aussi, ce qui montre que
$\FF_q \subseteq
\FF_{q'}$ d'après \ref{sous-corps-a-q-elements}.

La seconde affirmation est alors claire : $\FF_q \cap \FF_{q'}$ est un
corps fini qui contient le corps fini à $p^{r_1}$ éléments si et
seulement si $r_1 | r$ et $r_1 | r'$, c'est-à-dire si et seulement si
$r_1 | r_0$ où $r_0 = \pgcd(r,r')$ --- autrement dit, il s'agit
justement de $\FF_{q_0}$.
\end{proof}

\section{Polynômes irréductibles}

\subsection{Polynômes minimaux et éléments conjugués}

Lorsque $x \in \FF_{q^r}$, on rappelle que le \emph{polynôme minimal}
(\refext{Alg}{polynome-minimal}) de $x$ sur $\FF_q$ (lequel est un
sous-corps de $\FF_{q^r}$ d'après \ref{inclusions-corps-finis}) est le
polynôme unitaire $h \in \FF_q[X]$ engendrant l'idéal dans $\FF_q[X]$
des polynômes $f$ tels que $f(x) = 0$, et que c'est l'unique polynôme
unitaire irréductible dans $\FF_q[X]$ s'annulant en $x$ ; son degré
est le degré $s = [\FF_q(x) : \FF_q]$ de $x$ sur $\FF_q$, qui divise
le degré $r = [\FF_{q^r} : \FF_q]$ de l'extension.  De plus, dans ces
conditions, on a $\FF_q(x) \cong \FF_q[X]/(h) \cong \FF_{q^s}$ : en
particulier, d'après \ref{petit-theoreme-fermat}, l'élément $x$
vérifie $x^{q^s} = x$, et $h(X) | (X^{q^s}-X)$.  Réciproquement, on
rappelle que si $h \in \FF_q[X]$ est un polynôme irréductible
quelconque alors $\FF_q[X]/(h)$ est un corps, et la classe $x$ de $X$
modulo $h$ (c'est-à-dire dans $\FF_q[X]/(h) = \FF_q(x)$) a $h$ pour
polynôme minimal.

\begin{proposition2}\label{racines-polynome-minimal-corps-fini}
Lorsque $x \in \FF_{q^r}$ a pour polynôme minimal $h$ sur $\FF_q$ et
degré $s$ (divisant $r$), alors le polynôme $h$ est scindé sur
$\FF_{q^r}$ et ses racines sont $x, x^q, x^{q^2}, \ldots,
x^{q^{s-1}}$ :
\[
h(X) = \prod_{i=0}^{s-1} (X-\Frob_q^i(x))
\]
\end{proposition2}
\begin{proof}
Puisque $h \in \FF_q[X]$ et que $\Frob_q$ est un automorphisme de
$\FF_{q^r}$ fixant $\FF_q$, on a $h(\Frob_q^i(x)) =
\Frob_q^i(h(x)) = 0$ pour tout $i$, c'est-à-dire que les $x^{q^i}$
sont racines de $h$.  Montrons maintenant que $x, x^q, \ldots,
x^{q^{s-1}}$ sont deux à deux distincts, c'est-à-dire que l'ordre de
$\Frob_q$ agissant sur $x$ (qui doit diviser $s$, comme on l'a
expliqué) est exactement $s$ : or si on a $x^{q^t} = x$ pour $t \leq
s$, on a $x \in \FF_{q^t}$ donc le degré $s$ de $x$ sur $\FF_q$
diviserait $t$, ce qui n'est possible que pour $t=s$.  Finalement, on
a trouvé $s$ racines distinctes dans $\FF_{q^r}$ pour un
polynôme ($h$) de degré $s$, c'est-à-dire que ce polynôme est scindé
avec la décomposition annoncée.
\end{proof}

Le phénomène qu'on vient de mettre en évidence, bien particulier aux
corps finis, et qui traduira le fait que leur groupe de Galois absolu
est abélien, est que pour tout polynôme irréductible $h \in
\FF_q[X]$, le polynôme $h$ est scindé sur n'importe quel corps qui
en contient une racine, autrement dit, \emph{le corps de
rupture $\FF_q[X]/(h)$ de $h$ en est un corps de décomposition}.  En
particulier, en utilisant \ref{inclusions-corps-finis}, $\FF_{q^r}$
est un corps de décomposition de $h$ (supposé irréductible !) pour
tout multiple $r$ du degré de $h$.  Si $h$ n'est pas supposé
irréductible, il découle de ce qui vient d'être dit que \emph{son
corps de décompossition est $\FF_{q^r}$ où $r$ est le plus petit
commun multiple des degrés des facteurs irréductibles de $h$}.

De plus, on vient de voir que l'ordre de $\Frob_q$ agissant sur $x$
--- ou, par conséquent, sur $\FF_q(x)$ --- est exactement le degré $s$
de $x$ sur $\FF_q$.  En utilisant le théorème de l'élément
primitif (\refext{Alg}{element-primitif}), on peut conclure que
$\Frob_q$ agissant sur $\FF_{q^r}$ est d'ordre exactement $r$ ; on
fournira toutefois
en \ref{existence-polynome-irreductible-tout-degre-corps-finis} une
démonstration plus simple du théorème de l'élément primitif dans le
cas particulier des corps finis.

\begin{corollaire2}\label{elements-conjugues-corps-finis}
Soient $x,x' \in \FF_{q^r}$.  Les conditions suivantes sont
équivalentes :
\begin{enumerate}
\item les polynômes minimaux de $x$ et $x'$ sur $\FF_q$ sont égaux,
\item le polynôme minimal de $x$ s'annule en $x'$,
\item tout polynôme $f \in \FF_q[X]$ à coefficient dans $\FF_q$
  s'annulant en $x$ s'annule aussi en $x'$,
\item il existe $i$ (qu'on peut supposer compris entre $0$ et $r-1$)
  tel que $x' = x^{q^i}$.
\end{enumerate}
\end{corollaire2}
\begin{proof}
L'équivalence entre les deux premières conditions (qui n'a rien de
particulier au cas des corps finis) résulte du fait que le polynôme
minimal d'un élément sur $\FF_q$ est l'unique polynôme unitaire
irréductible sur $\FF_q$ s'annulant en cet élément.  L'équivalence
avec la troisième résulte de ce que les polynômes de $\FF_q[X]$
s'annulant en un élément de $\FF_{q^r}$ sont exactement les multiples
du polynôme minimal de cet élément.

Enfin, la proposition précédente montre que, quel que soit $x \in
\FF_{q^r}$, les autres racines de son polynôme minimal sont justement
les $x^{q^i}$ (pour $i$ qu'on peut supposer entre $0$ et $r-1$) : il y
a donc équivalence entre (ii) et (iv).
\end{proof}

Des éléments $x,x' \in \FF_{q^r}$ vérifiant les conditions
équivalentes énoncées dans le
corollaire \ref{elements-conjugues-corps-finis} sont dits
\emph{conjugués sur $\FF_q$}.  La première condition montre qu'il
s'agit bien d'une relation d'équivalence, et la seconde, que tout
élément de $\FF_{q^r}$ a un nombre de conjugués sur $\FF_q$ égal à son
degré sur $\FF_q$.  (Cette définition et ces propriétés seront
généralisées plus tard dans le cadre d'une extension de corps plus
générale : cf. \refext{CG}{conjugues=racines}.)

La proposition suivante généralise la dernière affirmation
de \ref{petit-theoreme-fermat} :
\begin{proposition2}\label{factorisation-x-q-r-x}
La décomposition en facteurs irréductibles du polynôme $X^{q^r} - X$
dans $\FF_q[X]$ est donnée comme le produit de tous les polynômes
unitaires irréductibles de $\FF_q[X]$ de degré divisant $r$, chacun
apparaissant avec multiplicité $1$.

Notamment, la somme des degrés de tous les polynômes unitaires
irréductibles de $\FF_q[X]$ de degré divisant $r$ vaut $q^r$.
\end{proposition2}
\begin{proof}
Si $h \in \FF_q[X]$ est irréductible de degré $s$ avec $s|r$, alors
il est scindé à racines simples dans $\FF_{q^r}$ d'après
\ref{racines-polynome-minimal-corps-fini} et les remarques qui
suivent : il s'ensuit que $h$ divise $X^{q^r} - X$ (dans
$\FF_{q^r}[X]$ donc dans $\FF_q[X]$).  Comme tous les polynômes
unitaires irréductibles de degré divisant $r$ dans $\FF_q[X]$ sont
deux à deux premiers entre eux, le fait que $X^{q^r}-X$ soit multiple
de chacun d'eux implique qu'il est multiple de leur produit.  Pour
conclure, il reste donc à montrer l'égalité des degrés, c'est-à-dire
la dernière affirmation de l'énoncé : or cela se voit en écrivant
$q^r$ (le cardinal de $\FF_{q^r}$) comme somme des cardinaux de chaque
classe de conjugaison d'éléments sur $\FF_q$ (chacune étant associée à
un unique polynôme minimal, dont elle a un cardinal égal au degré).
\end{proof}

\begin{exemple2}\label{irreductibles-sur-f16}
Le polynôme $X^{16}-X$ se factorise sur $\FF_2$ comme : $X^{16}-X =
X(X+1)\penalty-100 (X^2+X+1)\penalty-100 (X^4+X+1)\penalty0
(X^4+X^3+1)\penalty-50 (X^4+X^3+X^2+X+1)$.
\end{exemple2}

\subsubsection{}\label{definition-fonction-de-Moebius} On appelle \emph{fonction de Möbius} la fonction $\mu \colon \NN \to
\ZZ$ définie par $\mu(n) = 0$ si $n$ est multiple du carré d'un entier
autre que $1$ et $\mu(n) = (-1)^t$ si $n = p_1\cdots p_t$ avec
$p_1,\ldots,p_t$ des nombres premiers deux à deux distincts (ainsi,
$\mu(1) = 1$, $\mu(2) = -1$, $\mu(3) = -1$, $\mu(4) = 0$, $\mu(5) =
-1$, $\mu(6) = 1$, $\mu(7) = -1$, $\mu(8) = 0$, $\mu(9) = 0$, $\mu(10)
= 1$).  On admet le résultat suivant :
\begin{proposition2}[théorème d'inversion de Möbius]
Si $\Gamma$ est un groupe abélien et que $f\colon \NN_{>0} \to \Gamma$
est une fonction quelconque, alors les deux formules suivantes sont
équivalentes pour une fonction $g\colon \NN_{>0} \to \Gamma$ :
\[
g(n) = \sum_{d|n} f(d)
\]
\[
f(n) = \sum_{d|n} \mu\big(\frac{n}{d}\big)\, g(d)
\]
\end{proposition2}

\begin{corollaire2}\label{denombrement-polynomes-irreductibles-corps-finis}
Le nombre de polynômes unitaires irréductibles de degré $n$
sur $\FF_q$ vaut
\[
\frac{1}{n} \sum_{d|n} \mu\big(\frac{n}{d}\big)\, q^d
\]
Où $\mu$ est la fonction de Möbius.  Lorsque $n \to +\infty$ (à $q$
fixé), ce nombre vaut $\frac{1}{n} q^n + O(q^{n/2})$.
\end{corollaire2}
\begin{proof}
Pour ce qui est de la première affirmation, en notant $M(n)$ le nombre
--- qu'on cherche à calculer --- d'unitaires irréductibles de
degré $n$ sur $\FF_q$, la formule d'inversion de Möbius montre qu'il
suffit de prouver $q^n = \sum_{d|n} d\,M(d)$ : or c'est justement la
deuxième affirmation de l'énoncé de la
proposition \ref{factorisation-x-q-r-x}.

Pour ce qui est de l'estimation asymptotique, remarquons que dans la
somme exacte, le terme $d=n$ vaut $\frac{1}{n} q^n$, le terme
$d=\frac{n}{2}$, s'il existe (c'est-à-dire, si $n$ est pair), vaut
$-\frac{1}{n} q^{n/2}$, et tous les autres termes, dont le nombre est
au plus $n$, sont chacun $O(q^{n/3})$ --- leur somme est donc
bien $O(q^{n/2})$.
\end{proof}

Même sans utiliser la formule d'inversion de Möbius, on peut au moins
démontrer, dans le même esprit que cette estimation asymptotique :
\begin{corollaire2}\label{existence-polynome-irreductible-tout-degre-corps-finis}
Sur $\FF_q$, il existe au moins un polynôme irréductible de chaque
degré $r$.  De façon équivalente, dans $\FF_{q^r}$, il existe un
élément de degré $r$ sur $\FF_q$.
\end{corollaire2}
\begin{proof}
Le nombre d'éléments de $\FF_{q^r}$ de degré $<r$ est majoré par la
somme des cardinaux des $\FF_{q^s}$ pour $s|r$, or chacun est de
cardinal $\leq q^{r/2}$ et leur nombre est $\leq r$, par conséquent
cette somme de cardinaux est inférieure ou égale à $r q^{r/2}$.  Pour
avoir la conclusion souhaitée, il suffit d'avoir $q^r > r q^{r/2}$,
soit $q^{r/2} > r$, ce qui se produit dès que $2^r > r^2$, donc dès
que $r > 4$.  Pour les valeurs plus petites de $r$, on constate que
$q^4 > q^2 + q$ et $q^3 > q$ et $q^2 > q$ (et $q > 0$...) pour tout $q
\geq 2$.
\end{proof}

On verra en \ref{cyclicite-groupe-multiplicatif-corps} un résultat
plus fin : l'existence d'éléments ou de polynômes \emph{primitifs}.

Avec les remarques qui
suivent \ref{racines-polynome-minimal-corps-fini}, ceci montre
notamment que $\Frob_q$ agissant sur $\FF_{q^r}$ est d'ordre
exactement $r$.

\subsection{Critères d'irréductibilité}

\begin{proposition2}[critère d'irréductibilité de Rabin]\label{critere-rabin}
Un polynôme $h \in \FF_q[X]$ de degré $r$ est irréductible si et
seulement si il vérifie la conjonction des deux conditions
suivantes :
\begin{itemize}
\item le polynôme $h$ divise $X^{q^r}-X$,
\item le polynôme $h$ est premier avec $X^{q^s}-X$ pour tout $s$
diviseur strict de $r$ (ou simplement les diviseurs immédiats de $r$,
c'est-à-dire les $r/\ell$ avec $\ell$ diviseur premier de $r$).
\end{itemize}
\end{proposition2}
\begin{proof}
Si $h$ est irréductible de degré $r$, alors,
d'après \ref{factorisation-x-q-r-x}, $h$ divise $X^{q^r}-X$, et s'il
divise $X^{q^s}-X$ pour $s|r$, on doit avoir $r|s$, ce qui n'est
possible que pour $s=r$ et la seconde condition est démontrée
($h$ étant supposé irréductible, s'il ne divise pas $X^{q^s}-X$, il
est premier avec lui).

Réciproquement, si $h$ vérifie les deux conditions annoncées, et si
$h_1$ en est un facteur irréductible, le degré $r_1$ de $h_1$ doit
diviser $r$ d'après la première condition (toujours en
utilisant \ref{factorisation-x-q-r-x}), et il ne peut pas être un
diviseur strict de $r$ d'après la seconde condition (qui assure que
$h_1$ ne divise pas $X^{q^s}-X$) : donc $r_1=r$ et $h_1=h$.  Ceci
montre que $h$ est irréductible.

Le fait qu'il suffise de tester la seconde condition pour les
diviseurs $s$ de la forme $r/\ell$ avec $\ell$ premier résulte de ce
que $X^{q^s}-X$ divise $X^{q^{s'}}-X$ si $s|s'$.
\end{proof}

\begin{remarques2}\label{remarques-critere-rabin}
\begin{itemize}
\item On ne peut pas se contenter de vérifier l'une des deux conditions
énoncées : l'exemple du polynôme $X^6+X^5+X^4+X^3+X^2+X+1 =
(X^3+X^2+1)\penalty-100 (X^3+X+1) \in \FF_2[X]$, qui n'est pas
irréductible mais vérifie la première condition (il divise déjà
$X^8-X$) montre que la première condition, seule, n'assure pas
l'irréductibilité ; et l'exemple du polynôme $X^5 + X^4 + 1 =
(X^2+X+1)\penalty-100 (X^3+X+1) \in \FF_2[X]$, qui n'est pas
irréductible mais est premier à $X^2-X$ montre que la seconde
condition, seule, n'est pas non plus suffisante.  On peut aussi donner
l'exemple de $X^6 + X^5 + X = X (X^2+X+1) (X^3+X+1) \in \FF_2[X]$, qui
n'est pas irréductible bien qu'il vérifie la première condition et
aussi la seconde condition dans laquelle on a affaibli « $h$ est
premier avec $X^{q^s}-X$ » en « $h$ ne divise pas $X^{q^s}-X$ » (pour
tout diviseur $s$ de $r$, soit ici $s \in \{1,2,3\}$).
\item Le critère de Rabin fournit un \emph{algorithme} permettant de
tester l'irréductibilité d'un polynôme $h \in \FF_q[X]$ de degré $r$
en un nombre raisonnable (i.e., polynomial\footnote{On peut par
exemple montrer qu'il s'effectue en au pire $O(r^{2+\varepsilon})$
opérations pour tout $\varepsilon>0$, où la constante impliquée par
le $O$ dépend de $\varepsilon$ et $q$.} en $r$) d'opérations
dans $\FF_q$ : en effet, la première condition du critère s'exprime
également comme $X^{q^r} \equiv X \pmod{h}$, ce qui se teste en
calculant $X^{q^r}$ dans $\FF_q[X]/(h)$ au moyen d'un algorithme
d'exponentiation rapide, et la seconde condition, pour un $s$ donné,
peut se tester au moyen de l'algorithme d'Euclide étendu (pour
calculer le pgcd), dont la première étape consiste à calculer le reste
de la division euclidienne de $X^{q^s}-X$ par $h$, ce qui peut de
nouveau se faire en travaillant dans $\FF_q[X]/(h)$.
\item Une fois qu'on dispose d'un algorithme permettant de tester
l'irréductibilité d'un polynôme $h \in \FF_q[X]$ de degré $r$ donné,
il est possible de \emph{générer} des polynômes irréductibles de
degré $r$ selon le principe simple suivant : tirer un polynôme
(unitaire) de degré $r$ au hasard, tester son irréductibilité, et
recommencer jusqu'à trouver un polynôme irréductible.  En vertu de
l'asymptotique trouvée
en \ref{denombrement-polynomes-irreductibles-corps-finis}, parmi les
$q^r$ polynômes unitaires de degré $r$ sur $\FF_q$, une proportion
d'environ $\frac{1}{r}$ d'entre eux sont irréductibles, donc
l'algorithme qu'on vient de décrire réussira en environ $r$ essais en
moyenne.  Enfin, il convient de remarquer que la connaissance d'un
polynôme $h$ irréductible de degré $r$ sur $\FF_p$ permet de
représenter $\FF_{p^r}$ comme $\FF_p[X]/(h)$ (les calculs dans $\FF_p
= \ZZ/p\ZZ$ sont, pour leur part, faciles) : en combinant avec ce qui
vient d'être dit, on dispose des outils algorithmiques permettant
d'effectuer des calculs dans tous les corps finis.
\end{itemize}
\end{remarques2}

\begin{exemple2}\label{exemple-numerique-critere-rabin}
Montrons sur l'exemple de $h = X^6 -2 X^4 + 3 X^3 - X^2 - X -
2 \in \FF_7[X]$ comment on peut appliquer le critère de Rabin en
pratique, même sans ordinateur.  On commence par calculer la table des
restes modulo $h$ des puissances $X^7, X^{7\times 2}, X^{7\times
3}, \ldots, X^{7\times 6}$ de l'indéterminée :
\[
\begin{array}{r@{\,}l}
X^7 &\equiv 2X^5 - 3X^4 + X^3 + X^2 + 2X \pmod{h}\\
X^{14} &\equiv -3X^5 - 2X^4 + 2X^3 + 2X^2 + 2X + 2 \pmod{h}\\
X^{21} &\equiv -2X^5 + 3X^4 - 3X^3 - X^2 - 1 \pmod{h}\\
X^{28} &\equiv 3X^5 - 3X^4 - 2X^3 + 2X \pmod{h}\\
X^{35} &\equiv X^5 - 3X^4 - 2X^3 - 2X + 3 \pmod{h}\\
X^{42} &\equiv -3X^5 + X^4 + X^3 - X^2 + X \pmod{h}\\
\end{array}
\]
(la première ligne se calcule par division euclidienne de $X^7$
par $h$, puis chaque ligne suivante en multipliant par $2X^5 - 3X^4 +
X^3 + X^2 + 2X$ et en effectuant une nouvelle division euclidienne
par $h$).  Il est également utile de préparer une table des valeurs du
Frobenius sur le corps de base : ici, $a \mapsto a^7$ sur $\FF_7$ est
bien sûr l'identité.  Au moyen de ces deux tables, on peut facilement
élever n'importe quel polynôme à la puissance $7$ modulo $h$, donc
calculer $X^{7^i}$ pour $i$ allant de $1$ à $6$ modulo $h$ :
\[
\begin{array}{r@{\,}l}
X^7 &\equiv 2X^5 - 3X^4 + X^3 + X^2 + 2X \pmod{h}\\
X^{7^2} &\equiv 2^7 X^{35} - 3^7 X^{28} + X^{21} + X^{14} + 2^7 X^7\\
&\equiv -X^5 - 2X^4 + 3X^3 + 3X^2 + 3X \pmod{h}\\
X^{7^3} &\equiv -X^{35} - 2^7 X^{28} + 3^7 X^{21} + 3^7 X^{14} + 3^7 X^7\\
&\equiv -2X^5 + 3X^4 - X^3 - X^2 + 3X \pmod{h}\\
X^{7^4} &\equiv -2^7 X^{35} + 3^7 X^{28} - X^{21} - X^{14} + 3^7 X^7\\
&\equiv -3X^5 + X^4 + 2X^3 + 2X^2 \pmod{h}\\
X^{7^5} &\equiv -3^7 X^{35} + X^{28} + 2^7 X^{21} + 2^7 X^{14} \\
&\equiv -3 X^5 + X^4 + 2 X^3 + 2 X^2 - 2 X \pmod{h}\\
X^{7^6} &\equiv -3^7 X^{35} + X^{28} + 2^7 X^{21} + 2^7 X^{14} - 2^7 X^7 \\
&\equiv X \pmod{h}\\
\end{array}
\]
L'égalité $X^{7^6} \equiv X \pmod{h}$ montre que la première partie du
critère de Rabin est vérifiée.  Pour la seconde partie, il s'agit de
continuer l'algorithme d'Euclide pour calculer le pgcd de $X^{7^2} -
X \equiv -X^5 - 2X^4 + 3X^3 + 3X^2 + 2X$ et de $X^{7^3} - X\equiv
-2X^5 + 3X^4 - X^3 - X^2 + 2X$ avec $h$ : or au prix de nouvelles
divisions euclidiennes, on trouve
\[
\begin{array}{c}
h \equiv -2X^4 + 2X^2 + 2X - 2 \pmod{-X^5 - 2X^4 + 3X^3 + 3X^2 + 2X}\\
-X^5 - 2X^4 + 3X^3 + 3X^2 + 2X \equiv 2X^3 + X + 2 \pmod{-2X^4 + 2X^2 + 2X - 2}\\
-2X^4 + 2X^2 + 2X - 2 \equiv 3 X^2 - 3 X - 2 \pmod{2X^3 + X + 2}\\
2X^3 + X + 2 \equiv 2 X + 1 \pmod{3 X^2 - 3 X - 2}\\
3 X^2 - 3 X - 2 \equiv 2 \pmod{2X + 1}\\
\end{array}
\]
ce qui montre que $X^{7^2} - X$ est premier avec $h$, et pour ce qui
est de $X^{7^3} - X$ :
\[
\begin{array}{c}
h \equiv -2X^4 + X^2 - 3X - 2 \pmod{-2X^5 + 3X^4 - X^3 - X^2 + 2X}\\
-2X^5 + 3X^4 - X^3 - X^2 + 2X \equiv -2X^3 + 3X - 3 \pmod{-2X^4 + X^2 - 3X - 2}\\
-2X^4 + X^2 - 3X - 2 \equiv -2X^3 + 3X - 3 \pmod{-2X^3 + 3X - 3}\\
-2X^3 + 3X - 3 \equiv -2 X^2 - 2 \pmod{-2X^3 + 3X - 3}\\
-2X^3 + 3X - 3 \equiv -2 X - 3 \pmod{-2 X^2 - 2}\\
-2 X^2 - 2 \equiv -3 \pmod{-2 X - 3}\\
\end{array}
\]
--- ce qui conclut la vérification du critère de Rabin.  Tous ces
calculs montrent donc que $h = X^6 -2 X^4 + 3 X^3 - X^2 - X - 2$ est
irréductible dans $\FF_7[X]$.

Par la suite, nous passerons normalement sous silence toutes les
vérifications du fait qu'un polynôme univarié à coefficiens dans un
corps fini est irréductible.
\end{exemple2}

Le critère suivant, dans le même esprit que celui de Rabin, et plus
simple à énoncer, est plus généralement efficace quand il s'agit de
générer des polynômes irréductibles par le procédé expliqué à la fin
de \ref{remarques-critere-rabin} :
\begin{proposition2}[critère d'irréductibilité de Ben-Or]\label{critere-ben-or}
Un polynôme $h \in \FF_q[X]$ de degré $r$ est irréductible si et
seulement si $h$ est premier avec $X^{q^i}-X$ pour tout $1 \leq i \leq
\frac{r}{2}$ (c'est-à-dire $1 \leq i \leq \lfloor\frac{r}{2}\rfloor$
où $\lfloor\tiret\rfloor$ désigne la partie entière).
\end{proposition2}
\begin{proof}
D'après \ref{factorisation-x-q-r-x}, les facteurs irréductibles de
$X^{q^i}-X$ pour un $1\leq i<r$ ont pour degré les diviseurs de
ce $i$, qui sont tonc toujours strictement inférieurs à $r$ : ceci
montre qu'un $h$ irréductible de degré $r$ est premier avec tous les
$X^{q^i}-X$ pour $1\leq i<r$ (et en particulier $1 \leq
i \leq \frac{r}{2}$).  Réciproquement, si $h$ a un facteur
irréductible $h_1$ de degré $r_1<r$, alors on peut supposer
$r_1 \leq \frac{r}{2}$ (quitte à remplacer $h_1$ par un facteur
irréductible de $h/h_1$ si ce n'est pas le cas), et dans ce cas $h_1$
divise $X^{q^{r_1}}-X$ donc $h$ n'est pas premier avec ce dernier.
\end{proof}

Le critère d'irréductibilité suivant utilise, pour sa part, l'algèbre
linéaire plutôt que des manipulations de polynômes (on rappelle que
$h \in \FF_q[X]$ est dit \emph{séparable} lorsque $h$ est à racines
simples dans une clôture algébrique de $\FF_q$, c'est-à-dire,
concrètement, lorsque $h$ et $h'$ sont premiers entre eux, ce qui peut
se tester algorithmiquement par l'algorithme d'Euclide ; comme les
corps finis sont parfaits, cela équivaut encore à dire que $h$ est
sans facteur carré, cf. \ref{rappels-polynomes-sans-facteurs-carres-corps-finis}).
\begin{proposition2}[critère d'irréductibilité de Butler]\label{critere-butler}
Un polynôme $h \in \FF_q[X]$ de degré $r$ séparable est irréductible
si et seulement si $\dim_{\FF_q} \Ker(\Frob_q - \Id) = 1$, où
$\Frob_q \colon x \mapsto x^q$ et $\Id \colon x \mapsto x$ sont vus
comme des applications $\FF_q$-linéaires sur $\FF_q[X]/(h)$.
\end{proposition2}
\begin{proof}
Si $h$ est irréductible alors $\FF_q[X]/(h)$ est un corps (isomorphe
à) $\FF_{q^r}$ dans lequel $\Ker(\Frob_q - \Id)$ est le sous-corps
$\FF_q$ qui est donc de dimension $1$ comme $\FF_q$-espace vectoriel.

De façon générale, quel que soit $h \in \FF_q[X]$, le $\FF_q$-espace
vectoriel $\Ker(\Frob_q - \Id)$ contient au moins celui engendré
par $1$, donc sa dimension est au moins $1$ : il reste à prouver que
si $h$ est réductible cette dimension doit être strictement
supérieure.  Si $h = h_1 h_2$ avec $h_1,h_2$ premiers entre eux, on a
$\FF_q[X]/(h) \cong \FF_q[X]/(h_1) \times \FF_q[X]/(h_2)$ par le
théorème chinois, donc la dimension de $\Ker(\Frob_q - \Id)$ sur tout
cet espace vaut au moins $1+1=2$.
\end{proof}

Il sera de nouveau question de $\Ker(\Frob_q - \Id)$ (l'\emph{algèbre
de Berlekamp} de $h$) dans la
proposition \refext{ACF}{proposition-algorithme-berlekamp} qui généralise le
critère ci-dessus.

\begin{exemple2}\label{exemple-numerique-critere-butler}
Reprenons l'exemple du polynôme $h = X^6 -2 X^4 + 3 X^3 - X^2 - X -
2 \in \FF_7[X]$ de \ref{exemple-numerique-critere-rabin} en lui
appliquant cette fois le critère de Butler : il faut d'abord vérifier
que $h$ est séparable, c'est-à-dire, premier avec sa dérivée $h' =
-X^5 - X^3 + 2 X^2 - 2 X - 1$, ce qui se fait au moyen de l'algorithme
d'Euclide :
\[
\begin{array}{c}
h \equiv -3 X^4 - 2 X^3 - 3 X^2 - 2 X - 2 \pmod{h'}\\
h' \equiv -2 X^3 + 2 X^2 - X - 3 \pmod{-3 X^4 - 2 X^3 - 3 X^2 - 2 X - 2}\\
-3 X^4 - 2 X^3 - 3 X^2 - 2 X - 2 \equiv -3 X^2 - 2 X + 2 \pmod{-2 X^3 + 2 X^2 - X - 3}\\
-2 X^3 + 2 X^2 - X - 3 \equiv -3 X \pmod{-3 X^2 - 2 X + 2}\\
-3 X^2 - 2 X + 2 \equiv 2\pmod{-3 X}\\
\end{array}
\]
(la dernière ligne de calcul est, en fait, inutile : tout polynôme de
coefficient constant non nul est premier avec un multiple nul de
l'indéterminée).  On calcule alors la matrice de l'endomorphisme
$\Frob_7 - \Id$ sur la base $1, X, X^2, \ldots, X^5$ de
$\FF_7[X]/(h)$, en calculant successivement $X^7, X^{14}, \ldots,
X^{35}$ modulo $h$ --- les calculs sont donc très semblables à ceux
menés au début de \ref{exemple-numerique-critere-rabin} et conduisent
à :
\[
\Frob_7 = \left(
\begin{matrix}
1& 0& 2&-1& 0& 3\\
0& 2& 2& 0& 2&-2\\
0& 1& 2&-1& 0& 0\\
0& 1& 2&-3&-2&-2\\
0&-3&-2& 3&-3&-3\\
0& 2&-3&-2& 3& 1\\
\end{matrix}
\right)
\;,\;\;
\Frob_7-\Id = \left(
\begin{matrix}
0& 0& 2&-1& 0& 3\\
0& 1& 2& 0& 2&-2\\
0& 1& 1&-1& 0& 0\\
0& 1& 2& 3&-2&-2\\
0&-3&-2& 3& 3&-3\\
0& 2&-3&-2& 3& 0\\
\end{matrix}
\right)
\]
(Les coefficients de la première matrice sont les coefficients des
restes de $X^7, X^{14}, X^{21},\ldots, X^{35}$ modulo $h$, comme
calculés en \ref{exemple-numerique-critere-rabin}.)  On calcule le
rang de cette deuxième matrice en appliquant l'algorithme du pivot de
Gauß : on se convainc ainsi que les cinq colonnes non-nulles sont
linéairement indépendantes, c'est-à-dire que le rang est $5$, ce qui
prouve bien $\dim_{\FF_7} \Ker(\Frob_7 - \Id) = 1$, donc $h$ est bien
irréductible.
\end{exemple2}

\subsection{Polynômes irréductibles et extensions}

\subsubsection{} Nous étudions maintenant ce que devient un polynôme
irréductible sur un corps fini lorsque ce dernier est remplacé par une
extension (d'abord de degré divisant le degré du polynôme, puis
premier avec lui, et enfin en corollaire dans le cas général).

\begin{proposition2}\label{scindage-partiel-polynomes-corps-finis}
Soit $f \in \FF_q[X]$ irréductible de degré $r$, et $s$ un diviseur
de $r$.  Alors $f$ vu dans $\FF_{q^s}[X]$ est produit de $s$ facteurs
irréductibles chacun de degré $r/s$.  Si $h$ est l'un de ces facteurs,
alors tous sont donnés par les $\Frob_q^i(h)$ (où par là on désigne le
polynôme de même degré que $h$, dont les coefficients sont image de
ceux de $h$ par $\Frob_q^i$, sans faire agir ce dernier sur
l'indéterminée) pour $i$ allant de $0$ à $s-1$.
\end{proposition2}
\begin{proof}[Première démonstration]
Puisque $f$ est irréductible sur $\FF_q$, on
sait (\ref{factorisation-x-q-r-x}) qu'il divise $X^{q^r}-X$, qui
s'écrit encore $X^{(q^s)^{r/s}}-X$, par conséquent (toujours
d'après \ref{factorisation-x-q-r-x}) sur $\FF_{q^s}$ le polynôme $f$
est produit de facteurs irréductibles distincts de degrés
divisant $r/s$.  Mais par ailleurs $f$ est premier avec $X^{q^t}-X$
pour tout diviseur strict $t$ de $r$ (\ref{critere-rabin}) : en
particulier avec les $X^{(q^s)^t}-X$ pour $t$ diviseur strict
de $r/s$ ; ceci montre que les facteurs irréductibles de $f$ sont de
degré exactement $r/s$, et par conséquent ils sont bien au nombre
de $s$.  Si $h$ est un quelconque de ces facteurs irréductibles, qu'on
choisira unitaire, alors $\Frob_q^i(h)$ est encore, pour chaque $i$
entre $0$ et $s-1$, un facteur irréductible de degré $r/s$ de $h$ (car
$\Frob_q$ est un automorphisme de $\FF_q$).  Reste à savoir que tous
ces facteurs sont distincts (donc premiers entre eux) : or si $h$
était laissé stable par un $\Frob_q^i$ avec $0<i<s$, il serait à
coefficients dans un $\FF_{q^{s'}}[t]$ avec $s'$ diviseur strict
de $s$, dans lequel il serait certainement irréductible, mais c'est
impossible car on vient de voir que les facteurs irréductibles de $f$
dans $\FF_{q^{s'}}[t]$ sont de degré $r/s' > r/s$.
\end{proof}
\begin{proof}[Seconde démonstration]
Soit $h$ un facteur irréductible de $f$ dans $\FF_{q^s}[X]$, et $x$
une racine de $h$ dans $\FF_{q^r}$ (qui existe puisque $f$, donc $h$,
est scindé sur $\FF_{q^r}$).  Le degré de $x$, c'est-à-dire de
$\FF_q(x) = \FF_{q^r}$, sur $\FF_q$ vaut $r$, et par conséquent
(\ref{inclusions-corps-finis} ou \refext{Alg}{multiplicativité degré})
son degré sur $\FF_{q^s}$ vaut $r/s$ : c'est donc le degré de $h$
(polynôme minimal de $x$ sur $\FF_{q^s}$).  On a vu
en \ref{racines-polynome-minimal-corps-fini} que les racines de $f$
(dans $\FF_{q^r}$) sont les $\Frob_q^i(x)$ pour $i$ allant de $0$
à $r-1$, et que celles de $h$ sont les $(\Frob_{q^s})^j(x)
= \Frob_q^{js}(x)$ pour $j$ allant de $0$ à $(r/s)-1$.  Pour $i$
allant de $0$ à $s-1$, le polynôme $\Frob_q^i(h) \in \FF_{q^s}[X]$
s'annule en $\Frob_q^i(x)$ et en tous les $\Frob_q^{i+js}(x)$ ; il est
irréductible puisque $\Frob_q^i$ est un automorphisme de
$\FF_{q^s}[X]$ (et que $h$ est irréductible), et tous ces polynômes
$\Frob_q^i(h)$ sont premiers entre eux puisque leurs racines dans
$\FF_{q^r}$, où ils se scindent, sont disjointes : par conséquent, $f$
est bien égal, à une constante près, au produit des $\Frob_q^i(h)$
(pour $i$ allant de $0$ à $s-1$).
\end{proof}

Voir \ref{descindage-polynomes-tours-corps-finis} pour une sorte de
réciproque de cette affirmation.

\begin{proposition2}\label{polynomes-restent-irreductibles-corps-finis}
Soit $h \in \FF_q[X]$ irréductible de degré $r$, et soit $s$ premier
avec $r$.  Alors $h$ vu dans $\FF_{q^s}[X]$ est encore irréductible.
\end{proposition2}
\begin{proof}[Première démonstration]
D'après le critère de Rabin (\ref{critere-rabin}), le polynôme $h$
divise $X^{q^r}-X$, et est premier avec $X^{q^t}-X$ pour tout $t$
diviseur strict de $r$ : on veut prouver la même chose en remplaçant
$q$ par $q^s$.  Le fait que $X^{q^r}-X$ divise $X^{(q^s)^r}-X$ (et
donc que $h$ divise ce dernier) résulte du
lemme \ref{lemme-divisibilite-x-q-r-x} ; par ailleurs, un diviseur de
$h$ et de $X^{q^{st}}-X$ devrait diviser à la fois $X^{q^r}-X$ et
$X^{q^{st}}-X$ donc leur pgcd, qui vaut $X^{q^t}-X$
d'après \ref{lemme-pgcd-x-q-r-x} (puisque le pgcd de $r$ et $st$
est $t$).
\end{proof}
\begin{proof}[Seconde démonstration]
Soit $h_1$ un facteur irréductible de $h$ dans $\FF_{q^s}[X]$, et $x$
une racine de $h_1$ dans $\FF_{q^{rs}}$ (qui existe puisque $h$ est
scindé sur $\FF_{q^r}$, donc dans $\FF_{q^{rs}}$, donc $h_1$ est
scindé dans $\FF_{q^{rs}}$).  Alors $(\Frob_{q^s})^i(x)
= \Frob_q^{is}(x)$ est racine de $h_1$ pour tout $i$.  Or, $s$ étant
premier avec $r$, l'entier $is$ prend toutes les valeurs possibles
modulo $r$, donc $\Frob_q^{is}(x)$ parcourt toutes les racines de $h$
(cf. \ref{racines-polynome-minimal-corps-fini}) : ceci montre que
toute racine de $h$ est racine de $h_1$ et finalement $h = h_1$ est
irréductible dans $\FF_{q^s}[X]$.
\end{proof}

\begin{corollaire2}\label{corollaire-scindage-partiel-polynomes-corps-finis}
Soit $f \in \FF_q[X]$ irréductible de degré $r$, et $s > 0$ un entier
naturel, et soit $d = \pgcd(r,s)$.  Alors $f$ vu dans $\FF_{q^s}[X]$
est produit de $d$ facteurs irréductibles chacun de degré $r/d$.  Si
$h$ est l'un de ces facteurs, alors tous sont donnés par les
$\Frob_q^i(h)$ (où par là on désigne le polynôme de même degré
que $h$, dont les coefficients sont image de ceux de $h$ par
$\Frob_q^i$, sans faire agir ce dernier sur l'indéterminée) pour $i$
allant de $0$ à $d-1$.
\end{corollaire2}
\begin{proof}
C'est une conséquence immédiate des
propositions \ref{scindage-partiel-polynomes-corps-finis} et \ref{polynomes-restent-irreductibles-corps-finis},
en appliquant la première pour décrire $f$ dans $\FF_{q^d}[X]$ et la
seconde pour voir que chacun des facteurs irréductibles reste
irréductible en passant de $\FF_{q^d}[X]$ à $\FF_{q^s}[X]$ (vu que
$s/d$ est premier avec $r$).
\end{proof}

La proposition suivante doit être vue comme un complément
à \ref{scindage-partiel-polynomes-corps-finis} :

\begin{proposition2}\label{descindage-polynomes-tours-corps-finis}
Soit $h \in \FF_{q^s}[X]$ unitaire irréductible de degré $t$.  Alors
le polynôme $f = \prod_{i=0}^{s-1}\Frob_q^i(h)$, de degré $st$,
appartient à $\FF_q[X]$, et il est irréductible si et seulement si le
ppcm des degrés sur $\FF_q$ des coefficients de $h$ est égal à $s$.
\end{proposition2}
\begin{proof}
Le fait que $f$ appartienne à $\FF_q[X]$ vient de ce que $\Frob_q(f) =
f$ (on rappelle que $\Frob_q$ opère uniquement sur les coefficients
des polynômes), comme il résulte aisément de $\Frob_q^s(h) = h$.

Dire que le ppcm des degrés sur $\FF_q$ des coefficients de $h$ est
égal à $s$ signifie (cf. \ref{racines-polynome-minimal-corps-fini})
que $\Frob_q$ a pour période exactement $s$ en agissant sur $h$,
c'est-à-dire que tous les $\Frob_q^i(h)$ (pour $i$ allant de $0$
à $s-1$) sont distincts et donc, étant unitaires et irréductibles
sur $\FF_{q^s}$, premiers entre eux.  Si c'est le cas, alors $f$ est
irréductible sur $\FF_q$, car aucun sous-ensemble non trivial de ses
facteurs irréductibles $\Frob_q^i(h)$ sur $\FF_{q^s}$ n'est stable
par $\FF_q$ donc ne définit de polynôme de $\FF_q[X]$.
Réciproquement, si $f$ est irréductible dans $\FF_q[X]$, il a $st$
racines distinctes dans $\FF_{q^{st}}$, donc tous les $\Frob_q^i(h)$
sont distincts.
\end{proof}

On étudiera en \refext{ACF}{remarque-tours-corps-finis} la question du rapport
entre les présentations de $\FF_{q^{st}}$, dans les conditions de la
proposition précédente, données par $\FF_q[X]/(f)$ et par
$\FF_{q^s}[X]/(h)$.

\section{Éléments primitifs et groupe multiplicatif}

\subsection{Éléments primitifs}

\begin{théorème2}\label{cyclicite-groupe-multiplicatif-corps}
Tout sous-groupe fini du groupe multiplicatif d'un corps est cyclique.
En particulier, le groupe multiplicatif d'un corps fini est cyclique.
\end{théorème2}

\begin{exercice2}
En déduire une seconde démonstration de \ref{existence-polynome-irreductible-tout-degre-corps-finis}.
\XXX
\end{exercice2}

\begin{démo}
Soient $K$ un corps et $G⊆K^×$ un sous-groupe fini.  Pour tout entier
$n$, l'ensemble $G[n]$ des éléments de $G$ d'ordre divisant $n$ est de
cardinal au plus $n$ car il est inclus dans l'ensemble des racines
dans $K$ du polynôme $X^n-1$.  La conclusion résulte donc du lemme
suivant.
\end{démo}

\begin{lemme2}\label{lemme-detection-groupes-cycliques}
Soit $G$ un groupe fini non nécessairement abélien d'ordre $n$ tel que
pour tout $d$ divisant $n$ on ait
\[\# G[d]≤d\]
en notant $G[d]$ l'ensemble des éléments d'ordre divisant $d$.
Alors $G$ est cyclique.
\end{lemme2}

\begin{démo}
Pour tout $d$ divisant $n$, notons $X_d$ l'ensemble des éléments
d'ordre exactement $d$.  On souhaite montrer que $X_n$ est non vide.
Commençons par montrer que si un $X_d$ est non vide, il est d'ordre
$φ(d)$.  En effet, si $x∈X_d$, l'ensemble à $d$ éléments
$\{1,x,\dots,x^{d-1}\}$ est inclus dans — donc égal à — $G[d]$.  Pour
un tel $d$, $G[d]$ est cyclique d'ordre $d$ et $X_d$ est l'ensemble de
ses générateurs, donc de cardinal $φ(d)$.  Il résulte de la formule
$∑_{d|n} φ(d)=n$ et de l'égalité $G=∐_{d|n} X_d$ (le symbole $\coprod$
désignant la réunion disjointe) que chaque $X_d$ est non vide. En
particulier c'est le cas de $X_n$.
\end{démo}

\begin{definition2}\label{element-primitif-corps-fini}
Un élément $x \in \FF_q^\times$ qui engendre le groupe multiplicatif
$\FF_q^\times$ est dit \emph{primitif}.
\end{definition2}

Le théorème \ref{cyclicite-groupe-multiplicatif-corps} affirme donc
qu'il existe dans (le groupe multiplicatif de) tout corps fini $\FF_q$
des éléments primitifs, et leur nombre est alors $\varphi(q-1)$
(nombre de générateurs d'un groupe cyclique d'ordre $q-1$), où
$\varphi$ désigne la fonction indicatrice d'Euler.  Plus généralement,
le nombre d'éléments d'ordre exactement $d$ dans $\FF_q^\times$ est
$\varphi(d)$ si $d|(q-1)$ et $0$ sinon (comparer avec la démonstration
du lemme \ref{lemme-detection-groupes-cycliques}).

\begin{remarques2}\label{elements-et-polynomes-primitifs}
Si $x \in \FF_{q^r}^\times$ est primitif, alors tout élément conjugué
à $x$ sur $\FF_q$ (cf. \ref{elements-conjugues-corps-finis} et les
remarques qui suivent) est encore primitif (en effet, l'ordre
multiplicatif d'un élément est préservé par l'automorphisme de
corps $\Frob_q \colon z \mapsto z^q$).  Par ailleurs, le degré de $x$
sur $\FF_q$ est alors exactement $r$ (et non un diviseur strict $s$
de $r$) : en effet, si on avait $x \in \FF_{q^s}$ avec $s<r$ alors
toutes les puissances de $x$ appartiendraient à $\FF_{q^s}$,
contredisant l'hypothèse que $x$ soit primitif.

Il est donc raisonnable d'appeler aussi primitif le polynôme minimal
commun sur $\FF_q$ de $x$ et de ses conjugués.  Autrement dit, un
polynôme primitif sur $\FF_q$ est un polynôme irréductible de
degré $r$ sur $\FF_q$ dont les racines dans $\FF_{q^r}$ sont
primitives.

Puisqu'il existe $\varphi(q^r-1)$ éléments primitifs dans $\FF_{q^r}$
et que la classe de conjugaison de chacun comporte exactement $r$
éléments et définit un unique polynôme primitif unitaire, on en déduit
qu'il existe $\frac{1}{r}\varphi(q^r-1)$ polynômes primitifs unitaires
de degré $r$ sur $\FF_q$.  Ce résultat, à comparer
avec \ref{denombrement-polynomes-irreductibles-corps-finis}, fournit
une nouvelle démonstration du fait qu'il existe des polynômes
irréductibles de degré arbitraire sur un corps fini (et qu'il existe
dans $\FF_{q^r}$ des éléments de degré $r$ sur $\FF_q$).

Signalons la conjecture d'Artin : si $ℓ$ est un nombre premier,
il existe une infinité de nombres premiers $p$ tels
que $ℓ$ soit primitif modulo $p$, c'est-à-dire tel que l'image 
de $ℓ$ dans $𝐅_p$ soit un élément primitif. \XXX
%cf. p. ex. http://www.mast.queensu.ca/~murty/mi.dvi
\end{remarques2}

\begin{proposition2}\label{2-primitif-mod-p}
Si $p$ un nombre premier de la forme
$4ℓ+1$ où $ℓ$ est un nombre premier, alors $2$ est primitif modulo
$p$.
\end{proposition2}

Cette proposition s'applique par exemple à $p=13,29$ ou $53$.

\begin{démo}
Un nombre $a$ est primitif modulo $p$ si pour tout
premier $p'$ tel que $p$ soit congru à $1$ modulo $p'$, 
$a^{(p-1)/p'}$ n'est pas congru à $1$ modulo $p$. 
Sous l'hypothèse de la proposition, $p-1$ a deux diviseurs
premiers : $2$ et $ℓ$. Puisque $ℓ$ est impair,
$4ℓ+1$ congru à $5$ modulo $8$, de sorte que
(\refext{ACF}{formule-complementaire}) $2^{(p-1)/2}$ est congru à $-1$
modulo $p$. Enfin, $2^{(p-1)/ℓ}=2^4≡1$ modulo $p$ entraîne $p=3$ ou $5$.
\end{démo}

\begin{remarque2}
On ne sait pas s'il existe une infinité de nombres premiers
de la forme $(p-1)/4$. Par contre, la méthode dite du « crible »
permet de montrer qu'il existe une infinité de premiers $p$
tels que $(p-1)/4$ soit un produit de deux nombres premiers
plus grands que $p^θ$ où $θ$ est une constante strictement supérieure
à $⅓$. On peut en déduire (Heath-Brown) que l'un des trois entiers $2$, $3$ et $5$
est primitif pour une infinité de nombres premiers.
\end{remarque2}

\begin{exemples2}\label{primitifs-sur-f16}
\begin{itemize}
\item Le polynôme irréductible $h = X^4+X+1 \in \FF_2[X]$ est primitif
(sur $\FF_2$), c'est-à-dire qu'une quelconque de ses racines engendre
$\FF_{16}^\times$.  Pour se convaincre à la fois du fait qu'il est
irréductible et qu'il est primitif, on peut par exemple calculer les
puissances successives de la classe $x$ de $X$ modulo $h$, soit
$x^0=1$, $x^1=x$, $x^2$, $x^3$, $x^4=x+1$, $x^5=x^2+x$, $x^6=x^3+x^2$,
$x^7=x^3+x+1$, $x^8=x^2+1$, $x^9=x^3+x$, $x^{10}=x^2+x+1$,
$x^{11}=x^3+x^2+x$, $x^{12}=x^3+x^2+x+1$, $x^{13}=x^3+x^2+1$,
$x^{14}=x^3+1$ et $x^{15}=1$ : le fait qu'on ait obtenu un groupe
cyclique à $15$ éléments, c'est-à-dire tous les éléments non nuls de
$\FF_2[X]/(h)$, montre d'une part que l'ensemble des éléments non nuls
de $\FF_2[X]/(h)$ est un groupe (donc que $\FF_2[X]/(h)$ est un corps,
c'est-à-dire que $h$ est irréductible) et d'autre part que $x$ y est
primitif, c'est-à-dire que $h$ est primitif.
\item Le polynôme irréductible $h = X^4+X^3+X^2+X+1 \in \FF_2[X]$,
bien qu'irréductible, n'est pas primitif.  En effet, on a $X^5 \equiv
X \pmod{h}$, c'est-à-dire que la classe $x$ de $X$ dans $\FF_2[X]/(h)$
est d'ordre $5$, et cette classe n'engendre donc pas
$\FF_{16}^\times$.
\end{itemize}
\end{exemples2}

Ces exemples ont notamment pour but de souligner le fait que tous les
polynômes irréductibles ne sont pas nécessairement primitifs ou que,
de façon équivalente, le fait qu'un élément $x \in \FF_{q^r}$ soit de
degré $r$ sur $\FF_q$ ne suffit pas à entraîner qu'il soit primitif.
(De fait, c'était déjà clair sur les dénombrements qu'on a obtenus :
dans $\FF_{16}$ il y a $16-4 = 12$ éléments de degré $4$ sur $\FF_2$,
dont seulement $\varphi(15) = 8$ sont primitifs, c'est-à-dire qu'il y
a parmi les polynômes unitaires de degré $4$ sur $\FF_2$ un total de
$\frac{12}{4} = 3$ polynômes irréductibles dont $\frac{8}{4} = 2$ sont
primitifs.)

\begin{lemme2}\label{somme-x-s-dans-f-q}
Si $s$ est un entier naturel, alors $\sum_{x\in\FF_q} x^s$ vaut $-1$
si $s$ est non-nul \emph{et} multiple de $q-1$, et $0$ sinon (on fait
la convention $0^0 = 1$).
\end{lemme2}
\begin{proof}
Si $s=0$, la somme $\sum_{x\in\FF_q} x^s = \sum_{x\in\FF_q} 1$
vaut $q$, c'est-à-dire $0$ dans $\FF_q$.  Supposons maintenant $s>0$ :
alors $\sum_{x\in\FF_q} x^s = \sum_{x\in\FF_q^\times} x^s$, et en
appelant $g$ un élément primitif de $\FF_q$, cette somme s'écrit
encore $\sum_{i=0}^{q-2} g^{si}$.  Si $g^s = 1$, ce qui se produit
exactement lorsque $s$ est multiple de $q-1$, la somme vaut $q-1$,
c'est-à-dire $-1$ dans $\FF_q$.  Sinon, on a $\sum_{i=0}^{q-2} g^{si}
= \frac{g^{s(q-1)}-1}{g^s-1} = 0$.
\end{proof}

\subsection{Polynômes cyclotomiques et corps finis}

\subsubsection{} On rappelle que les polynômes cyclotomiques
$\Phi_n \in \ZZ[X]$ sont les uniques polynômes unitaires à
coefficients rationnels (et en fait, entiers) vérifiant pour tout $n$
la relation $X^n-1 = \prod_{d|n} \Phi_d(X)$ (le produit étant pris sur
tous les $d$ divisant $n$).  On peut aussi écrire $\Phi_n(X)
= \prod_\zeta (X-\zeta)$ pour $\zeta$ parcourant l'ensemble des
racines primitives $n$-ièmes de l'unité dans une extension quelconque
de $\QQ$ les contenant.  Les $\Phi_n$ sont irréductibles dans $\ZZ[X]$
(et deux à deux distincts, donc deux à deux premiers entre eux), et le
degré de $\Phi_n$ est $\varphi(n)$.  La formule $\Phi_n(X)
= \prod_\zeta (X-\zeta)$ pour $\zeta$ parcourant l'ensemble des
racines primitives $n$-ièmes de l'unité est encore valable dans
n'importe quel corps, de caractéristique ne divisant pas $n$, où il
existe une --- et donc $\varphi(n)$ --- racine primitive $n$-ième de
l'unité.

Si $q$ et $n$ sont premiers entre eux où $q$ est une puissance d'un
nombre premier $p$, considérons un $r$ tel que $n|(q^r-1)$
(c'est-à-dire $q^r \equiv 1 \pmod{n}$ ; un tel $r$ existe évidemment :
par exemple l'ordre multiplicatif de $q$ modulo $n$ convient) ; dans
ces conditions, si $\xi$ est un élément primitif de $\FF_{q^r}$, il
est facile de voir que $\zeta = \xi^{(q^r-1)/n}$ est d'ordre
multiplicatif exactement $n$ dans $\FF_{q^r}$, c'est-à-dire, est une
racine primitive $n$-ième de l'unité.  Dans ces conditions (lorsque
$n|(q^r-1)$), on a encore $\Phi_n(X) = \prod_\zeta (X-\zeta)$ dans
$\FF_{q^r}$, où $\zeta$ parcourt les racines primitives $n$-ièmes de
l'unité dans $\FF_{q^r}$, c'est-à-dire les $\varphi(n)$ éléments
d'ordre exactement $n$ dans $\FF_{q^r}^\times$.  En particulier, les
$\Phi_n$ pour $n$ premier avec $q$ sont encore deux à deux premiers
entre eux dans $\FF_q[X]$.

On a, de façon analogue à \ref{factorisation-x-q-r-x} :
\begin{proposition2}\label{factorisation-phi-q-r-1}
La décomposition en facteurs irréductibles du polynôme
$\Phi_{q^r-1}(X)$ dans $\FF_q[X]$ est donnée comme le produit de tous
les polynômes unitaires primitifs de $\FF_q[X]$ de degré $r$ (au
nombre de $\frac{1}{r}\varphi(q^r-1)$,
cf. \ref{elements-et-polynomes-primitifs}), chacun apparaissant avec
multiplicité $1$.
\end{proposition2}
\begin{proof}
D'après ce qui a été dit, $\Phi_{q^r-1}$ est scindé sur $\FF_{q^r}$ et
ses racines sont exactement les éléments primitifs de $\FF_{q^r}$
(chacune avec multiplicité $1$) ; et sur $\FF_q$ on a vu que les
polynômes minimaux de ces éléments primitifs de $\FF_{q^r}$ sont les
polynômes unitaires primitifs de degré $r$ sur $\FF_q$.
\end{proof}

\begin{exemple2}
Dans $\FF_2$, le polynôme $\Phi_{15}(X) = X^8 - X^7 + X^5 - X^4 + X^3
- X + 1 \in \ZZ[X]$ se factorise comme $(X^4 + X + 1)\penalty-100 (X^4
+ X^3 + 1)$ : ces deux facteurs sont les $\frac{1}{4} \varphi(15) = 2$
polynômes primitifs de degré $4$ sur $\FF_2$.  (Comparer
avec \ref{primitifs-sur-f16}.)
\end{exemple2}

Plus généralement :
\begin{proposition2}\label{factorisation-phi-n}
Soit $n$ un entier naturel premier avec $q$ (où $q$ est une puissance
d'un nombre premier).  Alors la décomposition en facteurs
irréductibles du polynôme $\Phi_n(X)$ dans $\FF_q[X]$ est formée de
$\frac{1}{r}\varphi(n)$ facteurs irréductibles chacun de degré $r$, où
$r$ est l'ordre multiplicatif de $q$ modulo $n$ (c'est-à-dire le plus
petit entier naturel tel que $q^r \equiv 1 \pmod{n}$).

En particulier, (toujours sous l'hypothèse que $n$ et $q$ sont
premiers entre eux, cf. \ref{irreductibilite-phi-n-complement})
$\Phi_n(X)$ est irréductible dans $\FF_q[X]$ exactement lorsque $q$
engendre le groupe multiplicatif $(\ZZ/n\ZZ)^\times$.
\end{proposition2}
\begin{proof}
Soit $r$ l'ordre multiplicatif de $q$ modulo $n$.  Il existe alors
dans $\FF_{q^r}$ une racine primitive $n$-ième de l'unité $\zeta$ :
ansi, $\Phi_n$ est scindé sur $\FF_{q^r}$ et on peut écrire $\Phi_n(X)
= \prod (X-\zeta^j)$ pour $j$ parcourant (les $\varphi(n)$ éléments
de) $(\ZZ/n\ZZ)^\times$.  Le degré de $\zeta^j$ sur $\FF_q$ (pour
$j \in (\ZZ/n\ZZ)^\times)$) est le plus petit $i$ tel que
$\zeta^{j\,q^i} = \zeta^j$, c'est-à-dire tel que $j q^i \equiv
j \pmod{n}$, ce qui équivaut à $q^i \equiv 1 \pmod{n}$ (puisque $j$
est inversible modulo $n$), c'est donc exactement $r$.  Ainsi,
$\Phi_n$ est scindé sur $\FF_{q^r}$, et les polynômes minimaux sur
$\FF_q$ de ses racines sur $\FF_{q^r}$ sont chacun de degré $r$ : ceci
prouve que $\Phi_n$ s'écrit sur $\FF_q$ comme produit de
$\frac{1}{r}\varphi(n)$ polynômes irréductibles de degré $r$.

La dernière affirmation signifie simplement que $q$ engendre le groupe
multiplicatif $(\ZZ/n\ZZ)^\times$ exactement lorsque son ordre
multiplicatif modulo $n$ est $\varphi(n)$.
\end{proof}

On peut dire (cf. les remarques
suivant \ref{racines-polynome-minimal-corps-fini}) que le corps de
décomposition de $\Phi_n$ sur $\FF_q$ (toujours sous l'hypothèse que
$n$ n'est pas multiple de $p$) est $\FF_{q^r}$ où $r$ est l'ordre
multiplicatif de $q$ modulo $n$.  Ce corps de décomposition, qui est
le corps de rupture d'un quelconque des facteurs irréductibles (tous
de degré $r$) de $\Phi_n$ sur $\FF_q$, peut se noter $\FF_q(\zeta_n)$,
en désignant par $\zeta_n$ une racine primitive $n$-ième de l'unité
dans $\FF_{q^r}$.  Il faut cependant se garder de croire que les
différents choix possibles de $\zeta_n$ soient interchangeables (plus
précisément, qu'ils seraient conjugués sous l'action de $\Frob_q$) :
même si le corps $\FF_q(\zeta_n) = \FF_{q^r}$ engendré par $\zeta_n$
est le même quel que soit le choix effectué, le polynôme minimal de
$\zeta_n$ sur $\FF_q$, lui, ne l'est pas (c'est justement l'un
quelconque des $\frac{1}{r} \varphi(n)$ facteurs irréductibles
de $\Phi_n$) ; ceci diffère de la situation sur $\QQ$ où toutes les
racines primitives $n$-ièmes de l'unité sont interchangeables
(précisément, on dira qu'elles sont conjuguées par le groupe de
Galois), non seulement elles engendrent le même corps $\QQ(\zeta_n)$
mais aussi elles ont le même polynôme minimal sur $\QQ$, qui est
justement $\Phi_n$.

\begin{corollaire2}
Le polynôme $Φ_ℓ$ a une racine dans $𝐅_p$ si et seulement si
$p ≡ 1 \mod ℓ$.
\end{corollaire2}

\begin{proposition2}
Soit $P ∈ 𝐙[X]$ un polynôme non constant. Il existe une infinité
de nombres premiers $p$ tels que $P$ ait une racine dans $𝐅_p$.
\end{proposition2}

% Variante (plus dure) : scindé
% Čebotarev pour l'absence de racine si P irréductible.

\begin{démo}
C'est une variante de la méthode d'Euclide pour montrer
qu'il existe une infinité de nombres premiers. Supposons
que les $P(n)$, $n ∈ 𝐍$ n'aient qu'un nombre fini de
diviseurs premiers $ℓ₁,ℓ₂,…,ℓ_r$. Pour chaque $n ∈ 𝐍$,
l'entier $P(n ℓ₁ℓ₂\ cdots ℓ_r)$ est congru à $P(0)=±1$
modulo chaque $ℓ_i$. En particulier, il est premier à
chacun d'entre eux. Or, si $n$ est grand, $P(n ℓ₁ℓ₂\ cdots ℓ_r)$
est grand (en valeur absolue) donc a un diviseur premier.
Absurde. Dans le cas général, on observe que si $a=P(0)$,
on a $P(aX)=aQ(X)$ où $Q(0)=1$. Si $Q$ a une racine
modulo $p$, il en est de même de $P$.
\end{démo}

\begin{corollaire2}
\label{Dirichlet faible}
Soit $ℓ$ un nombre premier. Il existe une infinité
de nombres premiers $p$ congrus à un modulo $ℓ$.
\end{corollaire2}

\begin{proposition2}
Soit $h$ un polynome irréductible unitaire sur $\FF_q$, autre que $X$.
Alors il existe un unique $n$ premier à $q$ tel que $h$
divise $\Phi_n$ : ce $n$ divise $q^r-1$ où $r$ est le degré de $h$.
Il s'agit exactement de l'ordre multiplicatif d'une racine
(quelconque) de $h$ dans $\FF_{q^r}$.
\end{proposition2}
\begin{proof}
On a $X^{q^r-1}-1 = \prod_{n|(q^r-1)} \Phi_n(X)$ par définition
des $\Phi_n$, donc $X^{q^r}-X = X\,\prod_{n|(q^r-1)} \Phi_n(X)$.
D'après \ref{factorisation-x-q-r-x}, le polynôme irréductible $h$
divise ce produit : il doit donc diviser un des $\Phi_n$ avec
$n|(q^r-1)$.  Comme les $\Phi_n$ pour $n$ premier à $q$ sont premiers
entre eux, il ne peut en diviser un autre.  Enfin, dire qu'une racine
de $h$ (dans $\FF_{q^r}$) est racine de $\Phi_n$ signifie précisément
que son ordre multiplicatif est exactement $n$.
\end{proof}

\begin{exemples2}
\begin{itemize}
\item Le polynôme $\Phi_5(X) = X^4+X^3+X^2+X+1 \in \ZZ[X]$ demeure
irréductible dans $\FF_2$ car $2$ engendre $(\ZZ/5\ZZ)^\times$.  Il
n'est, naturellement, pas primitif (puisque ses racines dans
$\FF_{2^4}$ sont d'ordre $5$ et non $15$).  On retrouve-là un exemple
déjà donné en \ref{primitifs-sur-f16}.
\item Le polynôme $\Phi_{9}(X) = X^6 + X^3 + 1 \in \ZZ[X]$
demeure irréductible dans $\FF_2$ car $2$
engendre $(\ZZ/9\ZZ)^\times$.  Il n'est, naturellement, pas primitif
(puisque ses racines dans $\FF_{2^6}$ sont d'ordre $9$ et non $63$).
\item Le polynôme $\Phi_{17}(X) = X^{16} + X^{15} + \cdots + X + 1 \in
\ZZ[X]$ se factorise dans $\FF_2$ comme produit de deux facteurs de
degré $8$ puisque $2$ est d'ordre $8$ dans $(\ZZ/17\ZZ)^\times$ (on a
$2^8 \equiv 1 \pmod{17}$).  À savoir : $\Phi_{17}(X) =
(X^8+X^5+X^4+X^3+1)\penalty-100 (X^8+X^7+X^6+X^4+X^2+X+1)$.  Aucun de
ces facteurs, naturellement, n'est primitif (puisque leurs racines
sont toutes d'ordre $17$ et non $2^8-1 = 255$).
\end{itemize}
\end{exemples2}

\subsubsection{} Lorsque $n$ n'est plus supposé premier avec $p$
(i.e., avec $q$), les choses sont très différentes, et le polynôme
$\Phi_n$ n'est généralement plus séparable sur $\FF_q$ comme on va le
voir.  Par exemple, il est facile de se convaincre par récurrence
sur $k$ que $\Phi_{p^k}(X) = (X-1)^{(p-1)p^{k-1}}$ sur $\FF_p$ (ou
sur $\FF_q$, donc).

\begin{proposition2}\label{factorisation-phi-n-inseparable}
Si $n = p^k m$ où $m$ n'est pas multiple de $p$, alors $\Phi_n(X)
= \Phi_m(X)^{(p-1)p^{k-1}}$ dans $\FF_p[X]$ (donc dans $\FF_q[X]$).
En particulier, sauf éventuellement dans le cas où $p=2$ et $k=1$, le
polynôme $\Phi_n(X)$ n'est ni séparable ni irréductible
sur $\FF_q[X]$.
\end{proposition2}
\begin{proof}
On procède par récurrence sur $k$ et, à $k$ fixé, par récurrence
sur $m$.  On a d'une part $X^{p^k m} - 1 = (X^m-1)^{p^k}
= \prod_{d|m}\Phi_d(X)^{p^k}$ et d'autre part $X^{p^k m} - 1
= \prod_{d|p^k m} \Phi_d(X) = \prod_{d|m}
(\Phi_d(X)\, \prod_{\ell=1}^k \Phi_{p^\ell d}(X))$.  Les hypothèses
des récurrences permettent de remplacer chaque $\Phi_{p^\ell d}(X)$
par $\Phi_d(X)^{(p-1)p^{\ell-1}}$ sauf le dernier
($\ell=k$ et $d=m$) : pour montrer qu'on a bien aussi $\Phi_{p^k m}(X)
= \Phi_m(X)^{(p-1)p^{k-1}}$, il suffit donc de montrer que
$\prod_{d|m}\Phi_d(X)^{p^k} = \prod_{d|m}
(\Phi_d(X)\, \prod_{\ell=1}^k \Phi_d(X)^{(p-1)p^{\ell-1}})$.  Or cela
résulte du fait que $1 + \sum_{\ell=1}^k (p-1)p^{\ell-1} = p^k$.
\end{proof}

\begin{proposition2}\label{irreductibilite-phi-n-complement}
Si $q$ est une puissance d'un nombre premier $p$ et $n$ est un entier
naturel, le polynôme cyclotomique $\Phi_n$ est irréductible
dans $\FF_q$ si et seulement si :
\begin{itemize}
\item le nombre $q$ engendre le groupe multiplicatif
$(\ZZ/n\ZZ)^\times$ (ce qui sous-entend que $q$ est premier
avec $n$), \emph{ou bien}
\item on a $n=2m$ avec $m$ impair, et $p=2$, et $q$ engendre le groupe
multiplicatif $(\ZZ/m\ZZ)^\times$.
\end{itemize}
\end{proposition2}
\begin{proof}
D'après \ref{factorisation-phi-n-inseparable}, on sait que si $n$ est
multiple de $p$ avec $p>2$, ou que $n$ est multiple de $4$ lorsque
$p=2$, alors $\Phi_n$ n'est pas irréductible modulo $p$ (donc
dans $\FF_q$).  Lorsque $n$ est premier avec $q$, la
proposition \ref{factorisation-phi-n} donne le premier cas.  Reste
enfin le cas où $n = 2m$ avec $m$ impair et $p=2$ : dans ce cas
$\Phi_n(X) = \Phi_m(X)$ modulo $2$, donc la
proposition \ref{factorisation-phi-n} donne de nouveau le résultat.
\end{proof}

\begin{exemples2}
\begin{itemize}
\item Modulo $2$, les polynômes $\Phi_{2m}(X)$ et $\Phi_m(X)$
(pour $m$ impair) sont toujours égaux.  (En fait, dans $\ZZ[X]$, on a
$\Phi_{2m}(X) = \Phi_m(-X)$ pour $m$ impair, puisque les racines
primitives $2m$-ièmes de l'unité sont les $-\zeta$ avec $\zeta$ racine
primitive $m$-ième de l'unité.)  Ensuite, toujours modulo $2$ et avec
$m$ impair, on a $\Phi_{4m}(X) = \Phi_m(X)^2$.
\item Le polynôme $\Phi_8(X) = X^4 + 1$, bien qu'irréductible dans
$\ZZ[X]$ ou $\QQ[X]$, n'est irréductible dans \emph{aucun}
$\FF_q[X]$ : en effet, en caractéristique $p=2$, on a $\Phi_8 =
(X-1)^4$, et en caractéristique $p\neq 2$, on a vu
en \ref{factorisation-phi-n} que pour que $\Phi_8$ soit irréductible
dans $\FF_q$ il faut (et il suffit) que $q$ engendre
$(\ZZ/8\ZZ)^\times$, or ce dernier n'est pas cyclique (il a quatre
éléments tous d'ordre divisant $2$) : donc $\Phi_8$ se scinde (en
quatre facteurs de degré $1$) pour $q \equiv 1 \pmod{8}$, et se
factorise en deux facteurs de degré $2$ pour tout autre $q$
impair. (\XXX Peut-on être un chouïa plus explicite sur la
factorisation de $\Phi_8$ modulo $p$ ?)
\item Si $n$ est multiple de deux nombres premiers impairs distincts
$\ell_1,\ell_2$, alors, de même, $\Phi_n$, bien qu'irréductible dans
$\ZZ[X]$ ou $\QQ[X]$, n'est irréductible dans aucun $\FF_q$ : en
effet, en caractéristique $\ell_1$ ou $\ell_2$, le polynôme $\Phi_n$
n'est pas irréductible (il est une puissance parfaite) ; et en toute
autre caractéristique, on sait que pour que $\Phi_n$ soit irréductible
dans $\FF_q$ il faut (et il suffit) que $q$ engendre
$(\ZZ/n\ZZ)^\times$, or ce dernier n'est pas cyclique car le théorème
chinois assure qu'on peut l'écrire comme produit de deux groupes
d'ordres pairs (par exemple $(\ZZ/n\ZZ)^\times \cong
(\ZZ/n_1\ZZ)^\times \times (\ZZ/n_2\ZZ)^\times$ où $n_1 = \ell_1^k$ et
$n_2$ est premier avec $\ell_1$).
\end{itemize}
\end{exemples2}

\subsubsection{Éléments primitifs modulo $n$} On dit qu'un élément
$g \in \ZZ/n\ZZ$ est \emph{primitif} modulo $n$ lorsque
$g$ est premier avec $n$ (c'est-à-dire $g \in
(\ZZ/n\ZZ)^\times$) et que $g$ engendre le groupe
multiplicatif $(\ZZ/n\ZZ)^\times$.  (Lorsque $n$ est
premier, cette terminologie est cohérente avec celle introduite
en \ref{element-primitif-corps-fini}.)  Autrement dit, dire qu'il
existe des éléments primitifs modulo $n$ signifie que
$(\ZZ/n\ZZ)^\times$ est cyclique, et lorsqu'il en
existe, il en existe exactement $\varphi(\varphi(n))$.

On rappelle ou admet le résultat suivant :
\begin{proposition2}
\begin{itemize}
\item Si $p$ est un nombre premier impair, alors
  $(\ZZ/p\ZZ)^\times$ est cyclique, i.e., il existe des éléments
  primitifs modulo $p$.  (Il en existe exactement $\varphi(p-1)$.)
\item Si $p$ est un nombre premier impair et $k\geq 2$, alors
  $(\ZZ/p^k\ZZ)^\times$ est cyclique, i.e., il existe des éléments
  primitifs modulo $p^k$.  (Il en existe exactement
  $\varphi(p^{k-1}(p-1))$.)  Plus précisément : $g$ est primitif
  modulo $p^k$ si et seulement si il l'est modulo $p^2$.
\item Si $p=2$ et $1\leq k\leq 2$, alors
  $(\ZZ/2^k\ZZ)^\times$ est (trivialement) cyclique.
\item Si $p=2$ et $k \geq 3$, alors
  $(\ZZ/2^k\ZZ)^\times$ \emph{n'est pas} cyclique : il est produit
  d'un groupe cyclique d'ordre $2$ engendré par $-1$ et d'un groupe
  cyclique d'ordre $2^{k-2}$ engendré par $5$ (l'ordre maximal
  possible d'un élément est $2^{k-2}$).
\item Si $n$ n'est pas de la forme $2$, $4$, $p^k$ ou $2 p^k$
  avec $p$ premier impair, alors $(\ZZ/n\ZZ)^\times$ \emph{n'est pas}
  cyclique : il peut s'écrire comme produit de deux groupes d'ordre
  pair.
\end{itemize}
\end{proposition2}

Par ailleurs, on admet provisoirement le théorème suivant, qui sera
démontré en \XXX :
\begin{theoreme2}[Dirichlet]
Si $b \in (\ZZ/n\ZZ)^\times$, alors il existe un nombre premier $p$
tel que $p \equiv b \pmod{n}$.
\end{theoreme2}

On peut alors remarquer :
\begin{proposition2}
Pour tout entier naturel $n$, il existe un nombre premier $p$ (ou, de
façon équivalente, une puissance $q$ d'un nombre premier) tel que
$\Phi_n$ soit irréductible dans $\FF_p$ (resp., dans $\FF_q$) si, et
seulement si, $n$ vaut $2$, $4$, $\ell^k$ ou $2\ell^k$ pour $\ell$
premier impair.
\end{proposition2}
\begin{proof}
Démontrons le « si » : si $n$ est d'une des formes indiquées, alors
$(\ZZ/n\ZZ)^\times$ est cyclique, donc il existe un élément $g \in
(\ZZ/n\ZZ)^\times$ qui soit primitif, et d'après le théorème de
Dirichlet, on peut supposer que $g \equiv p \pmod{n}$ avec $p$
premier, et d'après \ref{factorisation-phi-n} le polynôme $\Phi_n$ est
irréductible modulo $p$.

Montrons maintenant le « seulement si » : si $\Phi_n$ est irréductible
dans $\FF_q$, on sait d'après \ref{irreductibilite-phi-n-complement}
que soit $q$ est premier avec $n$ et primitif modulo $n$ soit $n=2m$
avec $m$ impair et $q = 2^r$ est primitif modulo $m$.  Dans le premier
cas, $n$ vaut $2$, $4$, $\ell^k$ ou $2\ell^k$ avec $\ell$ premier
impair, et dans le second, $m$ vaut $\ell^k$ avec $\ell$ premier
impair, donc $n=2m$ est bien de la forme $2\ell^k$ avec $\ell$ premier
impair.
\end{proof}

\subsection{Trace et norme}

On renvoie à \refext{Alg}{trace-et-norme} pour les généralités sur la
trace et la norme dans une algèbre quelconque sur un corps.  On se
préoccupera ici d'une extension $\FF_{q^r}\bo \FF_q$ de corps finis :
la \emph{trace} $\Tr_{\FF{q^r}\bo\FF_q}(x)$,
la \emph{norme} $\N_{\FF{q^r}\bo\FF_q}(x)$, et le \emph{polynôme
caractéristique} $\chi_{\FF{q^r}\bo\FF_q}(x,X)$ d'un élément
$x \in \FF_{q^r}$ sont respectivement la trace, la norme, et le
polynôme caractéristique de l'application $\FF_q$-linéaire $z \mapsto
xz$ de multiplication par $x$ sur $\FF_{q^r}$, ce dernier étant vu
comme un $\FF_q$-espace vectoriel de dimension $r$.

\begin{proposition2}\label{trace-et-norme-corps-finis}
Soit $x \in \FF_{q^r}$ : alors on a
\[\chi_{\FF{q^r}\bo\FF_q}(x,X) = \prod_{i=0}^{r-1} (X-\Frob_q^i(x))\]
et en particulier
\[\Tr_{\FF{q^r}\bo\FF_q}(x) = \sum_{i=0}^{r-1} \Frob_q^i(x)\]
\[\N_{\FF{q^r}\bo\FF_q}(x) = \prod_{i=0}^{r-1} \Frob_q^i(x) = x^{(q^r-1)/(q-1)}\]
\end{proposition2}
\begin{proof}
Considérons d'abord le cas où $x$ engendre $\FF_{q^r}$ sur $\FF_q$,
c'est-à-dire que son degré est $r$.  Alors on a vu
en \ref{elements-conjugues-corps-finis} que les conjugués de $x$ sont
justement les $\Frob_q^i(x)$ pour $i\in\{0,\ldots,r-1\}$, le polynôme
$\prod_{i=0}^{r-1} (X-\Frob_q^i(x))$ étant alors le polynôme minimal
de $x$.  Puisqu'il est de degré $r$, c'est aussi son polynôme
caractéristique, ce qui montre la première formule dans le cas
particulier considéré.

Dans le cas où $x$ est de degré $s<r$, on décompose l'extension
$\FF_{q^r}\bo\FF_q$ en deux extensions $\FF_q(x)\bo\FF_q$
(c'est-à-dire $\FF_{q^s}\bo\FF_q$) et $\FF_{q^r}\bo\FF_q(x)$, de
degrés respectifs $s$ et $r/s$.  On a
$\chi_{\FF_{q^r}\bo\FF_q(x)}(x,X) = (X-x)^{r/s}$.
D'après \refext{Alg}{composition-trace-norme}
et \refext{Alg}{Norme=pol-car}, on a $\chi_{\FF_{q^r}\bo\FF_q}(x,X)
= \N_{\FF_q(x)[X]\bo\FF_q[X]} (\chi_{\FF_{q^r}\bo\FF_q(x)}(x,X))
= \N_{\FF_q(x)[X]\bo\FF_q[X]}(X-x)^{r/s}
= \chi_{\FF_q(x)\bo\FF_q}(x,X)^{r/s}$.  Or d'après le cas déjà
démontré, $\chi_{\FF_q(x)\bo\FF_q}(x,X) = \prod_{i=0}^{s-1}
(X-\Frob_q^i(x))$ : on a donc $\chi_{\FF_{q^r}\bo\FF_q}(x,X)
= \prod_{i=0}^{s-1} (X-\Frob_q^i(x))^{s/r} = \prod_{i=0}^{r-1}
(X-\Frob_q^i(x))$ en se rappelant que $\Frob_q^s(x) = x^{q^s} = x$.
Ceci démontre la première formule en général.  Les autres formules
s'en déduisent immédiatement.
\end{proof}

\begin{proposition2}\label{surjectivite-trace-et-norme}
Soit $\FF_{q^r}\bo\FF_q$ une extension de corps finis.  Les
applications $\Tr_{\FF_{q^r}\bo\FF_q} \colon \FF_{q^r}\to\FF_q$ et
$\N_{\FF_{q^r}\bo\FF_q} \colon \FF_{q^r}\to\FF_q$ sont surjectives.
De plus, si $g \in \FF_{q^r}$ est primitif, alors
$\N_{\FF_{q^r}\bo\FF_q}(g) \in \FF_q$ est primitif.
\end{proposition2}
\begin{proof}
La trace $\Tr_{\FF_{q^r}\bo\FF_q} \colon \FF_{q^r}\to\FF_q$ étant
$\FF_q$-linéaire, il suffit pour montrer qu'elle est surjective de
montrer qu'elle n'est pas identiquement nulle.  Or en tant que
polynôme à coefficients dans $\FF_q$ (et évalué sur $\FF_{q^r}$), la
trace est donnée par $X + X^q + X^{q^2} + \cdots + X^{q^{r-1}}$ : ce
polynôme étant de degré $q^{r-1}$ (et non identiquement nul), il ne
peut pas s'annuler en tout point de $\FF_{q^r}$, ce qu'on voulait.

La norme $\N_{\FF_{q^r}\bo\FF_q} \colon \FF_{q^r}\to\FF_q$ est donnée
par $x \mapsto x^{(q^r-1)/(q-1)}$.  La valeur $0$ étant manifestement
atteinte, la norme est surjective lorsque tout élément de
$\FF_q^\times$ est atteint.  Or $\FF_{q^r}^\times$ est un groupe
cyclique d'ordre $q^r-1$ (\ref{cyclicite-groupe-multiplicatif-corps}),
et $\FF_q^\times$ est son unique sous-groupe d'ordre $q-1$ : si $g$
est un générateur de $\FF_{q^r}^\times$, alors
$\N_{\FF_{q^r}\bo\FF_q}(g) = g^{(q^r-1)/(q-1)}$ est d'ordre
exactement $q-1$, donc il engendre $\FF_q^\times$, ce qui montre à la
fois la surjectivité et le fait que l'élément annoncé est primitif.
\end{proof}

\subsection{Polynômes de Conway}

Le choix d'un polynôme $h$ irréductible de degré $r$ donné sur $\FF_p$
étant loin d'être unique
(cf. \ref{denombrement-polynomes-irreductibles-corps-finis}), même si
on demande qu'il soit primitif
(cf. \ref{elements-et-polynomes-primitifs}), la présentation de
$\FF_{p^r}$ comme $\FF_p[X]/(h)$ ne l'est pas plus.  Il est parfois
utile par exemple dans un logiciel de calcul formel devant manipuler
$\FF_{p^r}$, de fixer une fois pour toutes une présentation
particulière de chaque corps fini de façon à définir une notation
standard pour ses éléments.  On pourrait pour cela choisir
arbitrairement un polynôme unitaire irréductible de chaque degré sur
chaque $\FF_p$ (comme le plus petit lexicographiquement), mais il
s'avère souhaitable de faire des choix possédant certaites
compatibilités d'un $\FF_q$ à un autre : c'est ce que réalisent les
polynômes de Conway.

Introduisons d'abord une terminologie temporaire pour la condition de
compatibilité qui va nous occuper :

\begin{definition2}\label{familles-compatibles-polynomes-conway}
Soit $p$ un nombre premier.  On dit qu'une famille $h_1,\ldots,h_N$ de
polynômes de $\FF_p[X]$, avec $h_n$ unitaire de degré $n$,
est \emph{compatible au sens de Conway} lorsque :
\begin{itemize}
\item pour chaque $1\leq n\leq N$, le polynôme $h_n$ est primitif
(cf. \ref{elements-et-polynomes-primitifs}),
\item pour tout $m$ divisant $n$ entre $1$ et $N$, la norme
$\N_{\FF_{p^n}\bo\FF_{p^m}}(x) = x^{(p^n-1)/(p^m-1)}$ de $\FF_{p^n}$ à
$\FF_{p^m}$ d'une racine quelconque $x$ de $h_n$ dans $\FF_{p^n}$ est
une racine de $h_m$ (autrement dit, $h_n$ divise
$h_m(X^{(p^n-1)/(p^m-1)})$, cf. \ref{trace-et-norme-corps-finis}).
\end{itemize}
\end{definition2}

(Dans la deuxième condition, le choix de la racine $x$ de $h_n$ est
sans importance : dans tous les cas, le corps $\FF_p(x)$ est isomorphe
à $\FF_p[X]/(h_n)$, et dire que la norme $x^{(p^n-1)/(p^m-1)}$ de $x$
est racine de $h_m$ signifie que $h_m(X^{(p^n-1)/(p^m-1)}) \equiv
0 \pmod{h_n}$.)

\begin{proposition2}\label{existence-polynomes-conway}
Soit $p$ un nombre premier, et $h_1,\ldots,h_{n-1}$ une famille de
polynômes de $\FF_p[X]$, avec $h_i$ unitaire de degré $i$, compatible
au sens de Conway.  Alors il existe $h_n$ unitaire de degré $n$ tel
que $h_1,\ldots,h_n$ soit encore compatible au sens de Conway.
\end{proposition2}
\begin{proof}
Fixons une présentation quelconque de $\FF_{p^n}$.

Montrons dans un premier temps qu'on peut choisir, pour chaque $m$
allant de $1$ à $n-1$, une racine $x_m$ de $h_m$ dans $\FF_{p^n}$, de
façon à avoir la compatibilité suivante : si $\ell|m$ alors
$x_m^{(p^m-1)/(p^\ell-1)} = x_\ell$.  On définit les $x_m$ par
récurrence sur $m$.  Supposons les $x_\ell$ déjà choisis pour
$\ell<m$.  Si $z$ est une racine quelconque de $h_m$ dans $\FF_{p^n}$,
la condition de compatibilité des $h_m$ signifie que pour tout
$\ell|m$ on a $z^{(p^m-1)/(p^\ell-1)} = x_\ell^{p^{j_\ell}}$ pour un
certain $j_\ell \in \ZZ/\ell\ZZ$.  La compatibilité supposée sur
les $x_\ell$ (par récurrence) assure que si $k|\ell|m$ alors
$x_{k}^{p^{j_k}} = z^{(p^m-1)/(p^{k}-1)} = (z^{(p^m-1)/(p^\ell-1)})
^{(p^\ell-1)/(p^{k}-1)} = (x_\ell^{p^{j_\ell}})
^{(p^\ell-1)/(p^{k}-1)} = (x_\ell^{(p^\ell-1)/(p^{k}-1)})
^{p^{j_\ell}} = x_{k}^{p^{j_\ell}}$, donc (l'élément $x_k$ étant de
degré $k$ sur $\FF_p$) on a $j_\ell \equiv j_k \pmod{k}$.  Le théorème
chinois garantit alors qu'il existe $j \in \ZZ/m\ZZ$ tel que $j \equiv
j_\ell \pmod{\ell}$ pour tout $\ell|m$.  On pose $x_m = z^{p^{-j}}$ :
on a alors $x_m^{(p^m-1)/(p^\ell-1)} = x_\ell^{p^{-j} \cdot p^{j_\ell}}
= x_\ell$, comme souhaité.

Soit maintenant $g$ un élément primitif de $\FF_{p^n}$, de sorte que
$\FF_{p^n}^\times$ est isomorphe à $\ZZ/(p^n-1)\ZZ$ par $i \mapsto
g^i$.  Pour chaque $m$ divisant $n$, l'élément $g^{(p^n-1)/(p^m-1)}$
est primitif dans $\FF_{p^m}$ (cf. \ref{surjectivite-trace-et-norme}).
Écrivons $x_m = g^{i_m(p^n-1)/(p^m-1)}$ avec $i_m \in \ZZ/(p^m-1)\ZZ$,
et même $i_m$ inversible (c'est-à-dire premier avec $p^m-1$) puisque
$x_m$ est primitif dans $\FF_{p^m}$.  Si $\ell|m$ alors la
compatibilité $x_m^{(p^m-1)/(p^\ell-1)} = x_\ell$ obtenue au
paragraphe précédent signifie que $(g^{i_m(p^n-1)/(p^m-1)})
^{(p^m-1)/(p^\ell-1)} = g^{i_\ell(p^n-1)/(p^\ell-1)}$ donc $i_m \equiv
i_\ell \pmod{p^\ell-1}$.  Le théorème chinois (avec le fait que
$\pgcd(p^\ell-1, p^m-1) = p^{\pgcd(\ell,m)}-1$) garantit alors qu'il
existe $i \in \ZZ/(p^n-1)\ZZ$ inversible (c'est-à-dire premier avec
$p^n-1$) tel que $i \equiv i_m \pmod{p^m-1}$ pour tout $m|n$.  On
définit $x_n = g^i$ : alors $x_n$ est primitif car $i$ est inversible,
et $x_n^{(p^n-1)/(p^m-1)} = x_m$ pour tout $m|n$.  En appelant $h_n$
le polynôme minimal de $x_n$, le polynôme $h_n$ vérifie toutes les
compatibilités demandées.
\end{proof}

\begin{definition2}\label{definition-polynomes-conway}
Soit $p$ un nombre premier.  On introduit l'ordre total sur $\FF_p$
donné par $0 < 1 < 2 < \cdots < (p-1)$, et l'ordre total sur les
polynômes unitaires de degré $n$ de $\FF_p[X]$ (« ordre
lexicographique alterné ») donné par $X^n - a_1 X^{n-1} + \cdots +
(-1)^n a_n < X^n - b_1 X^{n-1} + \cdots + (-1)^n b_n$ si et seulement
si $a_i < b_i$ pour le plus petit $i$ tel que $a_i \neq b_i$.

On définit alors par récurrence sur l'entier naturel non nul $n$
le \emph{polynôme de Conway} de degré $n$ sur $\FF_p$ comme le plus
petit polynôme unitaire $h_n$ de degré $n$, pour l'ordre introduit
ci-dessus, tel que la famille $h_1,\ldots,h_n$ soit compatible au sens
de Conway (\ref{familles-compatibles-polynomes-conway}).

On appelle \emph{élément de Conway} de $\FF_{p^n}$ tout élément de ce
dernier qui est racine de $h_n$.
\end{definition2}

L'existence de $h_n$ est garantie par la
proposition \ref{existence-polynomes-conway}.  Le choix du polynôme le
plus petit pour l'ordre lexicographique alterné est simplement une
manière de fixer les choix effectués : la condition intéressante de
compatibilité est celle explicitée
en \ref{familles-compatibles-polynomes-conway}.  Un élément de Conway
est primitif (il y en a $n$ dans $\FF_{p^n}$, mais ils sont
conjugués), et sa norme à n'importe quel sous-corps est encore un
élément de Conway.

Le polynôme $h_1$ vaut $X - g$ où $g$ est le plus petit élément
primitif de $\ZZ/p\ZZ$ (pour l'ordre $0<1<\cdots<(p-1)$).  C'est pour
que la classe $x$ de $X$ dans $\FF_p[X]/(h_1)$ soit cet élément $g$
(et non son opposé) qu'on a fait la convention de signes particulière
de l'ordre lexicographique \emph{alterné}.

Le calcul algorithmique du polynôme de Conway $h_n$ (connaissant les
$h_m$ avec $m$ divisant $n$) peut se faire selon essentiellement deux
stratégies :
\begin{itemize}
\item énumérer les polynômes unitaires de degré $n$ dans l'ordre
lexicographique alterné jusqu'à trouver un polynôme primitif et
vérifiant la compatibilité demandée avec les $h_m$, ou bien
\item choisir une présentation quelconque de $\FF_{p^n}$, et dans
celle-ci, énumérer (au moyen d'un élément primitif de $\FF_{p^n}$) les
éléments dont la norme dans chaque $\FF_{p^m}$ pour $m|n$ est un
élément de Conway, et choisir celui dont le polynôme minimal est le
plus petit pour l'ordre lexicographique alterné.
\end{itemize}
La première stratégie applique directement la
définition \ref{familles-compatibles-polynomes-conway}, tandis que la
seconde fonctionne comme l'explique la preuve de la
proposition \ref{existence-polynomes-conway}.  La première est plus
appropriée quand $n$ est peu divisible, tandis que la seconde est plus
efficace si $n$ a beaucoup de diviseurs (donc que les conditions de
compatibilités sont fortes).

À titre d'exemple, le tableau suivant donne les quelques premiers
polynômes de Conway pour $p\leq 7$ :
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
$p=2$&$p^n=2$&$h_1 = X + 1$\\
&$p^n=4$&$h_2 =  X^2 + X + 1$\\
&$p^n=8$&$h_3 =  X^3 + X + 1$\\
&$p^n=16$&$h_4 =  X^4 + X + 1$\\
&$p^n=32$&$h_5 =  X^5 + X^2 + 1$\\
&$p^n=64$&$h_6 =  X^6 + X^4 + X^3 + X + 1$\\
&$p^n=128$&$h_7 =  X^7 + X + 1$\\
&$p^n=256$&$h_8 =  X^8 + X^4 + X^3 + X^2 + 1$\\
&$p^n=512$&$h_9 =  X^9 + X^4 + 1$\\
&$p^n=1024$&$h_{10} =  X^{10} + X^6 + X^5 + X^3 + X^2 + X + 1$\\
\hline
$p=3$&$p^n=3$&$h_1 = X + 1$\\
&$p^n=9$&$h_2 =  X^2 + 2 X + 2$\\
&$p^n=27$&$h_3 =  X^3 + 2 X + 1$\\
&$p^n=81$&$h_4 =  X^4 + 2 X^3 + 2$\\
&$p^n=243$&$h_5 =  X^5 + 2 X + 1$\\
&$p^n=729$&$h_6 =  X^6 + 2 X^4 + X^2 + 2 X + 2$\\
\hline
$p=5$&$p^n=5$&$h_1 = X + 3$\\
&$p^n=25$&$h_2 = X^2 + 4 X + 2$\\
&$p^n=125$&$h_3 = X^3 + 3 X + 3$\\
&$p^n=625$&$h_4 = X^4 + 4 X^2 + 4 X + 2$\\
\hline
$p=7$&$p^n=7$&$h_1 = X + 4$\\
&$p^n=49$&$h_2 = X^2 + 6 X + 3$\\
&$p^n=343$&$h_3 = X^3 + 6 X^2 + 4$\\
\hline
\end{tabular}
\end{center}


\ifx\danslelivre\undefined
\end{document}
\fi