Division euclidienne dans F2

[invitee75a2d43]

Bonjour, j´étudie les codes correcteurs et dans ce contexte (code binaire de Hamming de longueur 7) il est écrit dans mon cours:

"Le polynôme générateur g = 1 + X + X^3

et

g divise X^7 - 1 puisque X^7 - 1 = ( 1 + X + X^3)(1 + X + X^2 + X^4)"

C´est là que je m´aperçois qu´une division euclidienne dans F2 n´est pas claire dans ma tête. J´ai essayé la chose suivante:

J´ai fait la division euclidienne "classique", c´est à dire à coefficients dans Z de X^7 - 1 par g, et j´ai obtenu:

X^7 - 1 = (X^3 + X + 1)(X^4 - X^2 - X - 1)

Et dans le deuxième facteur de ma division, j´ai tout simplement remplacé les - par des +, vu que dans F2 -1 = +1. Ainsi j´obtiens le même résultat que dans mon cours.

Mais est-ce la bonne méthode? Y-a-t-il une méthode plus rationnelle ou plus directe?

merci d´avance

Christophe
-----

[invite8b04eba7]

Mais est-ce la bonne méthode? Y-a-t-il une méthode plus rationnelle ou plus directe?

Comment calcules-tu dans F₂ ? Simplement en calculant dans Z puis en effectuant les modulo 2. Pour la division euclidienne, c'est pareil : tu fais tout dans Z puis tu passes au modulo 2 (tu peux meme le faire a chaque etape). Ca te donne le bon resultat a cause de l'unicite de cette division : une relation A = BQ + R avec deg(R) < deg(B) reste de la meme forme modulo 2.

[invitee75a2d43]

Super merci, c´est exactement la confirmation dont j´avais besoin.

Mais dans ce (presque) même chapitre, j´ai une autre question: Il s´agit cette fois d´opérations dans des corps finis Fp. Si p est premier, c´est simple, il suffit comme tu l´expliques de calculer dans Z (addition ou multiplication, peu importe) puis de faire modulo p.

Par contre sur Fn, n n´était pas premier, je ne sais pas comment m´y prendre. Pour être plus concret, j´ai trouvé un sîte d´exercices d´arithmétique, où il s´agit, entre autre, d´opérations sur F4. Naivement j´ai essayé de faire les calculs exactement comme si 4 était premier, et logiquement, j´ai tout faux...

Voilà le sîte:

http://wims.auto.u-psud.fr/wims/wims...bra%2Foefff.fr
OEF corps finis

Comment faut-il s´y prendre?

merci d´avance

[invité576543]

Attention, ça ne marche que dans certains cas! On peut très bien avoir un produit dans P(F2) qui ne correspond à rien pour les polynômes sur Z.

Par exemple X²+1 est divisible par X+1 dans P(F2), et la méthode consistant à travailler dans Z ne risque pas de donner la bonne division!

Pour faire une division euclidienne entre polynômes de F2, faut faire comme pour des polynomes sur Z, mais en faisant les additions et soustractions dans Z/2Z, à chaque opération élémentaire.

Cordialement,

[A voir en vidéo sur Futura]

[invité576543]

Super merci, c´est exactement la confirmation dont j´avais besoin.

Mais dans ce (presque) même chapitre, j´ai une autre question: Il s´agit cette fois d´opérations dans des corps finis Fp. Si p est premier, c´est simple, il suffit comme tu l´expliques de calculer dans Z (addition ou multiplication, peu importe) puis de faire modulo p.

Par contre sur Fn, n n´était pas premier, je ne sais pas comment m´y prendre. Pour être plus concret, j´ai trouvé un sîte d´exercices d´arithmétique, où il s´agit, entre autre, d´opérations sur F4. Naivement j´ai essayé de faire les calculs exactement comme si 4 était premier, et logiquement, j´ai tout faux...

Voilà le sîte:

http://wims.auto.u-psud.fr/wims/wims...bra%2Foefff.fr
OEF corps finis

Comment faut-il s´y prendre?

merci d´avance

PEux-tu préciser et présenter un exemple?

Les calculs dans Z/nZ se font de la même manière pour n premier ou pas, ce qui change est le fait que certains nombres non nuls n'ont pas d'inverse, et que ab=0 n'implique pas que a=0 ou b=0.

Cordialement,

[invite9c9b9968]

Pour les corps fini F_p avec p non premier, on peut peut-être se ramener à un corps isomorphe particulier dans lequel effectuer l'opération non ?

Bon ok calculer dans un corps de rupture de polynôme, ce n'est pas folichon

[invitee75a2d43]

Ben oui, justement, c´est ça le problème dans cette série d´exos: Ils parlent de F4, donc du corps à 4 éléments {0,1,2,3}, mais justement il ne s´agit pas de Z/4Z vu que Z/4Z n´est pas un corps. Donc comment faire des opérations dans F4, vu que ce sont exactement les mêmes éléments, mais pas les mêmes opérations.

D´une façon générale, quand on parle de Fn, il s´agit du corps à n éléments 0 à (n-1). Donc si n est premier, Z/nZ étant alors un corps, on a Fn = Z/nZ. Mais si n n´est pas premier, alors Z/nZ n´est pas un corps, donc Fn <> Z/nZ. Du moins c´est ce que je crois avoir compris. Quelqu´un peut-il me le confirmer?

[invite9c9b9968]

Tu as raison, d'ailleurs une discussion récente citait des exemples de corps à 4 éléments (des corps de rupture, comme je te le disais).

[invitee75a2d43]

Donc euh... personne sait faire ces exos dans F4 dans ce sîte?

[invite8b04eba7]

Attention, ça ne marche que dans certains cas! On peut très bien avoir un produit dans P(F2) qui ne correspond à rien pour les polynômes sur Z.

On est d'accord, mais ça n'empeche pas la division euclidienne de marcher (le reste dans Z[X] peut etre nul dans Z/2Z[X]).

[invite8b04eba7]

Donc euh... personne sait faire ces exos dans F4 dans ce sîte?

Il suffit de comprendre ce qu'est F₄ : une division euclidienne ça ne requiert que des additions, des multiplications et peut-être une division.

[invitee75a2d43]

Bon ben entretemps j´ai trouvé une réponse (pragmatique, car sans explication) à ma question au sujet de F4: un texte dans Internet, avec une table de multiplication et une d´addition dans F4:


http://www.math.u-bordeaux.fr/~lasjauni/page_fr_8.htm
Page 8 sur 10

Par contre je ne m´explique toujours pas comment ils en arrivent à ce résultat.

[invite8b04eba7]

Salut !

Il me semble t'avoir déjà répondu à cette question : le groupe multiplicatif de F4 est cyclique de cardinal 3, engendré par un élément w. Si tu rajoutes 0 (qui annule tous les autres) tu obtiens ta loi de multiplication.

Pour la loi d'addition, le nombres 0 et 1 se comportent très bien entre eux. La seule relation non triviale est 1 + w +w^2 = 0 (ça n'est pas difficile de voir que 1+w est différent de 0,1 et w). Toutes les autres se déduisent de celle là et du fait que le corps est de caractéristique 2.