A NNALES DE L’I. H. P., SECTION B

M. M IGNOTTE
J. L. N ICOLAS
Statistiques sur Fq [X]Annales de l’I. H. P., section B, tome 19, no 2 (1983), p. 113-121.
<http://www.numdam.org/item?id=AIHPB_1983__19_2_113_0>© Gauthier-Villars, 1983, tous droits réservés.
L’accès aux archives de la revue « Annales de l’I. H. P., section B »(http://www.elsevier.com/locate/anihpb), implique l’accord avec les conditions générales d’utilisation (http://www.numdam.org/legal.php). Toute utilisation commerciale ou impression systématique est constitutive d’une
infraction pénale. Toute copie ou impression de ce fichier doit contenir la présente mention de copyright.

Article numérisé dans le cadre du programme
Numérisation de documents anciens mathématiques
http://www.numdam.org/

Section B :Ann. Inst. Henri Poincaré,Calcul des Probabilités et Statistique.

Vol. XIX, n° 2, 1983, p. 1 13-121.

Statistiques sur Fq[X]M.

MIGNOTTE

Université Louis-Pasteur, Centre de Calcul de l’Esplanade,7, rue René-Descartes, 67084 Strasbourg, FranceJ. L.

NICOLASU. E. R. des Sciences, 123, Avenue Albert-Thomas
87060 . Limoges, FranceSoit P un polynôme de degré n à coefficients dans un corps
RÉSUMÉ.
fini K. On étudie le degré de la plus petite extension de K dans laquelle
P se factorise complètement. On montre que le logarithme de ce degré est-«

presque touj ours » voisinde - 2 1 Log2n.

Let P be a polynomial of degree n with coefficients in aABSTRACT.
finite field K. We study the degree of the splitting field of P over K. We-show that the logarithm of this degree is « almost always » close1.

to - 2 1 Log2n.

INTRODUCTION

Ce travail a pour origine l’étude de la factorisation des polynômes envariable et à coefficients entiers. Les algorithmes actuels de factorisation comportent, comme étape intermédiaire, la factorisation d’un polynôme à coefficients dans un corps fini. Le principe est le suivant :a) on réduit le polynôme initial G modulo un certain nombre premier p,

uneAnnales de l’Institut Henri Poincaré-Section B-Vol. XIX, 0020-2347/ 1983 ~l 13 ;’$ 5,00/~ Gauthier-Villars-5

114

M. MIGNOTTE ET J. L. NICOLASb) le polynôme F de] ainsi obtenu est factorisé dans cet anneau,toutec) pourdécomposition F FIF2 du polynôme F danson teste si F~ est l’image modulo p d’un certain facteur de G, ceci en utili=sant une variante un lemme de Hensel.

