// xcas version=0.7.2 fontsize=20
// fltk 7Fl_Tile 36 -27 908 50 20
[
// fltk N4xcas23Comment_Multiline_InputE 36 -27 908 49 20
Creation du corps fini a p^m elements GF(p,m), en representation£Z/pZ[X]/polynome irreductible, recherche d'un poly irreductible de degre m
,
// fltk N4xcas10Log_OutputE 36 22 908 1 20

]
,
// fltk 7Fl_Tile 36 25 908 492 20
[
// fltk N4xcas7EditeurE 36 25 908 299 20
996 ,
rapide(A,n,P):={ 
  // powerpc rapide mod P un polynome
  local B;
  if (n==0) return 1;
  if (n==1) return A;
  B:=rapide(A,iquo(n,2),P);
  B:=rem(B*B,P);
  return when(irem(n,2),rem(A*B,P),B);
}:;

est_irred(P,p):={
  // teste si P est irreductible dans Z/pZ[X]
  // en calculant le pgcd de P avec X^(p^k)-X
  // pour k<=deg(P)/2 qui doit donner 1
  local m,k,Xpk,X,un;
  m:=degree(P)/2;
  X:=poly1[1,0]%p;
  Xpk:=X;
  un:=poly1[1]%p;
  for (k:=1;k<=m;k++){
    // X^(p^k) mod P
    Xpk:=rapide(Xpk,p,P); 
    if (gcd(Xpk-X,P)!=un) return 0;
  }
  return 1;
}:;

irred(p,m):={
  // calcul d'un polynome irreductible P
  // tel que GF(p,m)=Z/pZ[X]/P
  local n,irr,mini,pm;
  if (!isprime(p)) return p+" non premier!";
  pm:=p^m;
  // essai systematique de tous les poly, 
  // on pourrait aussi choisir n au hasard jusqu'au succes
  for (n:=1;n<=pm;n++){
    irr:=op(convert(n,base,p));
    irr:=poly1[1,0$(m-size(irr)),irr] % p;
    if (est_irred(irr,p)) return irr;
  }
  return "erreur!";
}:;,
// fltk N4xcas10Log_OutputE 36 324 908 150 20
// Parsing rapide£// Warning: rapide  declared as global variable(s) compiling rapide£// Parsing est_irred£// Warning: rapide  declared as global variable(s) compiling est_irred£// Parsing irred£// Warning: est_irred  declared as global variable(s) compiling irred£rapide: recursive definition£
,
// fltk N4xcas8EquationE 36 474 908 43 20
"Done","Done","Done"
]
,
// fltk 7Fl_Tile 36 519 908 74 20
[
// fltk N4xcas19Multiline_Input_tabE 36 519 908 30 20
P:=irred(2,4)
,
// fltk N4xcas10Log_OutputE 36 549 908 1 20

,
// fltk N4xcas8EquationE 36 550 908 43 20
poly1[1 % 2,0 % 2,0 % 2,1 % 2,1 % 2]
]
,
// fltk 7Fl_Tile 36 595 908 33 20
[
// fltk N4xcas23Comment_Multiline_InputE 36 595 908 32 20
on verifie que P=x^4+x+1 est bien irreductible (alors que x^4+1 ne l'est pas)
,
// fltk N4xcas10Log_OutputE 36 627 908 1 20

]
,
// fltk 7Fl_Tile 36 630 908 84 20
[
// fltk N4xcas19Multiline_Input_tabE 36 630 908 30 20
factor(horner(P,x)%2); factor((x^4+1)%2)
,
// fltk N4xcas10Log_OutputE 36 660 908 1 20

,
// fltk N4xcas8EquationE 36 661 908 53 20
(1 % 2)*x^4+(1 % 2)*x+1 % 2,((1 % 2)*x+1 % 2)^4
]
,
// fltk 7Fl_Tile 36 716 908 33 20
[
// fltk N4xcas23Comment_Multiline_InputE 36 716 908 32 20
autre methode (inutilisable pour p^m grand), on prend un facteur de degre 4 de x^(p^m)-x
,
// fltk N4xcas10Log_OutputE 36 748 908 1 20

]
,
// fltk 7Fl_Tile 36 751 908 114 20
[
// fltk N4xcas19Multiline_Input_tabE 36 751 908 30 20
factor((x^15-1)%2)
,
// fltk N4xcas10Log_OutputE 36 781 908 1 20

,
// fltk N4xcas8EquationE 36 782 908 83 20
((1 % 2)*x+1 % 2)*((1 % 2)*x^2+(1 % 2)*x+1 % 2)*((1 % 2)*x^4+(1 % 2)*x+1 % 2)*((1 % 2)*x^4+(1 % 2)*x^3+(1 % 2)*x^2+(1 % 2)*x+1 % 2)*((1 % 2)*x^4+(1 % 2)*x^3+1 % 2)
]
,
// fltk 7Fl_Tile 36 867 908 106 20
[
// fltk N4xcas23Comment_Multiline_InputE 36 867 908 105 20
GF(2,4) renvoie un polynome irreductible qui est aussi primitif£il est bien sur dans la liste des facteurs ci-dessus£Pour travailler dans GF(2,4) on utilisera plutot G:=GF(2,4,['a','G']),£puis b:=G(Q(a)) ou Q est un polynome renvoie l'element represente par Q£on peut alors calculer b^2, b+b^2 , etc. qui seront affiches en fonction de a
,
// fltk N4xcas10Log_OutputE 36 972 908 1 20

]
,
// fltk 7Fl_Tile 36 975 908 84 20
[
// fltk N4xcas19Multiline_Input_tabE 36 975 908 30 20
G:=GF(2,4)
,
// fltk N4xcas10Log_OutputE 36 1005 908 1 20

,
// fltk N4xcas8EquationE 36 1006 908 53 20
GF(2,x^4+x^3+1,x,undef)
]
,
// fltk 7Fl_Tile 36 1061 908 169 20
[
// fltk N4xcas23Comment_Multiline_InputE 36 1061 908 168 20
Pour trouver un polynome primitif, on calcule le poly minimal d'un element£primitif choisi au hasard dans le corps quotient Z/pZ[X]/P (poly irreductible).£On commence donc par chercher a primitif, il faut que a^(p^m-1)=1 soit£la premiere puissance realisant cette egalite,£i.e. a^((p^m-1)/d) != 1 pour tout d diviseur premier de p^m-1.£Pour trouver le poly minimal, on calcule en colonnes 1,a,...,a^(p-1)£dans la base canonique des polynomes modulo P et on calcule£le noyau de cette matrice (modulo p)
,
// fltk N4xcas10Log_OutputE 36 1229 908 1 20

]
,
// fltk 7Fl_Tile 36 1232 908 31 20
[
// fltk N4xcas23Comment_Multiline_InputE 36 1232 908 30 20
première méthode, avec les instructions de xcas
,
// fltk N4xcas10Log_OutputE 36 1262 908 1 20

]
,
// fltk 7Fl_Tile 36 1265 908 84 20
[
// fltk N4xcas19Multiline_Input_tabE 36 1265 908 30 20
A:=x^2+1:; Q:=x^4+x+1:; powmod(A,15,2,x^4+x+1); powmod(A,5,2,x^4+x+1); powmod(A,3,2,x^4+x+1); 
,
// fltk N4xcas10Log_OutputE 36 1295 908 1 20

,
// fltk N4xcas8EquationE 36 1296 908 53 20
"Done","Done",1,x^2+x+1,x^3+x
]
,
// fltk 7Fl_Tile 36 1351 908 81 20
[
// fltk N4xcas19Multiline_Input_tabE 36 1351 908 27 20
Ap:=[0$(degree(Q)+1)]:; Ap[0]:=1%2:; for (j:=1;j<size(Ap);j++){ Ap[j]:=rem(Ap[j-1]*A,Q,x); }; 
,
// fltk N4xcas10Log_OutputE 36 1378 908 1 20

,
// fltk N4xcas8EquationE 36 1379 908 53 20
"Done","Done",[1 % 2,(1 % 2)*x^2+1 % 2,(1 % 2)*x,(1 % 2)*x^3+(1 % 2)*x,(1 % 2)*x^2+(0 % 2)*x]
]
,
// fltk 7Fl_Tile 36 1434 908 71 20
[
// fltk N4xcas19Multiline_Input_tabE 36 1434 908 27 20
B:=seq(coeffs(Ap[j],x),j,0,size(Ap)-1);
,
// fltk N4xcas10Log_OutputE 36 1461 908 1 20

,
// fltk N4xcas8EquationE 36 1462 908 43 20
[poly1[1 % 2],poly1[1 % 2,0,1 % 2],poly1[1 % 2,0],poly1[1 % 2,0,1 % 2,0],poly1[1 % 2,0,0]]
]
,
// fltk 7Fl_Tile 36 1507 908 231 20
[
// fltk N4xcas19Multiline_Input_tabE 36 1507 908 27 20
for (j:=0;j<size(B);j++){ B[j]:=[0$(degree(Q)-size(B[j])),op(B[j])]; }
,
// fltk N4xcas10Log_OutputE 36 1534 908 1 20

,
// fltk N4xcas8EquationE 36 1535 908 203 20
[[0,0,0,1 % 2],[0,1 % 2,0,1 % 2],[0,0,1 % 2,0],[1 % 2,0,1 % 2,0],[0,1 % 2,0,0]]
]
,
// fltk 7Fl_Tile 36 1740 908 74 20
[
// fltk N4xcas19Multiline_Input_tabE 36 1740 908 30 20
ker(tran(B))
,
// fltk N4xcas10Log_OutputE 36 1770 908 1 20

,
// fltk N4xcas8EquationE 36 1771 908 43 20
[[1 % 2,1 % 2,0 % 2,0 % 2,1 % 2]]
]
,
// fltk 7Fl_Tile 36 1816 908 31 20
[
// fltk N4xcas23Comment_Multiline_InputE 36 1816 908 30 20
2ème méthode avec notre programme rapide et en représentation liste
,
// fltk N4xcas10Log_OutputE 36 1846 908 1 20

]
,
// fltk 7Fl_Tile 36 1849 908 94 20
[
// fltk N4xcas19Multiline_Input_tabE 36 1849 908 50 20
a:=5; A:=poly1[op(revlist(convert(a,base,2)%2))];£ rapide(A,5,P); rapide(A,3,P);
,
// fltk N4xcas10Log_OutputE 36 1899 908 1 20

,
// fltk N4xcas8EquationE 36 1900 908 43 20
5,poly1[1 % 2,0 % 2,1 % 2],poly1[1 % 2,1 % 2,1 % 2],poly1[1 % 2,0 % 2,1 % 2,0 % 2]
]
,
// fltk 7Fl_Tile 36 1945 908 73 20
[
// fltk N4xcas19Multiline_Input_tabE 36 1945 908 29 20
rapide(A,15,P);
,
// fltk N4xcas10Log_OutputE 36 1974 908 1 20

,
// fltk N4xcas8EquationE 36 1975 908 43 20
poly1[1 % 2]
]
,
// fltk 7Fl_Tile 36 2020 908 72 20
[
// fltk N4xcas19Multiline_Input_tabE 36 2020 908 28 20
A1:=A;A2:=rapide(A,2,P); A3:=rapide(A,3,P); A4:=rapide(A,4,P)
,
// fltk N4xcas10Log_OutputE 36 2048 908 1 20

,
// fltk N4xcas8EquationE 36 2049 908 43 20
poly1[1 % 2,0 % 2,1 % 2],poly1[1 % 2,0 % 2],poly1[1 % 2,0 % 2,1 % 2,0 % 2],poly1[1 % 2,0 % 2,0 % 2]
]
,
// fltk 7Fl_Tile 36 2094 908 196 20
[
// fltk N4xcas19Multiline_Input_tabE 36 2094 908 32 20
M:=tran([[0,0,0,1],[0,1,0,1],[0,0,1,0],[1,0,1,0],[0,1,0,0]])%2
,
// fltk N4xcas10Log_OutputE 36 2126 908 1 20

,
// fltk N4xcas8EquationE 36 2127 908 163 20
[[0 % 2,0 % 2,0 % 2,1 % 2,0 % 2],[0 % 2,1 % 2,0 % 2,0 % 2,1 % 2],[0 % 2,0 % 2,1 % 2,1 % 2,0 % 2],[1 % 2,1 % 2,0 % 2,0 % 2,0 % 2]]
]
,
// fltk 7Fl_Tile 36 2292 908 69 20
[
// fltk N4xcas19Multiline_Input_tabE 36 2292 908 25 20
ker(M)
,
// fltk N4xcas10Log_OutputE 36 2317 908 1 20

,
// fltk N4xcas8EquationE 36 2318 908 43 20
[[1 % 2,1 % 2,0 % 2,0 % 2,1 % 2]]
]
,
// fltk 7Fl_Tile 36 2363 908 31 20
[
// fltk N4xcas23Comment_Multiline_InputE 36 2363 908 30 20
donc x^4+x^3+1 est irred primitif
,
// fltk N4xcas10Log_OutputE 36 2393 908 1 20

]
,
// fltk 7Fl_Tile 36 2396 908 31 20
[
// fltk N4xcas19Multiline_Input_tabE 36 2396 908 30 20

,
// fltk N4xcas10Log_OutputE 36 2426 908 1 20

]