Corps de Galois

Utilisation de Xcas

Modérateur : xcasadmin

Répondre
laboriefred
Messages : 13
Inscription : mer. oct. 11, 2017 7:39 pm

Corps de Galois

Message par laboriefred » jeu. oct. 12, 2017 8:02 am

Bonjour j'utilise la commande suivante pour créer un corps de Galois :
G:=GF(2,k^8+k^4+k^3+k^2+1)
Puis en tapant G(k^8) j'obtiens bien k^4+k^3+k^2+1
Mais j'aimerais évaluer ce résultat ainsi que tous les autres G(k^n) pour k=2.
J'ai essayé subst, mais cela ne fonctionne pas...
Avez vous une réponse svp à m'apporter ?
Merci.

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: Corps de Galois

Message par parisse » jeu. oct. 12, 2017 5:57 pm

En fait k est un generateur du corps, vous pouvez ecrire par exemple f:=k^8 sans mettre de G autour. Ensuite f[0] renvoie la caracteristique, f[1] le polynome minimal et f[3] le polynome correspondant a f (sous forme de la liste de ses coefficients), vous pouvez alors faire horner(f[3],2) pour l'evaluer en k=2.
Avec le G autour il faut ecrire f[3][0][3] pour acceder au polynome ce qui est lourd...

laboriefred
Messages : 13
Inscription : mer. oct. 11, 2017 7:39 pm

Re: Corps de Galois

Message par laboriefred » ven. oct. 13, 2017 10:37 am

Un grand merci , bien cordialement

laboriefred
Messages : 13
Inscription : mer. oct. 11, 2017 7:39 pm

Re: Corps de Galois

Message par laboriefred » ven. oct. 13, 2017 10:12 pm

Bonjour, maintenant je veux faire un division du polynôme L1 par L2 (dans le corps de Galois du dessus)
où horner(L2,2,a) donne x^5+62*x^4+111*x^3+15*x^2+48*x+228 et horner(L1,2,a) donne 142*x^7+164*x^6+186*x^5

L2 et L1 ont pour coef des nombres dans le corps de GAlois du dessus.
je demande la division de L1 par L2 en faisant rem(L1,L2,x) puis je l'évalue : horner(rem(L1,L2,x),2,a) modulo 301 est j obtiens
54 % 301+x*124 % 301+x^2*133 % 301+x^3*(-69) % 301+x^4*14 % 301
En fait la doc sur datamatrix me dit que le résultat est 114x^4 + 25 x^3 + 5 x^2 + 88 x + 102

Je dois faire une mauvaise manip , auriez vous une idée svp ?

Merci, bien cordialement

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: Corps de Galois

Message par parisse » sam. oct. 14, 2017 6:01 am

Que vient faire le % 301 la-dedans? J'ai l'impression que vous essayez de suivre un cours en ligne qui utilise des entiers pour representer les elements d'un corps fini, mais giac n'utilise pas des entiers, vouloir convertir de l'un a l'autre sans arret risque de vous embrouiller plus qu'autre chose.
Si vous voulez travailler avec des polynomes dans le corps G, vous pouvez utiliser soit des expressions symboliques, par exemple k^8*x^2+(k^3+k)*x+1%2, soit des polynomes-listes, poly1[k^8,k^3+k,1%2], ensuite vous pouvez utiliser les operations arithmetiques de base, quo, rem, ... Si vous utilisez des expressions symboliques pour stocker les polynomes, il faut executer normal apres +,-,*

laboriefred
Messages : 13
Inscription : mer. oct. 11, 2017 7:39 pm

Re: Corps de Galois

Message par laboriefred » sam. oct. 14, 2017 12:51 pm

parisse a écrit :Que vient faire le % 301 la-dedans? J'ai l'impression que vous essayez de suivre un cours en ligne qui utilise des entiers pour representer les elements d'un corps fini, mais giac n'utilise pas des entiers, vouloir convertir de l'un a l'autre sans arret risque de vous embrouiller plus qu'autre chose.
Si vous voulez travailler avec des polynomes dans le corps G, vous pouvez utiliser soit des expressions symboliques, par exemple k^8*x^2+(k^3+k)*x+1%2, soit des polynomes-listes, poly1[k^8,k^3+k,1%2], ensuite vous pouvez utiliser les operations arithmetiques de base, quo, rem, ... Si vous utilisez des expressions symboliques pour stocker les polynomes, il faut executer normal apres +,-,*
Bonjour, je n'essaye pas de suivre un cours en ligne, simplement j'essaye d'utiliser XCAS pour retrouver les codes correcteurs d'un datamatrix (codage reed solomon).
Pour le post j'utilise la notation décimale bien plus lisible que des poly en k , c'est pour cela que j'ai mentionné que je les obtenais en faisant horner(L1,2,k) où L1 est un poly dont justement les coef sont dans le corps de Galois du départ. De même pour L2
En effet après mure réflexion le %301 n'est peut être pas licite, mais quand j'évalue rem(L1,L2,x) par horner(rem(L1,L2,x),2,k) j'obtiens
-31289538*x^4-57608760*x^3-7419216*x^2-22995072*x-118583712 mais les coefs ne sont plus dans [0 , 256] en décimal.