Les étapes a) et b) ont un coût raisonnable (polynomial en fonction dudegré et de la taille de G). Mais l’étape c) peut être très coûteuse (pour certains algorithmes, son coût peut être exponentiel en fonction du degré de G).
Le coût de l’étape c) dépend du nombre de facteurs irréductibles de F (siF possède k facteurs irréductibles il y a 2k décompositions possibles de laforme FFIF2). Il était donc important d’obtenir des renseignements
statistiques sur la factorisation de F pour connaître quel est « en général »le coût de l’étape c). Dans un algorithme de Mc. Eliece le degré, noté ici r(F),de la plus petite extension de ~p dans laquelle F se décompose complètement joue un rôle important. Nous étudierons tout particulièrement cette=fonction.
La quantité r(F) est égale au p. p. c. m. des degrés des facteurs irréductibles de F. Il est apparu de nombreuses analogies entre le comportement
de cette fonction et celui de l’ordre d’une permutation, qui est égal aup. p. c. m. des ordres des cycles de cette permutation. Cette deuxième fonction a été étudiée par Erdôs et Turan [Erd1]] et la méthode qu’ils ont
utilisée a pu être adaptée ici pour l’étude statistique de la fonction r (cf.
aussi [Bestet [Nic2 D..

Soit IF q le corps à q éléments, et soit
[X]l’anneau des polynômes à uneOn désigne par En l’ensemble des polynômes unitaires
indéterminée surde degré n de IFq [X]. On a donc : card En
qn. Soit ~m l’ensemble descard 8m, et l’on a (cf. :m.
Ondepose Im
polynômes irréductibles degré==’[Ber], [Car])est la fonction de Môbius. Il en résulte l’encadrement :Pour A E En’onécrira la décomposition en facteurs irréductibles :Annales de l’Institut Henri Poincaré-Section B

115

STATISTIQUES SUR

et l’on pose pour 1

i _ k :deg Pi=n; . On a donc :et aussi :On définit~/~max r(A) vérifie log g(n) ~La fonction g(n)log n, et a été étudiéedansNous nous proposons de démontrer le théorème suivant :=/A l’exception d’au plus O
THÉORÈME.
polynômes A de En vérifient
2014

II.
LEMME 1.

-B’’q (log n)7/32-"ÉTUDE DE LA FONCTION

Soit T un nombre entier, 1 _ TOn a :Démonstration. On aVol. XIX, n° 2-1983.

n, d’entre eux, lescc~Tn.

On pose116

M. MIGNOTTE ET J. L. NICOLAS

Notons que la constante sous entendue par le 0(1) est absolue, le plus
mauvais cas étant q
2. Pour une estimation plus précise voir [Kno ], p. 85.
=Avec les notations du lemme 1, il existe une constanteabsolue C telle que, pour tout T, 2 T n, on ait :LEMME 2.

-Démonstration. Suivons la démonstration de [Har ] pour la fonction cv
des nombres entiers ;1) est le nombre de paires P, Q avec
tellesetP ~ Q
que PA
QA, en comptant (P, (3) ~ (Q, P). On a donc
enposantD’où il vient :La démonstration du lemme s’achève en utilisant la formule

ainsi que le lemme 1.
LEMME 3 (Inégalité de Chebychev pour la fonction cv).

-Annales de l’Institut Henri Poincat-é-Section B

STATISTIQUES SUR

FJX]

117

Démonstration. On applique le lemme 2 avec T
LEMME 4.

-=n.

T’ n. Le nombre de polynômes A E EnTn,Soitet vérifiant pour tout T, T’

est au plus

Démonstration (Cf. [Erd2 ]). - D’après le lemme 2, le nombre de A E E"
’tels queest majoré par

Cqn/Z2.

On applique ce résultat pour T
Ti exp (i4), Z Z~
de polynômes A E En et vérifiant pour un certain i > io
==

=

=

i : le nombre

est au plus

On choisit io de façon que T~+i ~ T’ : on prend ~odonc io > 9. Excepté pour au plus
pour A E En et pour tout> io ,=polynômes de E~, on a,
T’ 2014 2T
n. Il existe i > io + 1 tel
Soit maintenant T vérifiant T’Ti T Ti+ i. On a alors, grâce à la croissance en T deet commeDe même :Ce qui achève la démonstration.
Vol. XIX, n° 2-1983.

1 ],

118

M. MIGNOTTE ET J. L. NICOLASET DU PRODUIT

III. COMPARAISON DU P. P. C. M.

LEMME 5.
Soit n > e~, et soit m un nombre entier > log n. Le
nombre de polynômes A E En qui ont deux diviseurs irréductibles dont le-degré est un multiple de m est majoré par q n(log2 n)2.

Démonstration. Comment fabriquer un tel polynôme A ? On choisit
polynôme irréductible de degré am, a > 1, et un polynôme irréductible
de degré bm, b > 1, avec (a + b)mn. Enfin on multiplie par un polynôme quelconque de degré n - (a + b)m. Le nombre de tels polynômes
est donc inférieur ou égal à :un

LEMME 6.

-On définit, pour m ~ N*, p(m)=max p . Avec les notapremiertions de l’introduction, le nombre de polynômes A e En pour lesquels(log n)3 est au plus 20142014"~~On doit compter les polynômes de En pour lesquels
Démonstration.
et P~. D’après le lemme 5,il existe p premier > (log ~ telsil y en a au plus :il existe ï et j, 1
pour ~ ~ ee.

fj ~ k tels queni))-LEMME 7.

-Soitp(log n)3 ~. Pour n > no,on a :_Démonstration.
On peut suivre la démonstration du lemme V de[Erd 1 ], qui permet d’expliciter no. On peut aussi utiliser les résultats deDe Bruijn sur la fonction-Annales de l’Institut Henri Poincaré-Section B

