Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Vérifier qu"un polynôme est primitif
481 views
Skip to first unread message
Laurent Claessens
Dec 20, 2011, 4:30:44 AM12/20/11
to
Bonjour
J'aimerais utiliser le polynome P=X^4+X^3+1 pour construire F_(16).
Je sais que F_2/P sera de toutes façon un corps à 16 éléments, mais si
X^4+X^3+1 est en plus primitif, je saurai de plus que F_16 sera
constructible comme étant les puissances succésives d'une racine de P.
J'ai trouvé pas mal de trucs sur internet qui parlent de ces choses,
mais je ne suis pas parvenu à mettre tout bien au clair dans ma tête.
1. comment vérifier que X^4+X^3+1 est primitif (sur F_2) ?
2. si c'est le cas, est-ce que je peux faire la construction
suivante ?
Soit K=F_2/X^4+X^3+1.
Soit a la classe de X dans ce quotient
On a : K=
a
a^2,
a^3
...
a^15
et toutes ces puissances sont des éléments distincts dans K.
3. Si P est primitif, alors la classe de X dans F_2/P est un
générateur du groupe multiplicatif (F_2/P)*
Ma question est surtout la 1 : pour les questions 2 et 3, je suis
presque certain que les réponses sont «oui».
Merci de vos lumières; si vous avez un lien qui donne tout ça bien
expliqué je suis très preneur.
Bonne journée
Laurent
J'aimerais utiliser le polynome P=X^4+X^3+1 pour construire F_(16).
Je sais que F_2/P sera de toutes façon un corps à 16 éléments, mais si
X^4+X^3+1 est en plus primitif, je saurai de plus que F_16 sera
constructible comme étant les puissances succésives d'une racine de P.
J'ai trouvé pas mal de trucs sur internet qui parlent de ces choses,
mais je ne suis pas parvenu à mettre tout bien au clair dans ma tête.
1. comment vérifier que X^4+X^3+1 est primitif (sur F_2) ?
2. si c'est le cas, est-ce que je peux faire la construction
suivante ?
Soit K=F_2/X^4+X^3+1.
Soit a la classe de X dans ce quotient
On a : K=
a
a^2,
a^3
...
a^15
et toutes ces puissances sont des éléments distincts dans K.
3. Si P est primitif, alors la classe de X dans F_2/P est un
générateur du groupe multiplicatif (F_2/P)*
Ma question est surtout la 1 : pour les questions 2 et 3, je suis
presque certain que les réponses sont «oui».
Merci de vos lumières; si vous avez un lien qui donne tout ça bien
expliqué je suis très preneur.
Bonne journée
Laurent
jlp
Dec 20, 2011, 11:05:20 AM12/20/11
to
la définition suivante ( s'il est correcte) trouvé sur internet:
http://www.bibmath.net/dico/index.php?action=affiche&quoi=./p/primitif.html
--
Cordialement
Jean-Louis Pasturel
AP
Dec 20, 2011, 12:38:15 PM12/20/11
to
On Tue, 20 Dec 2011 01:30:44 -0800 (PST), Laurent Claessens
<moky...@gmail.com> wrote:
> Bonjour
>
>
> J'aimerais utiliser le polynome P=X^4+X^3+1 pour construire F_(16).
comme il est irréductible sur F_2[X] , pas de pb :F_2[X]/P donne F_16
<moky...@gmail.com> wrote:
> Bonjour
>
>
> J'aimerais utiliser le polynome P=X^4+X^3+1 pour construire F_(16).
les deux autres poly irré sur F_2[X] sont P2=X^4+X+1 et
P3=X^4+X^3+X^2+X+1 qui donnent aussi F_16
>Je sais que F_2/P sera de toutes façon un corps à 16 éléments, mais si
>X^4+X^3+1 est en plus primitif, je saurai de plus que F_16 sera
>constructible comme étant les puissances succésives d'une racine de P.
>
>J'ai trouvé pas mal de trucs sur internet qui parlent de ces choses,
>mais je ne suis pas parvenu à mettre tout bien au clair dans ma tête.
>
>1. comment vérifier que X^4+X^3+1 est primitif (sur F_2) ?
pour moi primitif c'est le pgcd des coeff =1
>X^4+X^3+1 est en plus primitif, je saurai de plus que F_16 sera
>constructible comme étant les puissances succésives d'une racine de P.
>
>J'ai trouvé pas mal de trucs sur internet qui parlent de ces choses,
>mais je ne suis pas parvenu à mettre tout bien au clair dans ma tête.
>
>1. comment vérifier que X^4+X^3+1 est primitif (sur F_2) ?
>2. si c'est le cas, est-ce que je peux faire la construction
>suivante ?
> Soit K=F_2/X^4+X^3+1.
> Soit a la classe de X dans ce quotient
> On a : K=
>a
>a^2,
>a^3
>...
>a^15
>et toutes ces puissances sont des éléments distincts dans K.
oui c'est vrai , et ces 15 éléments sont non nuls cad cl(X) engendre
> On a : K=
>a
>a^2,
>a^3
>...
>a^15
>et toutes ces puissances sont des éléments distincts dans K.
K
ca marche aussi pour P2 , mais pour P3, cl(X) n'engendre pas
(F2[X]/P2)* : il engendre un sgroupe d'ordre 5 ;
>3. Si P est primitif, alors la classe de X dans F_2/P est un
>générateur du groupe multiplicatif (F_2/P)*
AP
Dec 20, 2011, 2:38:39 PM12/20/11
to
On Tue, 20 Dec 2011 18:38:15 +0100, AP
<marc.pi...@wanadoo.fr.invalid> wrote:
>On Tue, 20 Dec 2011 01:30:44 -0800 (PST), Laurent Claessens
<marc.pi...@wanadoo.fr.invalid> wrote:
>On Tue, 20 Dec 2011 01:30:44 -0800 (PST), Laurent Claessens
>>et toutes ces puissances sont des éléments distincts dans K.
>
>oui c'est vrai , et ces 15 éléments sont non nuls cad cl(X) engendre
>K
>
engendre K* et non K
>
>oui c'est vrai , et ces 15 éléments sont non nuls cad cl(X) engendre
>K
>
Laurent Claessens
Dec 21, 2011, 4:41:58 AM12/21/11
to
> >1. comment vérifier que X^4+X^3+1 est primitif (sur F_2) ?
>
> pour moi primitif c'est le pgcd des coeff =1
internet.
> oui c'est vrai , et ces 15 éléments sont non nuls cad cl(X) engendre
> K
>
> ca marche aussi pour P2 , mais pour P3, cl(X) n'engendre pas
> (F2[X]/P2)* : il engendre un sgroupe d'ordre 5 ;
>
> >3. Si P est primitif, alors la classe de X dans F_2/P est un
> >générateur du groupe multiplicatif (F_2/P)*
>
> c'est bien sûr cela , vu P3?
http://wims.unice.fr/wims/wims.cgi
D'après elle, P3 n'est pas primitif.
Et c'est ce qui me chiffonne. Il y a des polynômes irréductibles dont
le pgcd des coefficients est 1 et qui ne sont pas primitifs.
En fait une définition largement diffusée sur internet est la
suivante :
un polynôme de degré n dans F_p[X] est primitif si l'ordre de ses
racines dans F_p[X]/P est p^n-1.
Cette définition n'est manifestement pas équivalente à celle avec le
pgcd, comme l'indique très justement ce P3.
Par ailleurs, pour répondre à la question, oui je suis quasiment
certain que si P est primitif, alors la classe de X dans F_p[X]/P est
un générateur du groupe (F_p[X]/P)*. (c'est la seconde définition la
plus courante sur internet)
En fait la définition avec le pgcd est valable dans un anneau
factoriel; je ne sais pas (mais je vais vérifier) si F_p est un anneau
factoriel. Si ce n'est pas le cas, alors ça explique au moins pourquoi
les deux définitions ne sont pas équivalentes.
Mais ça n'expliquerait pas comment on peut vérifier si un polynôme
donné est primitif au sens où dans le quotient, la classe de X est
d'ordre p^n-1.
Bonne journée
Laurent
Lavau Gerard
Dec 21, 2011, 6:10:13 AM12/21/11
to
AP <marc.pi...@wanadoo.fr.invalid> wrote:
>>1. comment vérifier que X^4+X^3+1 est primitif (sur F_2) ?
>pour moi primitif c'est le pgcd des coeff =1
Laurent veut peut-être plutôt demander :
>>1. comment vérifier que X^4+X^3+1 est primitif (sur F_2) ?
>pour moi primitif c'est le pgcd des coeff =1
a) comment savoir si un polynôme est irréductible ?
b) comment savoir si ses racines sont primitives ?
Pour le a), dans le cas présent, ça peut se faire à la main comme
suit. 0 et 1 ne sont pas racines, donc s'il y a des facteurs, ils sont
du second degré. Mais :
X^4 + X^3 + 1 = (X^2 + a*X + 1)(X^2 + b*X + 1)
conduit à :
a + b = 1 (termes en X^3)
a + b = 0 (termes en X)
ce qui est impossible.
Y a-t-il une procédure générale pour les polynômes de degré quelconque
?
Pour le b), y a-t-il une autre méthode à part calculer effectivement
les puissances de alpha, alpha racine du polynôme ?
Lavau Gérard
AP
Dec 21, 2011, 6:31:46 AM12/21/11
to
p^n-1=(p^n)-1, donc comme cl(P)=0, cl(X) est racine de P donc d'ordre
(p^n)-1 donc générateur du groupe (F_p[X]/P)*.
d'ailleurs ttes les racines de P sont géné
idem pour X^4+X+1
ce qui fait 8 géné donc on a tous les géné puisque leur nombre est
phi(15)=8
rem F_16 est constitué des 16 racines de X^16-X=
X(X+1)(X^2+X+1)(X^4+X+1(X^4+X^3+1)(X^4+X^3+X^2+X+1]
>En fait la définition avec le pgcd est valable dans un anneau
>factoriel; je ne sais pas (mais je vais vérifier) si F_p est un anneau
>factoriel. Si ce n'est pas le cas, alors ça explique au moins pourquoi
>les deux définitions ne sont pas équivalentes.
>Mais ça n'expliquerait pas comment on peut vérifier si un polynôme
>donné est primitif au sens où dans le quotient, la classe de X est
>d'ordre p^n-1.
ca , je ne sais pas si ca court les rues...
>factoriel; je ne sais pas (mais je vais vérifier) si F_p est un anneau
>factoriel. Si ce n'est pas le cas, alors ça explique au moins pourquoi
>les deux définitions ne sont pas équivalentes.
>Mais ça n'expliquerait pas comment on peut vérifier si un polynôme
>donné est primitif au sens où dans le quotient, la classe de X est
>d'ordre p^n-1.
(Escofier dans son chapitre sur les corps finis ne l'évoque pas , mais
bon c'est pas le seul ouvrage sur la question)
>Bonne journée
>Laurent
Laurent Claessens
Dec 21, 2011, 10:40:23 AM12/21/11
to
> cf ta définition de primitif : ttes les racines de P sont d'ordre
> p^n-1=(p^n)-1, donc comme cl(P)=0, cl(X) est racine de P donc d'ordre
> (p^n)-1 donc générateur du groupe (F_p[X]/P)*.
montrer que X^4+X^3+1 est primitif, c'est à dire que ces racines
génèrent le groupe (F_p[X]/P)*
Cela dit, à défaut de méthodes générales pour vérifier si un polynôme
est primitif, on peut vérifier que la classe de X est génératrice
assez vite dans les cas de dimensions pas trop grande :
Nous avons X^4+X^3+1=1, donc X^4=X^3+1 (parce que -1=1) et par
conséquent les puissances de X sont
X
X^2
X^3
X^3+1
X^3+X+1
X^3+X^2+X+1
X^2+X+1
X^3+X^2+X
X^2+1
X^3+X
X^3+X^2+1
X+1
X^2+X
X^3+X^2
1
Cela font bien 15 éléments distincts et prouve que X^4+X^3+1 est
primitif.
Bref, je suis toujours preneur d'idées
merci pour vos réponses
Laurent
AP
Dec 21, 2011, 11:56:30 AM12/21/11
to
On Wed, 21 Dec 2011 07:40:23 -0800 (PST), Laurent Claessens
<moky...@gmail.com> wrote:
>
>> cf ta définition de primitif : ttes les racines de P sont d'ordre
>> p^n-1=(p^n)-1, donc comme cl(P)=0, cl(X) est racine de P donc d'ordre
>> (p^n)-1 donc générateur du groupe (F_p[X]/P)*.
>
>Heu ... j'avoue que je ne suis pas très bien ces "donc". Je cherche à
>montrer que X^4+X^3+1 est primitif, c'est à dire que ces racines
>génèrent le groupe (F_p[X]/P)*
le but c'était de montrer que cette définition de poly primitif
<moky...@gmail.com> wrote:
>
>> cf ta définition de primitif : ttes les racines de P sont d'ordre
>> p^n-1=(p^n)-1, donc comme cl(P)=0, cl(X) est racine de P donc d'ordre
>> (p^n)-1 donc générateur du groupe (F_p[X]/P)*.
>
>Heu ... j'avoue que je ne suis pas très bien ces "donc". Je cherche à
>montrer que X^4+X^3+1 est primitif, c'est à dire que ces racines
>génèrent le groupe (F_p[X]/P)*
implique effectivement que cl(X) est générateur du groupe
multiplicatif du corps quotient
>Cela dit, à défaut de méthodes générales pour vérifier si un polynôme
>est primitif, on peut vérifier que la classe de X est génératrice
>assez vite dans les cas de dimensions pas trop grande :
je ne connais pas d'autre méthode
>est primitif, on peut vérifier que la classe de X est génératrice
>assez vite dans les cas de dimensions pas trop grande :
>Nous avons X^4+X^3+1=1, donc X^4=X^3+1 (parce que -1=1) et par
X^4+X^3+1=0
>conséquent les puissances de X sont
>
>X
>X^2
>X^3
>X^3+1
>X^3+X+1
>X^3+X^2+X+1
>X^2+X+1
>X^3+X^2+X
>X^2+1
>X^3+X
>X^3+X^2+1
>X+1
>X^2+X
>X^3+X^2
>1
>
>Cela font bien 15 éléments distincts et prouve que X^4+X^3+1 est
>primitif.
en fait vu la définition que tu as donnée de primitif ceci ne le
>
>X
>X^2
>X^3
>X^3+1
>X^3+X+1
>X^3+X^2+X+1
>X^2+X+1
>X^3+X^2+X
>X^2+1
>X^3+X
>X^3+X^2+1
>X+1
>X^2+X
>X^3+X^2
>1
>
>Cela font bien 15 éléments distincts et prouve que X^4+X^3+1 est
>primitif.
prouve pas : il faudarit montrer que ttes les racines de P sont géné
du groupe cylcique (Z/2Z[X]/P)*
en fait on peut montrer la propiété : si une racine de P est
générateur du groupe cyclique (Z/2Z[X]/P)* , toutes les racines de P
sont générateur de ce groupe cyclique
[et si on a une racine de P on obtient les autres par des élévations
successives à la puissance 2 : ici
X^2, X^4, X^8 sont aussi racine de P , donc générateurs du groupe
cylique , ce qui est d'ailleurs cohérent avec le fait que 2,4,8 sont
1er avec 15 ;
vérif P(X^2)=X^8+X^6+1=(X^3+1)^2+X^6+1=X^6+1+X^6+1=0]
donc prouver qu'une racine de P est géné prouve que P est
effectivement primitif ;
la ppté ci-dessus justifie d'ailleurs la définition
en fait on doit l'appeler poly primitif car un géné du groupe
multiplicatif (Z/2Z[X]/P)* peut être considéré comme un élément
primitif de l'extension de corps Z/2Z -> Z/2Z[X]/P
mais tout élément primitif de cette extension n'est pas forcément
générateur du groupe multiplicatif
>Bref, je, suis toujours preneur d'idées>merci pour vos réponses
>Laurent
Mehdi Tibouchi
Dec 22, 2011, 1:23:50 AM12/22/11
to
Laurent Claessens wrote in message
<b2a4b7a5-64f3-49d2...@q11g2000vbq.googlegroups.com>:
notions mathématiques distinctes, et c'est le cas ici : « primitif » au
sens « coefficients premiers entre eux » et au sens « ayant pour racine
un générateur du groupe multiplicatif de l'extension », ça n'a rien à
voir. Cela dit, ça ne devrait pas causer de grande confusion dans la
mesure où sur un corps, tous les polynômes non nuls sont primitifs au
premier sens (et donc personne ne s'intéresse à cette notion dans le cas
d'un corps).
> Mais ça n'expliquerait pas comment on peut vérifier si un polynôme
> donné est primitif au sens où dans le quotient, la classe de X est
> d'ordre p^n-1.
Ce n'est pas forcément très simple à faire.
Une approche raisonnable, surtout pour les tailles qui semblent vous
intéresser, consiste à dire (sachant que P est un polynôme irréductible
de degré n sur F_p) que X est d'ordre exactement p^n-1 dans le groupe
multiplicatif si et seulement si X^{(p^n-1)/q} est différent de 1 dans
F_p[X]/(P) pour tout diviseur premier q de p^n-1.
Pour p=2 et n=4, p^n-1 = 15 a deux diviseurs premiers (3 et 5), donc il
suffit de vérifier deux inégalités dans F_2[X]/(P) (dont l'une est
triviale) pour tester le caractère primitif.
<b2a4b7a5-64f3-49d2...@q11g2000vbq.googlegroups.com>:
>
>> pour moi primitif c'est le pgcd des coeff =1
>
> C'est un de mes doutes. Certes c'est la définition la plus donnée sur
> internet.
Il arrive malheureusement souvent qu'un même mot désigne plusieurs
>> pour moi primitif c'est le pgcd des coeff =1
>
> C'est un de mes doutes. Certes c'est la définition la plus donnée sur
> internet.
notions mathématiques distinctes, et c'est le cas ici : « primitif » au
sens « coefficients premiers entre eux » et au sens « ayant pour racine
un générateur du groupe multiplicatif de l'extension », ça n'a rien à
voir. Cela dit, ça ne devrait pas causer de grande confusion dans la
mesure où sur un corps, tous les polynômes non nuls sont primitifs au
premier sens (et donc personne ne s'intéresse à cette notion dans le cas
d'un corps).
> Mais ça n'expliquerait pas comment on peut vérifier si un polynôme
> donné est primitif au sens où dans le quotient, la classe de X est
> d'ordre p^n-1.
Une approche raisonnable, surtout pour les tailles qui semblent vous
intéresser, consiste à dire (sachant que P est un polynôme irréductible
de degré n sur F_p) que X est d'ordre exactement p^n-1 dans le groupe
multiplicatif si et seulement si X^{(p^n-1)/q} est différent de 1 dans
F_p[X]/(P) pour tout diviseur premier q de p^n-1.
Pour p=2 et n=4, p^n-1 = 15 a deux diviseurs premiers (3 et 5), donc il
suffit de vérifier deux inégalités dans F_2[X]/(P) (dont l'une est
triviale) pour tester le caractère primitif.
Laurent Claessens
Dec 23, 2011, 12:59:42 PM12/23/11
to
Merci à tous pour vos réponses. Les choses sont maintenant plus
claires.
Si ça intéresse quelqu'un, j'ai écrit les résultats de mes cogitations
en tenant compte de vos réponses dans
http://student.ulb.ac.be/~lclaesse/mes_notes.pdf
(toutes vos remarques sont les bienvenues)
Bonne fêtes
Laurent
Mehdi Tibouchi
Dec 23, 2011, 9:13:54 PM12/23/11
to
Laurent Claessens wrote in message
<31c14e0f-6e24-4bb1...@t16g2000vba.googlegroups.com>:
>
> Si ça intéresse quelqu'un, j'ai écrit les résultats de mes cogitations
> en tenant compte de vos réponses dans
> http://student.ulb.ac.be/~lclaesse/mes_notes.pdf
> (toutes vos remarques sont les bienvenues)
Je suppose que ce sont les paragraphes 2.10.2 et 2.10.3 (ça pourrait être
> Si ça intéresse quelqu'un, j'ai écrit les résultats de mes cogitations
> en tenant compte de vos réponses dans
> http://student.ulb.ac.be/~lclaesse/mes_notes.pdf
> (toutes vos remarques sont les bienvenues)
utile de préciser, parce que personne n'a envie de parcourir un document
de 1000 pages !).
Voici quelques remarques :
* Dans toute cette partie, K/(P) n'a pas de sens. Veillez à toujours écrire
K[X]/(P).
* Si je regarde la preuve de la proposition 2.124 :
-- la preuve de (1) montre que n'importe quel polynôme annulateur non
nul est minimal, ce qui est clairement faux. Je vous invite à
chercher l'erreur.
-- dans la preuve du (2), il est fait allusion à un groupe cyclique
d'ordre q. Je ne vois pas lequel (et du reste il est faux qu'un
élément x d'un tel groupe satisfasse x^q = x).
* Au paragraphe suivant, il est affirmé que X^4+1 est un polynôme
irréductible sur F_2. C'est faux.
Joyeux Noël.
Laurent Claessens
Dec 24, 2011, 5:56:52 AM12/24/11
to
> Je suppose que ce sont les paragraphes 2.10.2 et 2.10.3 (ça
pourrait être
> utile de préciser, parce que personne n'a envie de parcourir un document
> de 1000 pages !).
Mwouais; je ne sais pas très bien comment indiquer les pages ou les
pourrait être
> utile de préciser, parce que personne n'a envie de parcourir un document
> de 1000 pages !).
numéros de sections parce que c'est destiné à changer régulièrement.
C'est sans doute une limitation de la philosophie "release early
release often" appliquée aux textes de math.
Bref, il s'agit effectivement de la sous-section intitulée
"Construction de F_q" dans la section "Corps finis"; ces titres ne
vont probablement pas changer.
> Voici quelques remarques :
[snip]
C'est corrigé (j'espère ;)).
Merci (particulièrement pour le coup du poly minimal)
Laurent
jp
Jan 3, 2012, 10:44:13 AM1/3/12
to
phi(15)/4.
>
> rem F_16 est constitué des 16 racines de X^16-X=
> X(X+1)(X^2+X+1)(X^4+X+1(X^4+X^3+1)(X^4+X^3+X^2+X+1]
>> En fait la définition avec le pgcd est valable dans un anneau
>> factoriel; je ne sais pas (mais je vais vérifier) si F_p est un anneau
>> factoriel. Si ce n'est pas le cas, alors ça explique au moins pourquoi
>> les deux définitions ne sont pas équivalentes.
>> Mais ça n'expliquerait pas comment on peut vérifier si un polynôme
>> donné est primitif au sens où dans le quotient, la classe de X est
>> d'ordre p^n-1.
> ca , je ne sais pas si ca court les rues...
> (Escofier dans son chapitre sur les corps finis ne l'évoque pas , mais
> bon c'est pas le seul ouvrage sur la question)
>> Bonne journée
>> Laurent
>
F_16 est étudié par Escofier dans les exercices XIV.9 et suivants.
Les polynômes irréductibles de degrés n, générateurs de F_q, (p premier
et q=p^n), sont les facteurs dans F_p[X] du polynôme cyclotomique
Phi_{q-1} et leur nombre est phi(q-1)/n.
Cordialement
--
jp
0 new messages