Inscription / Connexion Nouveau Sujet

1 2 3 +


Posté par
infophile
re : Code de Reed Salomon 09-06-09 à 16:09

Ohoh je viens de comprendre un truc qui m'avait complètement échappé en vous lisant, dites moi si je me trompe :

Dans la définition d'un corps de rupture de P sur K, on dit que c'est une extension L de K sur laquelle P admet une racine a ET telle que a engendre L. Ici quand on dit que a engendre L ça se traduit comment mathématiquement ? C'est ce que ayoub qualifié de "primitif au sens corpusculaire" ?

J'en suis venu à me poser cette question quand j'ai remarqué ceci :

- On montre que (1,x,x²,...,x^(n-1)) est une base de K=Fp[X]/(P) où P est seulement irréductible et x la classe de X dans K.
=> donc tout élément de K s'exprime comme une combinaison linéaire des x^i, c'est pour cela qu'on les représente par des polynômes en x.
- Et toujours dans ce cas j'ai vu dans le livre d'annette qu'il arrivait que la classe x de X n'engendrait pas tout K* (par exemple dans K=F3[X]/(X²+1)), donc qu'il y a des éléments qui ne font pas des puissances de x.
- Tandis que lorsque P est primitif (et on a une caractérisation) là ça marche.
=> ici ça dit que tout élément est une puissance de x.

Donc en fait le mot "engendre" est relatif à la structure dont on parle.

Right ?

Ca devient vraiment intéressant quand ça commence à rentrer

Posté par
infophile
re : Code de Reed Salomon 09-06-09 à 16:23

au passage Annette, il n'y aurait pas une petite erreur à la page 150 dans la définition 4.2 ? Je pense que c'est plutôt K et pas L.

Posté par
1 Schumi 1
re : Code de Reed Salomon 09-06-09 à 18:01

Donc en fait le mot "engendre" est relatif à la structure dont on parle. >> Oui, bien sûr. C'est pour ça que j'ai souvent repris les hypothèses pour être sur qu'on parlait bien de la même chose. En général, l'ambiguité est enlevé par un contexte (si ya S_n pas loin, engendrer en terme de groupe est un epsilon plus cohérent que engendrer en terme de corps...).

Sinon, pour revenir à ta question... Je suppose que q=p^n?
L'élément x est générateur de K* ssi x est d'ordre q-1 >> Je pense pas que c'est ça qui pose problème, c'est un peu la définition.
ssi x est racine de phi_(q-1) >> Etre racine de phi_(q-1) c'est être une racine primitive q-1 ème de l'unité, ie être d'ordre q-1...
Le reste de la phrase, c'est la même justification.

Le mot important c'est "racine primitive [...]".

Posté par
infophile
re : Code de Reed Salomon 09-06-09 à 18:14

Mais comment tu traduis mathématiquement "engendré en terme de corps" ?

"ssi x est racine de phi_(q-1) >> Etre racine de phi_(q-1) c'est être une racine primitive q-1 ème de l'unité, ie être d'ordre q-1..."

Oui le sens <= OK, mais je ne vois pas pourquoi si x est d'ordre q-1 alors x est racine de phi_(q-1)

PS : oui q=p^n.

Merci

Posté par
1 Schumi 1
re : Code de Reed Salomon 09-06-09 à 18:26

Mais comment tu traduis mathématiquement "engendré en terme de corps" ? >> Le sous-corps engendré par "truc" est truc'...

mais je ne vois pas pourquoi si x est d'ordre q-1 alors x est racine de phi_(q-1) >> Euh, c'est quoi ta définition de phi_(q-1)...?

Posté par
infophile
re : Code de Reed Salomon 09-06-09 à 19:18

"Le sous-corps engendré par "truc" est truc'..."

Euh ça m'éclaire pas trop pour le coup ^^

Dans le cas d'un groupe cyclique c'est engendré par x donc G = {1,x,x²,... }, pour un ev c'est des combinaisons linéaires, et pour un corps qu'est-ce qui engendre quoi?

phi(q-1)(X) = prod(X-a) avec a les racines primitives q-1 ième de l'unité.