119STATISTIQUES SURet écrire la somme à majorer au moyen de l’intégrale de Stieltjes

On obtient une meilleure majoration, mais les constantes ne sont pas
explicitées dans les estimations de De Bruijn (cf. [Bru]).

LEMME 8.
divisant-lesSoitOn écritdegrés des polynômes irréductibles

avec :

Alors le nombre de polynômes A E En pour lesquels il existe i tel que> exp({log log n)4), 1-i-k, est au plusgrand.

qog ndès que n est assez

Démonstration. Pour un tel polynôme A, ~m E R, m > exp ((log log n)4)
tel que A ait un facteur irréductible dont le degré est multiple de m. Par un
raisonnement déjà fait dans la démonstration du lemme 5, pour un m fixe,
il y a au plus qn

polynômes A ayant un facteur irréductible

de degré multiple de m. Le nombre total de polynômes A est donc majoré par

LEMME 9.

-Pour nassez - grand, à l’exception d’au plus ~°~ ’~~ poly-nômes, les éléments de E~ vérifient

2014

On enlève d’abord de En les polynômes tels quek > 2 log yï. D’après le lemme 3, avec /L==il y en a au plus

Cqn log n.

On enlève ensuite les polynômes tels que pour un couple f, ~ (ï 5~ 7) on aitp((ni, nj)) > (log n)3. D’après le lemme 6, il y en a au plus 20142014 . On enlève
Vol. XIX, n03BF 2-1983.

M. MIGNOTTE ET J. L. NICOLAS

120enfin les polynômes pour lesquels il existe i, tel quen

D’après le lemme 8, il y en a au plus q> exp((log log n)4).

. Pour les polynômes restants,

sont premiers entre eux, et l’on a :lesIV.

DÉMONSTRATION DU THÉORÈMEOn choisit, dans le lemme 4, log T’ (log n)7/8 . En enlevant
polynômes de E~, on aura pour ceux qui restent:=O ( qn (log n)7/32)~~

On a par ailleurs :cequi entraîne :Il vient alors :avec

Annales de l’Institut Henri Poincaré-Section B

121

STATISTIQUES SUR

On applique ensuite le lemme 9 : en enlevant 0(qn/log n) polynômes, onaura pour les polynômes A restants :RÉFÉRENCES[Ber] E. R. BERLEKAMP, Algebraic coding theory, Mc Graw Hill, New York, 1968.
[Best] M. R. BEST, The distribution of some variables on symmetric groups,Nederl. Akademie Wetens. Proc., ser. A, t. 73, n° 5, 1970, p. 385-402.

[Bru] N. G. DE BRUIJN, On the number of positive integers ~ x and free of prime
factors > y. I, Nederl. Akad. Wetensch. Proc. ser. A, t. 54, 1951, p. 50-60.
Some topics in the arithmetic of polynomials, Bull. Amer.
Math. Soc., t. 48, 1942, p. 679-691.
[Erd1] P. ERDÖS and P. TURAN, On some problems of a statistical group-theory I.
Zeit. f. Wahrscheinlichkeitstheorie und verw. Gebiete, t. 4, 1965, p. 175-186.
[Erd2] P. ERDÖS, Some unconventional problems in number theory, Astérisque,t. 61, 1979, p. 73-82.
[Har] G. H. HARDY and E. M. WRIGHT, An introduction to the theory of numbers, 4th ed. Oxford, at the Clarendon Press, 1960.
[Kno] J. KNOPFMACHER, Analytic arithmetic of algebraic function fields, MarcelKekker inc., 1979, Lecture Notes in pure and applied mathematics, vol. 50.
[Mc. E] R. J. Mc ELIECE, Factorization of polynomials over finite fields, Math.
of Comp., t. 23, n° 108, 1969, p. 861-868.
[Nic 1]J. L. NICOLAS, Ordre maximal d’un élément du groupe Sn des permutationset « highly composite numbers », Bull. Soc. Math. France, t. 97, 1969,
p. 129-191.
[Nic 2] J. L. NICOLAS, Statistiques sur le groupe symétrique, Séminaire DelangePisot-Poitou (théorie des nombres), 13e année, 1971-1972, n° G2, 6 p.

[Car] L. CARLITZ,(Manuscrit reçu le 30 octobre 1981 )Vol. XIX, n° 2-1983.