Question : Xcas a t il un fonction qui permet de transformé un nombre décimal en écriture dans le corps de Galois ?
Bien cordialement
Pour information résultat de rem(L1,L2,x) :
-k^22*x^4-k^23*x^3-3*k^21*x^4-3*k^22*x^3-6*k^20*x^4-5*k^21*x^3-10*k^19*x^4-8*k^20*x^3-14*k^18*x^4-12*k^19*x^3-k^20*x^2-17*k^17*x^4-16*k^18*x^3-3*k^19*x^2-23*k^16*x^4-23*k^17*x^3-6*k^18*x^2-27*k^15*x^4-30*k^16*x^3-10*k^17*x^2-k^17*o*x-30*k^14*x^4-33*k^15*x^3-14*k^16*x^2-k^17*w-2*k^16*o*x-32*k^13*x^4-37*k^14*x^3-17*k^15*x^2-2*k^16*w-3*k^15*o*x-33*k^12*x^4-39*k^13*x^3-22*k^14*x^2-3*k^15*w-4*k^14*o*x-28*k^11*x^4-39*k^12*x^3-26*k^13*x^2-4*k^14*w+k^12*o*x^2-5*k^13*o*x-25*k^10*x^4-37*k^11*x^3-30*k^12*x^2-5*k^13*w+k^11*o*x^2-5*k^12*o*x+k^12*w*x-14*k^9*x^4-32*k^10*x^3-33*k^11*x^2-5*k^12*w+k^10*o*x^2-8*k^11*o*x+k^11*w*x-6*k^8*x^4-21*k^9*x^3-33*k^10*x^2-8*k^11*w+k^9*o*x^2-8*k^10*o*x+k^10*w*x+3*k^7*x^4-13*k^8*x^3-30*k^9*x^2-8*k^10*w-k^7*o*x^3+2*k^8*o*x^2-9*k^9*o*x+k^9*w*x+9*k^6*x^4-6*k^7*x^3-25*k^8*x^2-9*k^9*w+k^7*o*x^2-k^7*w*x^2-8*k^8*o*x+2*k^8*w*x+9*k^5*x^4+3*k^6*x^3-17*k^7*x^2-8*k^8*w+3*k^6*o*x^2-8*k^7*o*x+k^7*w*x+6*k^4*x^4+7*k^5*x^3-7*k^6*x^2-8*k^7*w+2*k^5*o*x^2-5*k^6*o*x+3*k^6*w*x+k^3*x^4+9*k^4*x^3-5*k^6*w-k^3*o*x^3+3*k^4*o*x^2-4*k^5*o*x+2*k^5*w*x-2*k^2*x^4+6*k^3*x^3+4*k^4*x^2-4*k^5*w-k^2*o*x^3+2*k^3*o*x^2-k^3*w*x^2+3*k^4*w*x-k*x^4+2*k^2*x^3+4*k^3*x^2-k*o*x^3-k^2*w*x^2+2*k^3*o*x+2*k^3*w*x+2*k^2*x^2+2*k^3*w-k*w*x^2+2*k^2*o*x+2*k^2*w

laboriefred
Messages : 13
Inscription : mer. oct. 11, 2017 7:39 pm

Re: Corps de Galois

Message par laboriefred » sam. oct. 14, 2017 1:08 pm

Bonjour , je viens de m apercevoir d'une erreur de frappe dans la commande G:=GF(2,k^8+k^4+k^3+k^2+1)
en fait cela doit être G:=GF(2,k^8+k^5+k^3+k^2+1) d 'où le %301 était illicite.
Je reprends tous les calculs ...

frederic han
Messages : 1137
Inscription : dim. mai 20, 2007 7:09 am
Localisation : Paris
Contact :

Re: Corps de Galois

Message par frederic han » sam. oct. 14, 2017 3:01 pm