Mais on a X^(q-1)-1 = phi(q-1) * Prod(d|q-1 et # q-1) phi_d

Donc si x est d'ordre q-1 il est racine soit de phi(q-1) soit du produit non ?

Posté par
1 Schumi 1
re : Code de Reed Salomon 09-06-09 à 20:47

Euh ça m'éclaire pas trop pour le coup ^^ >> Ok, je reprends.

On prend k un corps et x dans k.
On dit que x engendre k lorsque le plus petit sous-corps de k qui contient x, c'est k.
Pour faire plus simple: x engendre k lorsque tout élément de k est une fraction rationnelle en x. Ladite fraction rationnelle étant à coefficients dans le sous-corps premier de k, oeuf course.

Donc si x est d'ordre q-1 il est racine soit de phi(q-1) soit du produit non ? >> Ben c'est ta définition de l'ordre qui n'est pas bonne alors...
Soit G un groupe, x dans G. On considère {n€N*, x^n=e}.
Si ce truc est vide x est dit d'ordre infini. Sinon, l'ordre de x, c'est le plus petit élément de ce truc.
Donc non, il peut être que racine de q-1...

Posté par
infophile
re : Code de Reed Salomon 09-06-09 à 21:46

Ah oui j'suis bête..

merci ayoub !

Posté par
1 Schumi 1
re : Code de Reed Salomon 09-06-09 à 21:53

Pas de quoi.

Posté par
infophile
re : Code de Reed Salomon 09-06-09 à 21:55

Le sens <= pour être sûr que je ne raconte pas de bétises :

si x est racine de phi_(q-1) c'est une racine primitive q-1 ième de l'unité, et comme les autres racines de phi_d avec d|q-1 strictement, ne sont pas primitives, c'est que x n'est pas racines de phi_d, donc elle annule pas X^k-1 avec k < q-1. Et donc q-1 c'est bien l'ordre de x.

Posté par
1 Schumi 1
re : Code de Reed Salomon 09-06-09 à 22:09

si x est racine de phi_(q-1) c'est une racine primitive q-1 ième de l'unité, et comme les autres racines de phi_d avec d|q-1 strictement, ne sont pas primitives, c'est que x n'est pas racines de phi_d, donc elle annule pas X^k-1 avec k < q-1. Et donc q-1 c'est bien l'ordre de x. >> Juste mais tu compliques un peu j'trouve. Vu la définition de "être d'ordre q-1" rappelée ci-dessus, "être d'ordre q-1" ou "être racine primitive q-1ème de l'unité" c'est évidemment dire deux fois la même chose, t'es pas d'accord?

Posté par
infophile
re : Code de Reed Salomon 11-06-09 à 17:25

J'aimerais revenir sur un point Ayoub.

Citation :
Je vois pas ce que tu ne comprends pas quand il faut démontrer que Fp[X]/(P) et Fp(x) sont isomorphes... Reviens à la définition, si t'es pas entièrement convaincu que ça peut pas être faux ce truc-là.

Tu prends comme définition:

"Par définition un corps de rupture de P sur Fp est une extension K' de Fp sur lequel il existe x' dans K' tel que P(x')=0 et K'=Fp(x')."

Ben cool, pour Fp[X]/(P), c'est clairement engendré par la classe de l'indéterminée X et pour l'autre c'est engendré par la racine x. Donc ben voilà, tu l'as ton isomorphisme...


Je vais te détailler l'avancement des choses comme je les ais comprises, tu me diras si ça te parait correct.

* Fp[X]/(P) est un corps de rupture de P irréductible de degré n

=> Pour démontrer ceci j'ai dit que la classe a de X annule P, ET que (1,a,a²,...a^(n-1)) est une base de Fp[X]/(P) sur Fp, donc en ce sens la classe de X , ou plutôt la famille (1,a,a²,...,a^(n-1)) "engendre" l'espace vectoriel Fp[X]/(P). Mais là je ne pense pas que ça soit la bonne justification, il faut que a engendre le corps Fp[X]/(P) c'est-à-dire que ça soit le plus petit corps contenant Fp et a non ? Si oui comment ?

* Deux corps de rupture sont isomorphes

=> L=K[X]/(P) est un corps de rupture de P sur K. Soit L' un autre corps de rupture de P sur K, et a' une racine de P dans L' tel que L' = K(a). L'application qui à un polynôme Q € K[X] associe Q(a') dans L' est surjective de noyau (P), donc d'après le théorème d'isomorphisme L' ~ K[X]/(P) = L.

* la classe de X engendre (Fp[X]/(P))* où P est le polynôme minimal du générateur x de K* (un corps fini quelconque)

=> Fp(x) est un sous-corps de K car K contient Fp et x, mais comme x engendre K* on a Fp(x) = K (ou K* ?). Fp(x) est un corps de rupture, Fp[X]/(P) aussi donc ils sont isomorphes. Donc K est isomorphe à Fp[X]/(P). Et comme x engendre K* alors la classe de X qui est une autre racine de P engendre (en terme de groupe multiplicatif) (Fp[X]/(P))* par isomorphisme. Je suis pas très sûr de moi là...

