Algèbre T1
d’où une minoration de I(n, p). Finalement :
p n − p E(n/2)+1
n
I(n, p)
p n
n
·
Cela montre que I(n, p) > 0. Mieux encore, on en déduit qu’un polynôme irréductible unitaire de grand degré n choisi au hasard a, en gros, une chance sur n
d’être irréductible.
Enfin, expliquons comment vérifier le critère d’irréductibilité de manière efficace : on se place dans l’anneau quotient F p [x]/(P ) et on calcule les puissances x p i
de x modulo P . Puisque x p i+1 = (x p i ) p , on procède par récurrence et on calcule
successivement les restes R i de la division euclidienne de R
p
i−1 par P , à partir
de R 0 = x. La condition (i) s’écrit R n = x et la condition (ii) est équivalente à
R i = x pour i < n.
1. Écrire une procédure irreductible?:=proc(P,p) testant l’irréductible de P
sur F p (où P est entré comme un polynôme à coefficients entiers). On utilisera
la stratégie exposée ci-dessus.
La fonction suivante permet de tirer au hasard un polynôme unitaire de degré
n 1 dans F p [x] :
>randpol:=(n,p)->sort(x^n+RandomTools[Generate]
(polynom(integer(range=0..p-1), x,degree=n-1))):
Vérifier que la probabilité d’obtenir un polynôme irréductible de degré n par
un tel tirage au hasard est de l’ordre de 1/n. On pourra écrire une procédure
test:=proc(N,n,p) renvoyant la proportion de cas favorables pour N tirages.
Enfin, écrire une procédure polirreductible:=proc(n,p) renvoyant un polynôme de F p [x] unitaire irréductible de degré n.
Factorisation sur F p
L’algorithme procède en plusieurs étapes.
La première étape consiste à éliminer les facteurs multiples à l’aide de la
dérivation. Écrivant f =
a i x i ∈ F p [x], le polynôme dérivé est par définition
f =
ia i x i−1 . Il est nul si et seulement si f ∈ F p [x p ], ou encore, puisque
a ip x ip = (
a ip x i ) p , si et seulement si f = g p , g ∈ F p [x]. En particulier, la
dérivée d’un polynôme irréductible est non nulle.
Il s’agit d’écrire la « factorisation sans facteur carré » de f , c’est-à-dire la
décomposition f = λh 1
1 h 2
2 . . . h s
s où λ est le coefficient dominant de f et les h i
sont unitaires sans facteur carré et premiers deux à deux. Si f = λ
r
i=1 f
e i
i
252
d’où une minoration de I(n, p). Finalement :
p n − p E(n/2)+1
n
I(n, p)
p n
n
·
Cela montre que I(n, p) > 0. Mieux encore, on en déduit qu’un polynôme irréductible unitaire de grand degré n choisi au hasard a, en gros, une chance sur n
d’être irréductible.
Enfin, expliquons comment vérifier le critère d’irréductibilité de manière efficace : on se place dans l’anneau quotient F p [x]/(P ) et on calcule les puissances x p i
de x modulo P . Puisque x p i+1 = (x p i ) p , on procède par récurrence et on calcule
successivement les restes R i de la division euclidienne de R
p
i−1 par P , à partir
de R 0 = x. La condition (i) s’écrit R n = x et la condition (ii) est équivalente à
R i = x pour i < n.
1. Écrire une procédure irreductible?:=proc(P,p) testant l’irréductible de P
sur F p (où P est entré comme un polynôme à coefficients entiers). On utilisera
la stratégie exposée ci-dessus.
La fonction suivante permet de tirer au hasard un polynôme unitaire de degré
n 1 dans F p [x] :
>randpol:=(n,p)->sort(x^n+RandomTools[Generate]
(polynom(integer(range=0..p-1), x,degree=n-1))):
Vérifier que la probabilité d’obtenir un polynôme irréductible de degré n par
un tel tirage au hasard est de l’ordre de 1/n. On pourra écrire une procédure
test:=proc(N,n,p) renvoyant la proportion de cas favorables pour N tirages.
Enfin, écrire une procédure polirreductible:=proc(n,p) renvoyant un polynôme de F p [x] unitaire irréductible de degré n.
Factorisation sur F p
L’algorithme procède en plusieurs étapes.
La première étape consiste à éliminer les facteurs multiples à l’aide de la
dérivation. Écrivant f =
a i x i ∈ F p [x], le polynôme dérivé est par définition
f =
ia i x i−1 . Il est nul si et seulement si f ∈ F p [x p ], ou encore, puisque
a ip x ip = (
a ip x i ) p , si et seulement si f = g p , g ∈ F p [x]. En particulier, la
dérivée d’un polynôme irréductible est non nulle.
Il s’agit d’écrire la « factorisation sans facteur carré » de f , c’est-à-dire la
décomposition f = λh 1
1 h 2
2 . . . h s
s où λ est le coefficient dominant de f et les h i
sont unitaires sans facteur carré et premiers deux à deux. Si f = λ
r
i=1 f
e i
i
252