Bonjour,
ce que veut dire bernard est que votre corps G a beau avoir 256 elements, le fait de les noter par des entiers entre 0 et 255 n'est pas compatible avec l'addition ni la multiplication des entiers, il ne faut donc pas esperer trouver un % quelque chose qui vous permettre de realiser un corps a 256 elements.

Si cette bijection vous est utile pour faire un dessin il faut la faire apres tous les calculs:

ici je crée une fonction nG pour aller de [0,256[ vers G et une fonction Gn pour la bijection reciproque.
Ensuite la divition doit absolument etre faite dans G, et puis je peux la convertir sous la forme que vous vouliez.
GF256.png
GF256.png (89.27 Kio) Consulté 14422 fois
(edit: j'ai eu quelques soucis avec la saisie d'ecran, voici la bonne)

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: Corps de Galois

Message par parisse » sam. oct. 14, 2017 3:44 pm

le seul % qui me semble raisonnable si on travaille sur un corps a 256 elements, c'est 2 la caracteristique du corps. On peut bien sur representer les elements d'un corps fini a 256 elements par des entiers entre 0 et 255 (de deux facons en fait, en representation additive et multiplicative), mais l'arithmetique n'est pas +/-/* modulo quelque chose, je prefere donc afficher les elements du corps fini comme des polynomes, ainsi Xcas sait comment faire toutes les operations correctement.
Sinon, a propos des codes de Reed-Solomon, je vous signale qu'il y a une session dans le menu Aide>Exemple>crypto implementant le decodage.

laboriefred
Messages : 13
Inscription : mer. oct. 11, 2017 7:39 pm

Re: Corps de Galois

Message par laboriefred » sam. oct. 14, 2017 4:03 pm

Merci pour votre réponse, j'ai compris que je faisais une mauvaise manip, et en écrivant les coefs sous la forme par exemple l:=G(a^185) les calculs se font correctement et j'obtiens pour f:=rem(l*x^7+p*x^6+q*x^5 , x^5+h*x^4+n*x^3+m*x^2+o*x+w ,x) :

G(a^6+a^5+a^2+a)+x*G(a^6+a^4+a^3)+x^2*G(a^2+1)+x^3*G(a^4+a^3+1)+x^4*G(a^6+a^5+a^4+a)

Donc j'évalue maintenant le coef de x^4 en faisant :horner(f[2][1][3],2,a) j'obtiens 114 :)

mais par le même type de commande horner(f[1][1][3],2,a) ou horner(f[6][1][3],2,a) je n'arrive pas à évaluer le coef constant G(a^6+a^5+a^2+a).

c'est normal ? Comment puis je faire ?
Pièces jointes
Capture.PNG
Capture de mes commandes
Capture.PNG (18.42 Kio) Consulté 14419 fois

laboriefred
Messages : 13
Inscription : mer. oct. 11, 2017 7:39 pm

Re: Corps de Galois

Message par laboriefred » sam. oct. 14, 2017 4:19 pm

Merci, je vais y regarder.

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: Corps de Galois

Message par parisse » sam. oct. 14, 2017 6:31 pm

Plutot qu'une capture d'ecran, mettez le texte de vos commandes dans un champ Code, ca permet de reproduire facilement. Comme indique sur un autre topic, je vais modifier la commande coeff, on pourra lui passer un element d'un corps de Galois, et il renverra le polynome correspondant, ou bien coeff(element,indice) le coefficient.

laboriefred
Messages : 13
Inscription : mer. oct. 11, 2017 7:39 pm

Re: Corps de Galois

Message par laboriefred » dim. oct. 15, 2017 6:36 am

Bonjour, merci pour l'information.
Les modifications sur la commande Coeff seront disponibles pour la prochaine version de Xcas ?
Sinon, y a t il une manip à faire pour actualiser Xcas ?
Merci pour ce fabuleux logiciel :P
Bien cordialement.

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: Corps de Galois

Message par parisse » dim. oct. 15, 2017 8:47 am

laboriefred a écrit :Bonjour, merci pour l'information.
Les modifications sur la commande Coeff seront disponibles pour la prochaine version de Xcas ?
oui, sans doute la semaine prochaine.
Sinon, y a t il une manip à faire pour actualiser Xcas ?
si vous etes sous Windows, le plus simple est d'installer a nouveau (cela ecrase l'install precedente). Sur linux, mettez a jour.

laboriefred
Messages : 13
Inscription : mer. oct. 11, 2017 7:39 pm

Re: Corps de Galois

Message par laboriefred » dim. oct. 15, 2017 10:51 am

Merci

Répondre