Donc en fait la seule chose qu'il me reste à justifier proprement c'est que la classe de X engendre (au sens de corps) Fp[X]/(P).

Merci beaucoup, et désolé d'insister mais je veux remettre les choses en ordre

Posté par
apaugam
re : Code de Reed Salomon 12-06-09 à 09:31

je reprends apres quelques jours de vacances
j'ai regardé le document annexe 2 construction des corps finis et il y manque une hypothèse essentielle pour les racines de \Phi_n elles ne sont racines primitives nieme de l'unite que lorsque n est premier a la caracteristique
aussi il vaut mieux reprendre la source c'est a dire Demazure

le fait qu'une racine de P soit racine primitive est vrai grâce au fait que n est premier à p

le fait que ksi soit racine de X^{p^r}-X ne dit pas pourquoi il engendre toutes les racines de ce polynome. On ne sait pas a priori qu'elles sont toutes dans ce corps L
il faut dire ds le paragraphe precedent que r divise s et alors un corps à p^r elements, ensemble des racines de ce polynome est contenu dans le corps L à p^s elements

Ce que tu ne comprend pas en gras vient tout simplement de la definition des polynomes cyclotomiques page 175 de mon livre c'est le polynome qui a pour racine les racines primitives nieme de l'unité ds le corps de decomposition de X^n-1 sur Z/pZ
mais attention pour que tout cela marche il faut n premier à la caracteristique voir au bas de la page 175 la partie grisée

Posté par
apaugam
re : Code de Reed Salomon 12-06-09 à 12:54

C'est tout simplement par définition de \Phi_{q-1} regarde la definition 5.13 page 175

par contre le papier Annexe II construction des corps finis est tres incomplet
il oublie de dire que n doit etre premier à p pour que les racines de \Phi_{n} soient primitives. C'est bien le cas ici car n=p^k-1 pour le cas qui nous interesse mais il ne l'ecrit pas dans sa proposition preliminaire. C'est une faute classique.
il vaut mieux retourner à la source Demazure ou à mon bouquin relis le grisé au bas de la page 175 et meme tout ce passage de 174 à 180

plus loin dans la demonstration il vaut mieux remarquer que r divise s ce qui permet de dire que toutes les racines de X^{p^r}-X sont dans L car L contient alors un sous corps de cardinal p^r (encore que, dans mon livre je le demontre apres)

Tu peux aussi utiliser ma proposition 5.16

Posté par
apaugam
re : Code de Reed Salomon 12-06-09 à 12:57

milles excuses, jai ecrit deux fois la meme chose car je regardais la page 1 de ce forum

Posté par
apaugam
re : Code de Reed Salomon 13-06-09 à 02:59

Citation :
au passage Annette, il n'y aurait pas une petite erreur à la page 150 dans la définition 4.2 ? Je pense que c'est plutôt K et pas L.

Si !
Merci bien, j'en prend note
Malgré les nombreuses relectures il reste toujours des erreurs

Posté par
apaugam
re : Code de Reed Salomon 13-06-09 à 03:21

Citation :
Pour démontrer ceci j'ai dit que la classe a de X annule P, ET que (1,a,a²,...a^(n-1)) est une base de Fp[X]/(P) sur Fp, donc en ce sens la classe de X , ou plutôt la famille (1,a,a²,...,a^(n-1)) "engendre" l'espace vectoriel Fp[X]/(P). Mais là je ne pense pas que ça soit la bonne justification, il faut que a engendre le corps Fp[X]/(P) c'est-à-dire que ça soit le plus petit corps contenant Fp et a non ? Si oui comment ?

effectivement il y a là un "petit miracle"
tu as raison de dire qu'a priori on obtient plutôt \mathbb F_p[a] mais comme ce \mathbb F_p[a] est un corps car on a quotienté par un polynôme irréductible les expressions polynomiales non nulles sont inversibles.
On sait même calculer l'inverse de Q(a) polynôme en a non nul, c'est-à-dire avec Q non divisible par P donc premier avec P (toujours car P est irréductible).
il suffit avec l'algorithme d'Euclide d'obtenir Bezout dans \mathbb F_p[X] : U(X)P(X)+V(X)Q(X)=1
Pour X=a on obtient l'inverse de Q(a) : c'est V(a).
les fractions \frac{Q(a)}{D(a)}
 \\ peuvent donc s'écrire comme des polynômes en a et ainsi \mathbb F_p[a]=\mathbb F_p(a).
