Corps finis, exemples

On se propose d’illustrer les manipulations de base à l’aide du logiciel Pari/GP. Le programme s’installe assez facilement sous windows, linux ou osX. Il existe également un port javascript, que l’on utilise dans ces pages.

Si besoin, voir auparavant une page de mini-introduction à Pari/GP.

Dans cette page, on se propose de :

  • construire un corps fini \(K\) de cardinal donné, par exemple \(3^6\).

  • en déterminer un générateur \(g\) du groupe \(K^\times\).

  • calculer le polynôme minimal de \(g\) sur \(\F_p\).

Construire un corps \(K\) à \(3^6\) éléments.

  1. critère d’irréductibilité

    isirred(P,p) = {
  n = poldegree(P);
  q = factor(n)[,1];
  xP = Mod(x,P);
  for(i=1,#q,
    if(gcd(lift(xP^p^(n/q[i])-x),P)!=1,return(0));
    );
  return(1);
}

  2. on tire au hasard jusqu’à obtenir un polynôme irréductible

    findirred(n,p) = {
  until(isirred(P,p),
    P = x^n+random(Mod(1,p)*x^(n-1));
    );P;
  }

Exemples:

findirred(3,3)
P = x^6 + x^5 + x - Mod(1,3)
isirred(P, 3)

Déterminer un élément primitif \(a\) de \(K\).

On veut trouver un élément d’ordre \(q-1\).

is_generator(a,q) = {
  f = factor(q-1)[,1];
  for(i=1,#f,
      if(a^((q-1)/f[i])==1, return(0));
  );
  return(1);
}

Il y en a \(\varphi(q-1)\), donc une bonne proportion, on peut se permettre de tirer au hasard.

q = 3^6;
eulerphi(q-1)/(q-1)
is_generator(Mod(x, P), 3^6)

Déterminer le polynôme minimal de \(a\) sur \(\F_3\).

a = Mod(x-1, P)
Q = prod(i=0,5, y - a^3^i)

Représentation multiplicative (ou de Zech) d’un corps fini

Jusqu’à présent, on a représenté les éléments d’un corps fini \(\F_p^n\) par une algèbre quotient \(\F_p[x]/(P)\), avec \(P\) irréductible de degré \(n\).

De cette manière, l’addition de deux éléments est élémentaire (coefficient par coefficient) tandis que la multiplication nécessite d’effectuer une multiplication et une division sur des polynômes.

En utilisant l’isomorphisme

\[\F_q^\times \to \Z/(q-1)\Z\]

on peut également représenter \(\F_q^\times\) par le groupe cyclique \(\Z/q-1\Z\) via les puissances d’un générateur \(\alpha\), et l’on ajoute un point \(\infty\) pour représenter \(0\).

La multiplication et la division deviennent évidentes :

\[\alpha^e \times \alpha^f = \alpha^{e+f \bmod q-1}\]

En revanche il faut calculer les additions. On se contente de précalculer la table de l’addition par \(1\), à laquelle on se ramène en écrivant

\[a + b = a \times (1+b/a)\]

  1. Pour représenter \(\F_{p^n}\), il faut un générateur \(\alpha\), ou de manière équivalente un polynôme \(P\) de degré \(n\) tel que \(a=x\bmod P\) soit d’ordre \(p^n-1\) (en particulier \(P\) sera irréductible).

    primgenerator(p,n)={
    my(q,f,P,a);
    q = p^n;
    f = factor(q-1)[,1];
    while(1,
        P=x^n+random(Mod(1,p)*x^(n-1));
        a=Mod(x,P);
        \\ check order of a divides q-1
        if(polcoeff(P,0)==0,next());
        if(a^q!=a,next());
        \\ and not strict divisor
        for(i=1,#f,if(a^((q-1)/f[i])==1,next(2)));
        break();
    );
    a;
}

  2. On calcule la table d’addition par 1, que l’on conserve dans un grand tableau de taille \(q-1\).

    Pour cela, on calcule toutes les puissances \(g^k\) et on les fait correspondre aux décalés \(1+g^l\).

    zffinit(p,e) = {
    my(g,q,v,w,gk);
    g = primgenerator(p,e); q=p^e;
    v=vector(q); w=vector(q-1); gk=1;
    for(k=1,q-1,
      gk*=g;
      v[subst(liftall(gk),x,p)]=k;
      w[k]=subst(liftall(gk+1),x,p);
      );
    for(k=1,q-1,w[k]=if(w[k]==0,[],v[w[k]]));
    [q-1,w,g];
}

    Ainsi le corps \(\F_{27}\) se représente

    [q1, v, g] = zffinit(3, 3)

    où q1 vaut \(27-1\), v est la liste des \(1+g^k=g^{v_k}\) et g est l’élément primitif choisi pour représenter \(\F_{27}\).

    On vérifie par exemple

    1 + g^3
    g^v[3]

  3. On définit les opérations usuelles, en utilisant [] pour représenter le point \(\infty\) correspondant au \(0\) de \(\F_q\).

    zffmul(z,a,b) = if(a==[]||b==[],[],(a + b) % z[1]);

zffadd(z,a,b) = if(a==[],b,b==[],a,zffmul(z,a,z[2][(b-a) % z[1] + 1]));

    et si besoin

    zffneg(z,a) = if(a==[],[],(a + z[1]/2) % z[1]);

zffinv(z,a) = if(a==[],error("inv 0"),z[1] - a);

zffdiv(z,a,b) = if(b==[],error("div by 0"),a==[],[],(a - b) % z[1]);

  4. Exemple : multiplication matricielle

    zffmatmul(z,A,B)={
  my(m,n,na,mb);
  [m,na]=matsize(A);
  [mb,n]=matsize(B);
  if(na!=mb,error("incompatible size"));
  matrix(m,n,i,j,
    my(s=[]);
    for(k=1,na,s=zffadd(z,s,zffmul(z,A[i,k],B[k,j])));
    s
    );
}

    Bon, on va avoir une grosse déception : c’est super lent… c’est à cause du modèle gp qui passe les arguments par valeur.

    z = zffinit(3, 10);
A = matrix(50,50,i,j,zffadd(z, i, j));
B = matrix(50,50,i,j,(i-j) % z[1]));
zffmatmul(z,A,B);
##

    Pour se consoler, on peut voir qu’une version C est nettement plus performante.