Ce qui fait marcher la chose c'est le fait que a soit algébrique.
Par exemple, par contre, \mathbb Q[\pi]\neq\mathbb Q(\pi)

Posté par
infophile
re : Code de Reed Salomon 15-06-09 à 14:57

Bonjour Annette,

Merci beaucoup de prendre de votre temps pour expliquer tout ça un simple taupin ^^

J'ai lu la partie grisée, on a bien X^m-1 = (X^r-1)^p par Frobenius (avec m = pr).

Donc si x^m-1 = 0 c'est que x^r-1 = 0 donc x est d'ordre au plus r, OK.

Mais pourquoi \phi_{m,k} vaut 1 ?

Autre petite question :

Quand je considère le morphisme f de Fp[X] dans K qui à Q associe Q(x) (où x est racine de P dans Fp[X]/(P)).

Pour appliquer le théorème d'isomorphisme j'ai besoin que Im f = K, mais pourquoi est-ce le cas ?

Merci

Posté par
infophile
re : Code de Reed Salomon 15-06-09 à 15:06

Une dernière chose :

* Vous disiez dans un précédent post que pour un polynôme primitif, si x engendre K*, par isomorphisme la classe de X engendre (Fp[X]/(P))*.

Si on veut expliciter un tel isomorphisme peut-on considérer l'application :

f : Fp[X]/(P) --> K(x)
       cl(Q)  --> Q(x)

qui est injective car on a quotienter par le noyau, et même bijective car même nombre d'éléments dans les deux ensembles.

Donc si on prend le polynôme Q(X)=X on a bien la classe de X qui s'envoie sur x.

Juste ?

Posté par
apaugam
re : Code de Reed Salomon 16-06-09 à 02:26

oui c'est juste

Posté par
apaugam
re : Code de Reed Salomon 16-06-09 à 02:40

Citation :
Merci beaucoup de prendre de votre temps pour expliquer tout ça un simple taupin ^^

J'ai lu la partie grisée, on a bien X^m-1 = (X^r-1)^p par Frobenius (avec m = pr).

Donc si x^m-1 = 0 c'est que x^r-1 = 0 donc x est d'ordre au plus r, OK.

Mais pourquoi \phi_{m,k} vaut 1 ?

C'est un plaisir pour moi de dépanner les gens qui s'interessent aux maths et particulièrement aux corps finis.

lorsque m=pr il n'y a aucune racine primitive mieme dans aucun corps de caracteristique p
le produit definissant \phi_{m,k} est donc le produit vide qui vaut 1 par convention.

d'autres ouvrages prennent comme definition de \phi_{m,k} la reduction de \phi_{m,Z} mod p.
dans ce cas ce polynome \phi_{m,k} n'a pas pour racine des racines primitives mieme
cela ne change pas grand chose au probleme.
Dans beaucoup d'ouvrages c'est ecrit en tout petit au debut du chapitre on suppose la caracteristique p premiere à m et souvent les gens n'y prete pas attention.

Posté par
infophile
re : Code de Reed Salomon 16-06-09 à 17:27

C'est très clair merci

Et pour mon post de 14:57 vous pouvez m'expliquer ?

Citation :
Autre petite question :

Quand je considère le morphisme f de Fp[X] dans K qui à Q associe Q(x) (où x est racine de P dans Fp[X]/(P)).

Pour appliquer le théorème d'isomorphisme j'ai besoin que Im f = K, mais pourquoi est-ce le cas ?

Posté par
apaugam
re : Code de Reed Salomon 17-06-09 à 07:23

c'est surjectif parce que tout élément de K est la classe d'un polynôme Q égal à f(Q)
car si l'on divise Q par P formellement
Q=PQ1+R
en faisant X=x dans K on a
Q(x)=R(x)= classe de Q(X)=Q(classe de X) car la projection dans le quotient est un morphisme d'anneau

tout est-il clair maintenant ?

Posté par
infophile
re : Code de Reed Salomon 17-06-09 à 18:47

Merci pour tout annette

Posté par
infophile
re : Code de Reed Salomon 20-06-09 à 17:49

Bonjour

Et oui encore moi ^^

Il y a un tout petit truc que je ne comprends pas (le passage en gras) dans la démo pas 232 de Demazure :

Citation :
Soit C un code cyclique. Parmi tous les mots de C, choisissons en un qui ait le nombre maximum de zéros consécutifs à la fin, soit m = (a_0,...,a_(n-k),0,...,0), avec a_(n-k) # 0 et le polynôme g(X) associé. Quitte à multiplier par l'inverse de a_(n-k) on peut supposer a_(n-k)=1. Le mot m est unique car s'il en existait un autre m', la différence m-m' aurait au moins un 0 de plus à droite. Puisque le code est cyclique, les k-1 mots déduits par décalage (application s) appartiennent à C. Les k mots ainsi construits sont bien sur linéairement indépendants. Prouvons qu'ils engendrent C. Soit n un mot quelconque et n(X) le polynome correspond. Par division euclidienne dans Fq[X] : n(X) = (b_0+...+b_(k-1)X^(k-1))g(X)+r(X) où deg(r) < n-k. On a donc la relation n = (b_0m + b_1s(m)+...) + r.

Si m appartient à C, on voit par différence que r appartient à C (ça OK).

Mais cela implique r=0 puisqu'il a trop de zéros à droite.


Merci

Posté par
apaugam
re : Code de Reed Salomon 21-06-09 à 04:20

Cela m'est un peu difficile de répondre car je suis à Pékin et n'ai pas Demazure sous la main
j'emet une hypothèse sur l'interprétation
peut être les mots du code étant des polynômes le reste de la division s'il n'est pas nul étant de degré plus petit il aurait plus de zéro à droite ( termes de plus ht degré nuls)
mais c'est une hypothèse de lecture car je n'ai pas en tête le contexte

Posté par
infophile
re : Code de Reed Salomon 21-06-09 à 18:38

J'avais fini par trouver merci !

Sinon pour être sûr de bien comprendre ici :

Soit k un corps fini à q éléments et pgcd(n,q)=1. Soit K contenant k et n racines n-ièmes de l'unité, donc une racine primitive aussi. Donc K est obtenu par adjonction à k d'une racine primitive a. Le polynôme minimal P de a est un facteur irréductible de \phi_n, donc de degré r (r étant la classe de q dans (Z/nZ)*), il en résulte que le corps K à q^r éléments.

Le premier passage en gras : Est-ce du à l'équivalence "il y a exactement n racines n-ièmes dans A <=> il existe au moins une racine primitive n-ième dans A" ?

Le deuxième : je dirais que k(a) s'identifie à k[X]/(P) qui a q^r éléments.

C'est ça ?

Posté par
infophile
re : Code de Reed Salomon 21-06-09 à 21:10

Ah et un truc que je ne comprends pas :

Soit g_{\sum}(X)=\Bigprod_{i\in\sum}(X-\alpha^i) est primitive et \sum une partie de Z/nZ.

Pourquoi si \sum est stable par q on a g(X^q)=(g(X))^q ?

Merci beaucoup

Posté par
apaugam
re : Code de Reed Salomon 22-06-09 à 01:29

Donc K est obtenu par adjonction à k d'une racine primitive a.

c'est tout simplement parce que s'il y a une racine primitive c'est-à-dire si (n,q)=1 le corps contenant cette racine contient aussi toutes les racines de l'unité

il en résulte que le corps K à q^r éléments.

Le deuxième : je dirais que k(a) s'identifie à k[X]/(P) qui a q^r éléments.
Exact !

Posté par
apaugam
re : Code de Reed Salomon 22-06-09 à 01:42

Pour
Soit g_{\sum}(X)=\Bigprod_{i\in\sum}(X-\alpha^i) où  est primitive et \sum une partie de Z/nZ.

Pourquoi si \sum est stable par q on a g(X^q)=(g(X))^q ?

d'abord si x est racine d'un polynôme g a coef ds F_q comme frobenius est un morphisme de corps x^q est aussi racine
si g est irreductible sur F_q et x une racine de g ds une extension les autres racines sont obtenu en appliquant le morphisme de frobenius
autrement dit le groupe de Galois est engendré par Frobenius

si \sum est stable par q
g a des racines stables par frobenius ce sera donc un produit de polynôme irréductible sur F_q
et pour un polynôme sur F_q  on a g(X^q)=(g(X))^q toujours par Frobenius

Posté par
infophile
re : Code de Reed Salomon 22-06-09 à 11:48

Je pense avoir trouvé hier, je crois que ça rejoint ce que vous me dites :

j'ai dit que Sigma est stable par q donc pour tout i de Sigma, qi = i, donc (alpha^i)^q = (alpha)^(qi) = alpha^i.

(g(X))^q = (Prod (X-alpha^i))^q = Prod (X-alpha^i)^q = Prod (X^q-(alpha^i)^q) = Prod (X^q - alpha^i) = g(X^q).

C'est bien ça ?

Posté par
apaugam
re : Code de Reed Salomon 23-06-09 à 01:27

je n'ai pas le contexte dc je me trompe peut être mais je ne pense pas que \alpha soit un élément de F_q
et donc je pense que \alpha^q\neq 1
par contre le polynôme minimal de \alpha sur F_q a pour racine les images par Frobenius (élever à la puissance q) de \alpha
j'ai l'impression que cela correspond plutot à cette situation mais comme je n'ai pas Demazure ...

Pour le savoir regarde bien si \alpha est dans F_q(ds ce cas c'est toi qui pourrai avoir raison) ou dans une extension de F_q

Posté par
infophile
re : Code de Reed Salomon 29-06-09 à 11:37

Bonjour

Désolé pour le retard !

J'ai vu mon erreur c'est vous qui avez raison.

"d'abord si x est racine d'un polynôme g a coef ds F_q comme frobenius est un morphisme de corps x^q est aussi racine (OK)

si g est irreductible sur F_q et x une racine de g ds une extension les autres racines sont obtenu en appliquant le morphisme de frobenius" >> pourquoi ?

Et je ne vois pas en quoi ces remarques préalables servent pour la suite :

"si \sum est stable par q
g a des racines stables par frobenius ce sera donc un produit de polynôme irréductible sur F_q
et pour un polynôme sur F_q  on a g(X^q)=(g(X))^q toujours par Frobenius"

Par stabilité on sait que si x^i est racine de g alors (x^i)^q aussi. Mais je ne comprends pas ce "donc".

Parce qu'en fait je dois montrer que g(X^q) = (g(X))^q pour en déduire que g est à coefficients dans Fq.

Merci

Posté par
apaugam
re : Code de Reed Salomon 30-06-09 à 00:50

le "donc" vient du fait que pour un polynôme irréductible sur un corps fini, le groupe de Galois est engendré par Frobenius
cela signifie que l'on obtient toutes les racines à partir d'une racine en appliquant frobenius (voir JPE par exemple)
autrement dit si a est algebrique sur Fq et P son polynôme minimal on a
P(X)=produit des différents facteurs (X-F^ i(a))
un polynôme quelconque dont les racines sont stables par frobenius va se décomposer en facteurs irreductibles sur le corps de base
on prends une racine et les images par frobenius de cette racine on obtient un premier facteur le polynôme minimal de cette première racine puis on continue jusqu'à épuisement des racines avec une racine qui n'est pas racine de ce premier facteur on obtient un deuxième facteur etc...
  

Posté par
infophile
re : Code de Reed Salomon 30-06-09 à 19:13

Je n'ai pas vu les groupes de Galois, et ils ne figurent pas dans le Demazure donc je suppose qu'on peut s'en sortir sans.

Voici la démonstration que l'on trouve dans Demazure :

Citation :
Ecrivons pour simplifier g au lieu de g_{\sum}. Si g est à coefficients dans Fq, chaque coefficient de g est stable par élévation à la puissance q-ième. Puisque cette opération respecte aussi l'addition, on voit que g(X^q)=(g(X))^q; par conséquent, l'ensemble des racines de g est stable par passage à la puissance q-ième, ce qui signifie que \sum est stable par multiplication par q. Inversement si \sum est stable par multiplication par q, on vérifie aussitôt que g(X^q)=(g(X))^q et cela implique que les coefficients de g appartiennent à Fq.


Exercice 9.14 : Compléter les détails de cette démonstration.
Correction : Raisonner comme dans 8.2, en utilisant 8.3

Je vous écris ces propositions :

Proposition 8.2 - Soit K un corps. L'application x\to x^p est un automorphisme de K, compatible avec l'addition et la multiplication. La condition x^p=x\Leftright x\in F_p. Soit Q\in K[X], on a Q\in F_p[X]\Leftright Q(X^p)=(Q(X))^p.

Théorème 8.3 - Soit K un corps fini.
(a) Cardinal de la forme p^n.
(b) x^{p^n}=x pour tout x dans K, et dans K[X] on a : X^{p^n}-X=\prod_{a\in K}(X-a)
(c) K* est cyclique d'ordre p^n-1.
(d) Tout sous corps de K a p^r éléments où r|n.
(e) Pour tout r|n, il existe un unique sous corps à p^r éléments : l'ensemble des x dans K tels que x^{p^r}=x

J'ai donc essayé de compléter la démonstration, je n'ai pas eu de problème à priro pour le sens direct, mais pour l'autre sens je ne vois pas comment "aussitôt" on vérifie que Q(X^q)=(Q(X))^q, après sinon ça marche bien.

Code de Reed Salomon

Merci mille fois

Posté par
apaugam
re : Code de Reed Salomon 01-07-09 à 03:00

C'est plus facile de répondre avec un peu plus de contexte
Si g_{\sum}(X)=\Bigprod_{i\in\sum}(X-\alpha^i) où  \alpha est primitive et \sum une partie de Z/nZ stable par x par q on a g(X^q)=(g(X))^q.

(X-\alpha^i)^q=X^q-\alpha^{iq}
la multiplication par q définit une permutation de \sum
on retrouve donc dans g(X)^q tous les facteurs de g(X) permutés où, dans chaque facteur, X a été remplacé par X^q. C'est bien g(X^q).

j'espère que cette fois tu auras tous les éléments pour comprendre

pour quand ce mémoire doit-il être fini ?
ou peut-être travailles tu juste pour le plaisir ?

Posté par
infophile
re : Code de Reed Salomon 01-07-09 à 11:35

Ah mais oui tout simplement ! Je n'ai pas pensé à revenir à la forme factorisée de g

Merci beaucoup

Citation :
pour quand ce mémoire doit-il être fini ?
ou peut-être travailles tu juste pour le plaisir ?


Pour le moment pour le plaisir, j'ai presque terminé ce "mémoire" sur les corps finis & codes correcteurs. En fait ça me permet surtout de bien assimiler toutes ces notions en les rédigeant de manière ordonnée et détaillée (car dans le Demazure certaines choses sont admises au niveau master et méritent d'être démontrées pour un taupin lambda).

Je viens de voir le codage/décodage des codes BCH, et je compte dans les prochains jours en programmer un en Maple (ma référence c'est le fichier que vous m'aviez conseillé sur le site de Rennes). Dans les grandes lignes j'ai compris les procédures car j'ai assimilé le côté théorique, mais il me reste maintenant à voir quelques commandes que je n'ai jamais utilisé, comme "Normal(a) mod p" etc. Donc j'aurai peut-être quelques questions d'ordre pratique à vous poser pour la suite.

Ensuite tout ceci pourra faire l'objet de mon TIPE pour l'an prochain (je fais 5/2), en espérant un jour pouvoir le présenter aux ENS... (l'espoir fait vivre!).

En tout cas c'était très gentil de m'aider, j'apprécie bon séjour à Pékin !

Kévin.

Posté par
1 Schumi 1
re : Code de Reed Salomon 01-07-09 à 13:01

Ensuite tout ceci pourra faire l'objet de mon TIPE pour l'an prochain (je fais 5/2), en espérant un jour pouvoir le présenter aux ENS... (l'espoir fait vivre!). >> Pour venir juste de le passer, je peux t'assurer que 10 min, ça passe bien plus vite que prévu et qu'on a vraiment rien le temps de dire. Aux ens c'est un autre problème... d'ailleurs c'est plus un problème aux ens avec le principe du "rapport". Tkt pour l'an prochain, en travaillant tu l'auras sans problème ton ens. Je te fais confiance pour ça.

Posté par
infophile
re : Code de Reed Salomon 01-07-09 à 15:23

Salut Ayoub

Oui 10 minutes et un rapport d'au plus 5 pages ça fait short (surtout que tout rédigé avec les démos j'ai 50 pages là ^^). Donc ce que j'ai fait ça me sert plus de support qu'autre chose. Au final je pense que j'expliquerais seulement la méthode pour construire le code BCH en joignant la feuille Maple. Après si l'examinateur veut plus de détails sur le côté théorique je pourrais éventuellement en apporter.

Comment ça s'est passé pour toi ? Ca se déroule comment ?

Et tes autres oraux ça a été ? (j'ai eu un aperçu sur prepa.org)

Je suis assez pressé de voir mes notes histoire de voir si j'ai une chance pour l'an prochain (cad si je suis excessivement en dessous de la barre d'admissibilité ou non).

Bonnes vacances !

Posté par
1 Schumi 1
re : Code de Reed Salomon 01-07-09 à 15:33

Centrale s'est relativement bien passé (à part à physique I où un 5 ne m'étonnerait pas trop...)
ENS, ben, j'suis en plein dedans donc j'attends de finir ça pour savoir si stresser pendant les 10 jours restants est justifié ou pas.
Pour l'histoire des notes, te fais pas trop de soucis pour ça: c'est vraiment révélateur de rien particulièrement aux ens. D'une part parce qu'un 5/2 qui n'avait eu aucune ens l'an dernier s'est retrouvé admissible à ulm dans le groupe I (tu sais, le truc où ya que 32 admissibles là...^^) et que pas mal d'autre qui était admissible nulle part l'an dernier ont eu au moins cachan voire même lyon cette année. Il y a bien une marge de progression possible pour les ens et elle est de taille.
D'autre part parce que les ens, c'est noté un peu n'importe comment: mon prof de physique m'avait demandé avant les résultats si je pensais pouvoir être admissible Ulm. Je lui ai dit "Ulm ça va être chaud, lyon par contre ça devrait passer". Il m'a demandé si j'avais réussi math I, je lui ai dit que ça c'était pas trop mal passé. Il m'a répondu "dans ce cas, ya pas de problème. S'ils ont envie de vous voir aux oraux, vous inquiétez pas, ils feront en sorte que vous soyez aux oraux". Ben ça a pas manqué... ^^

Entraîne toi avec des sujets ens pendant l'année, question de connaître ce que les ens considérent comme "classique et inadmissible que ça ne soit pas connu" (beaucoup de trucs quoi ) ainsi que les questions un peu plus chaudes dont il faut absoluement en faire si on veut espérer que ça passe. T'as un an, t'as vraiment le temps de t'y préparer sérieusement.



Posté par
infophile
re : Code de Reed Salomon 01-07-09 à 15:49

Ok ben je te demanderai conseils

Du coup je pense que je vais zappé la physique et me concentrer sur les maths. De toute façon je veux faire prof donc après tout la physique ne va pas me servir des masses.

Bonne chance pour tes oraux !

Posté par
monrow Posteur d'énigmes
re : Code de Reed Salomon 01-07-09 à 16:00

Bonne chance à vous deux !

Kévin, je suis comme toi cette année ... Je me suis retrouvé avec les CCP et point final Bon courage pour l'année prochaine, je sais bien que tu auras tes ens l'année prochaine ... Mais travaille un peu au mois d'août quand même

Ayoub, torche nous cet oral ! (et puis moi j'hésite pas à te déranger à chaque fois avec mes questions: genre "comment ça passe? Ah 10 minutes c'est suffisa
nt? ..." ^^ , fais de même Kévin ... )

Posté par
infophile
re : Code de Reed Salomon 01-07-09 à 16:19

Salut momo !

Tu fais 5/2 aussi alors ?

Oui je vais profiter que ma copine part en vacances pour travailler un peu

J'espère que ça passera l'an prochain !

Posté par
monrow Posteur d'énigmes
re : Code de Reed Salomon 01-07-09 à 16:28


Citation :
Tu fais 5/2 aussi alors ?


C'est pas encore sur ... Si j'ai l'ENSIMAG (y a beaucoup de maths !!), je pense que je vais foncer, sinon je ferai surement une 5/2

Posté par
infophile
re : Code de Reed Salomon 01-07-09 à 16:33

C'est surtout axé informatique non ?

Mais c'est vrai qu'il paraît que c'est une bonne école

Posté par
monrow Posteur d'énigmes
re : Code de Reed Salomon 01-07-09 à 16:36

Oui c'est spécialisé en mathématiques et informatique !

Citation :
Mais c'est vrai qu'il paraît que c'est une bonne école


Bof, j'ai plus de souffle pour la prépa .. (la physique ne m'a pas laissé de chance ^^)

Posté par
infophile
re : Code de Reed Salomon 01-07-09 à 17:19

Est-ce que chez vous vous arrivez à enregistrer vos feuilles Maple ?

Car moi c'est une version crackée (chut! ) et ça ne fonctionne pas.

Posté par
monrow Posteur d'énigmes
re : Code de Reed Salomon 01-07-09 à 18:14

J'ai aussi une version crackée (non mais chut ) et ça fonctionne bien (j'ai la version 12 ...)

Posté par
infophile
re : Code de Reed Salomon 01-07-09 à 18:17

Tu as un lien où je peux le trouver ?

Posté par
infophile
re : Code de Reed Salomon 03-07-09 à 22:42

Annette,

Dans la feuille maple du site de l'université de Rennes, on construit le générateur du code comme ppcm des polynômes minimaux des \alpha^i que l'on cherche parmi la liste des facteurs irréductibles de X^n-1.

Mais alors du coup à quoi ça sert d'avoir travailler sur les classes cyclotomiques ? c'est pour les "petits" codes correcteurs ?

De même dans la feuille je ne vois nulle part apparaître l'utilité des tables de correspondances ?

Merci

1 2 3 +




Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1675 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !