Bill Allombert on Tue, 13 Mar 2007 23:49:21 +0100

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

 PARI/GP support for finite fields element

```Hello PARI-dev,

I am working on a patch (in attachment) that add support for 'finite
field elements' to PARI/GP.

Under GP, this is to be used as follow:
? P=ffinit(3,3,a); \\Polynomial defining F_3^3
? a=ffgen(P); \\return the element "a mod P" of Fp[X]/(P)
? a^5
%3 = 2*a^2 + 2*a
? matdet([1,1,1;a,a^3,a^9;a^2,a^6,a^18])
%4 = 1

The following operations are available on finite field elements:
+,-,*,/,^
==,!=
shiftmul sqr
sqrt sqrtn
norm trace
charpoly minpoly
factor(polynomial over a finite field)

This patch create a new PARI type 't_FFELT'. Two data format are used
depending on the size of the characteristic p of the field to improve
performance.

Cheers,
Bill.
```
```Index: src/basemath/Flx.c
===================================================================
RCS file: /home/cvs/pari/src/basemath/Flx.c,v
retrieving revision 1.81
diff -u -r1.81 Flx.c
--- src/basemath/Flx.c	13 Mar 2007 20:21:05 -0000	1.81
+++ src/basemath/Flx.c	13 Mar 2007 20:21:20 -0000
@@ -1447,6 +1447,36 @@
return V;
}

+ulong
+Flxq_norm(GEN x, GEN T, ulong p)
+{
+  ulong y = Flx_resultant(T, x, p);
+  ulong L = T[lg(T)-1];
+  if ( L==1 || lgpol(x)==0) return y;
+  return Fl_div(y, Fl_pow(L, (ulong)degpol(x), p), p);
+}
+
+/*x must be reduced*/
+GEN
+Flxq_charpoly(GEN x, GEN T, ulong p)
+{
+  pari_sp ltop=avma;
+  long v=varn(T);
+  GEN R = Flx_FlxY_resultant(T, deg1pol_i(Fl_to_Flx(1,x[1]),Flx_neg(x,p),v) ,p);
+  return gerepileupto(ltop,R);
+}
+
+GEN
+Flxq_minpoly(GEN x, GEN T, ulong p)
+{
+  pari_sp ltop=avma;
+  GEN R=Flxq_charpoly(x, T, p);
+  GEN G=Flx_gcd(R,Flx_deriv(R,p),p);
+  G=Flx_normalize(G,p);
+  G=Flx_div(R,G,p);
+  return gerepileupto(ltop,G);
+}
+
/***********************************************************************/
/**                                                                   **/
/**                               FlxV                                **/
Index: src/basemath/alglin2.c
===================================================================
RCS file: /home/cvs/pari/src/basemath/alglin2.c,v
retrieving revision 1.234
diff -u -r1.234 alglin2.c
--- src/basemath/alglin2.c	13 Mar 2007 19:20:23 -0000	1.234
+++ src/basemath/alglin2.c	13 Mar 2007 19:29:27 -0000
@@ -112,6 +112,13 @@
gel(p1,2) = gnorm(x); av = avma;
gel(p1,3) = gerepileupto(av, gneg(gtrace(x)));
gel(p1,4) = gen_1; return p1;
+
+    case t_FFELT: {
+      pari_sp ltop=avma;
+      if (py) pari_err(typeer,"easychar");
+      p1 = FpX_to_mod(FF_charpoly(x), FF_p(x));
+      setvarn(p1,v); return gerepileupto(ltop,p1);
+    }

case t_POLMOD:
if (py) pari_err(typeer,"easychar");
@@ -264,6 +271,12 @@
pari_sp ltop=avma;
GEN P;
if (v<0) v = 0;
+  if (typ(x)==t_FFELT)
+  {
+      GEN p1 = FpX_to_mod(FF_minpoly(x), FF_p(x));
+      setvarn(p1,v); return gerepileupto(ltop,p1);
+  }
+
P=easymin(x,v);
if (P) return P;
if (typ(x)==t_POLMOD)
@@ -384,6 +397,11 @@
case t_POL: case t_SER: case t_RFRAC: av = avma;
return gerepileupto(av, greal(gmul(gconj(x),x)));

+    case t_FFELT:
+      y=cgetg(3, t_INTMOD);
+      gel(y,1) = icopy(FF_p(x));
+      gel(y,2) = FF_norm(x);
+      return y;
case t_POLMOD:
if (typ(gel(x,2)) != t_POL) return gpowgs(gel(x,2), degpol(gel(x,1)));
return RgXQ_norm(gel(x,2), gel(x,1));
@@ -705,6 +723,13 @@
if (typ(z) != t_POL || varn(y) != varn(z)) return gmulsg(degpol(y), z);
av = avma;
return gerepileupto(av, quicktrace(z, polsym(y, degpol(y)-1)));
+
+    case t_FFELT:
+      y=cgetg(3, t_INTMOD);
+      gel(y,1) = icopy(FF_p(x));
+      gel(y,2) = FF_trace(x);
+      return y;
+

case t_RFRAC:
Index: src/basemath/gen1.c
===================================================================
RCS file: /home/cvs/pari/src/basemath/gen1.c,v
retrieving revision 1.182
diff -u -r1.182 gen1.c
--- src/basemath/gen1.c	27 Sep 2006 14:03:02 -0000	1.182
+++ src/basemath/gen1.c	13 Mar 2007 13:21:52 -0000
@@ -725,6 +725,7 @@
if (gequal(gel(x,1), gel(y,1)))
return add_polmod_same(gel(x,1), gel(x,2), gel(y,2));
return add_polmod(gel(x,1), gel(y,1), gel(x,2), gel(y,2));
+    case t_FFELT: return FF_add(x,y);
case t_POL:
vx = varn(x);
vy = varn(y);
@@ -810,6 +811,7 @@
case t_COMPLEX: return addRc(x, y);
+        case t_FFELT: return FF_Z_add(y,x);
}

case t_REAL:
@@ -838,6 +840,10 @@
p1 = modii(mulii(gel(y,1), Fp_inv(gel(y,2),X)), X);
return add_intmod_same(z, X, p1, gel(x,2));
}
+        case t_FFELT:
+          if (!equalii(gel(x,1),FF_p(y)))
+            pari_err(operi,"+",x,y);
case t_COMPLEX: return addRc(x, y);
case t_PADIC: { GEN X = gel(x,1);
z = cgetg(3, t_INTMOD);
@@ -1284,6 +1290,7 @@
case t_COMPLEX: return mulcc(x, y);
case t_PADIC: return mulpp(x, y);
case t_QUAD: return mulqq(x, y);
+    case t_FFELT: return FF_mul(x, y);
case t_POLMOD:
if (gequal(gel(x,1), gel(y,1)))
return mul_polmod_same(gel(x,1), gel(x,2), gel(y,2));
@@ -1397,6 +1404,7 @@
case t_COMPLEX: return mulRc(x, y);
case t_PADIC: return signe(x)? mulTp(x, y): gen_0;
case t_QUAD: return mulRq(x,y);
+        case t_FFELT: return FF_Z_mul(y,x);
}

case t_REAL:
@@ -1424,16 +1432,24 @@
return mul_intmod_same(z, X, gel(x,2), padic_to_Fp(y, X));
}
case t_QUAD: return mulRq(x, y);
-      }
+        case t_FFELT:
+          if (!equalii(gel(x,1),FF_p(y)))
+            pari_err(operi,"*",x,y);
+          return FF_Z_mul(y,gel(x,2));
+     }

case t_FRAC:
switch(ty)
{
case t_COMPLEX: return mulRc(x, y);
case t_PADIC: return signe(x[1])? mulTp(x, y): gen_0;
-        case t_QUAD: return mulRq(x, y);
+        case t_QUAD:  return mulRq(x, y);
+        case t_FFELT: return FF_Z_Z_muldiv(y, gel(x,1),gel(x,2));
}

+    case t_FFELT:
+      pari_err(operf,"*",x,y);
+
case t_COMPLEX:
switch(ty)
{
@@ -1718,6 +1734,8 @@
av=avma; p1=gsqr(gel(x,2)); tetpil=avma;
gel(z,2) = gerepile(av,tetpil, grem(p1,gel(z,1)));
return z;
+
+      case t_FFELT: return FF_sqr(x);
}

switch(tx)
@@ -1988,6 +2006,8 @@
av = avma; p1 = quadnorm(y); p2 = mulqq(x, gconj(y)); tetpil = avma;
return gerepile(av, tetpil, gdiv(p2,p1));

+    case t_FFELT: return FF_div(x,y);
+
case t_POLMOD: av = avma;
if (gequal(gel(x,1), gel(y,1)))
{
@@ -2047,10 +2067,15 @@
long s = signe(x);
if (!s) {
if (gcmp0(y)) pari_err(gdiver);
-      if (ty != t_INTMOD) return gen_0;
-      z = cgetg(3,t_INTMOD);
-      gel(z,1) = icopy(gel(y,1));
-      gel(z,2) = gen_0; return z;
+      switch (ty)
+      {
+      default: return gen_0;
+      case t_INTMOD:
+        z = cgetg(3,t_INTMOD);
+        gel(z,1) = icopy(gel(y,1));
+        gel(z,2) = gen_0; return z;
+      case t_FFELT: return FF_zero(y);
+      }
}
if (is_pm1(x)) {
if (s > 0) return ginv(y);
@@ -2082,6 +2107,7 @@
}
return z;

+      case t_FFELT: return Z_FF_div(x,y);
case t_COMPLEX: return divRc(x,y);
case t_PADIC: return divTp(x, y);
@@ -2115,6 +2141,11 @@
z = cgetg(3,t_INTMOD); p1 = remii(mulii(gel(y,2), gel(x,2)), X);
return div_intmod_same(z, X, p1, modii(gel(y,1), X));
}
+        case t_FFELT:
+          if (!equalii(gel(x,1),FF_p(y)))
+            pari_err(operi,"/",x,y);
+          return Z_FF_div(gel(x,2),y);
+
case t_COMPLEX:
av = avma; p1 = cxnorm(y); p2 = mulRc(x, gconj(y)); tetpil = avma;
return gerepile(av,tetpil, gdiv(p2,p1));
@@ -2158,6 +2189,9 @@
z = cgetg(3,t_INTMOD); p1 = remii(mulii(gel(y,2),gel(x,2)), Y);
return div_intmod_same(z, Y, gel(x,1), p1);
}
+        case t_FFELT: av=avma;
+          return gerepileupto(av,Z_FF_div(gel(x,1),FF_Z_mul(y,gel(x,2))));
+
case t_COMPLEX: return divRc(x, y);

@@ -2168,7 +2202,20 @@
av=avma; p1=quadnorm(y); p2=gmul(x,gconj(y)); tetpil=avma;
return gerepile(av,tetpil,gdiv(p2,p1));
}
-
+    case t_FFELT:
+      switch (ty)
+      {
+        case t_INT: return FF_Z_Z_muldiv(x,gen_1,y);
+        case t_FRAC: return FF_Z_Z_muldiv(x,gel(y,2),gel(y,1));
+        case t_INTMOD:
+          if (!equalii(gel(y,1),FF_p(x)))
+            pari_err(operi,"/",x,y);
+          return FF_Z_Z_muldiv(x,gen_1,gel(y,2));
+        default:
+        pari_err(operf,"/",x,y);
+      }
+      break;
+
case t_COMPLEX:
switch(ty)
{
@@ -2319,6 +2366,7 @@
gel(z,2) = gerepileuptoint((pari_sp)z, modii(mulsi(s,gel(y,2)), p));
gel(z,1) = icopy(p); return z;
}
+    case t_FFELT: return FF_Z_mul(y,stoi(s));
case t_FRAC:
if (!s) return gen_0;
z = cgetg(3,t_FRAC);
@@ -2429,6 +2477,8 @@
case t_INTMOD:
z = cgetg(3, t_INTMOD);
return div_intmod_same(z, gel(x,1), gel(x,2), modsi(s, gel(x,1)));
+
+    case t_FFELT: return FF_Z_Z_muldiv(x,gen_1,stoi(s));

case t_FRAC: z = cgetg(3, t_FRAC);
i = cgcd(s, smodis(gel(x,1), s));
@@ -2527,6 +2577,8 @@
gel(z,2) = gerepileuptoint((pari_sp)z, modii(shifti(a,n), b));
gel(z,1) = icopy(b); return z;

+    case t_FFELT: return FF_mul2n(x,n);
+
case t_FRAC: a = gel(x,1); b = gel(x,2);
l = vali(a);
k = vali(b);
Index: src/basemath/gen2.c
===================================================================
RCS file: /home/cvs/pari/src/basemath/gen2.c,v
retrieving revision 1.167
diff -u -r1.167 gen2.c
--- src/basemath/gen2.c	3 Mar 2007 21:36:11 -0000	1.167
+++ src/basemath/gen2.c	9 Mar 2007 00:39:13 -0000
@@ -185,6 +185,9 @@
case t_INTMOD: case t_POLMOD:
return gcmp0(gel(x,2));

+    case t_FFELT:
+      return FF_cmp0(x);
+
case t_FRAC:
return 0;

@@ -253,9 +256,12 @@
case t_REAL:
return signe(x) > 0 ? absrnz_egal1(x): 0;

-    case t_INTMOD: case t_POLMOD:
+    case t_INTMOD: case t_POLMOD:
return gcmp1(gel(x,2));
-
+
+    case t_FFELT:
+      return FF_cmp1(x);
+
case t_FRAC:
return 0;

@@ -295,6 +301,9 @@

case t_FRAC:
return 0;
+
+    case t_FFELT:
+      return FF_cmp_1(x);

case t_COMPLEX:
return gcmp_1(gel(x,1)) && gcmp0(gel(x,2));
@@ -495,6 +504,9 @@
return gequal(gel(x,2),gel(y,2))
&& (x[1]==y[1] || gequal(gel(x,1),gel(y,1)));

+      case t_FFELT:
+        return FF_equal(x,y);
+
case t_QFR:
if (!gequal(gel(x,4),gel(y,4))) return 0; /* fall through */
case t_QFI:
@@ -921,6 +933,8 @@
gel(y,2) = gneg(gel(x,2));
gel(y,3) = gneg(gel(x,3)); break;

+    case t_FFELT: return FF_neg(x);
+
case t_POL: case t_SER:
case t_VEC: case t_COL: case t_MAT:
y = init_gen_op(x, tx, &lx, &i);
@@ -961,6 +975,8 @@
case t_POLMOD: y=cgetg(3,t_POLMOD); y[1]=x[1];
gel(y,2) = gneg_i(gel(x,2)); break;

+    case t_FFELT: return FF_neg_i(x);
+
gel(y,2) = gneg_i(gel(x,2));
gel(y,3) = gneg_i(gel(x,3)); break;
Index: src/basemath/gen3.c
===================================================================
RCS file: /home/cvs/pari/src/basemath/gen3.c,v
retrieving revision 1.257
diff -u -r1.257 gen3.c
--- src/basemath/gen3.c	28 Feb 2007 19:02:36 -0000	1.257
+++ src/basemath/gen3.c	13 Mar 2007 20:23:51 -0000
@@ -1085,6 +1085,7 @@
else gel(z,2) = ginvmod(gel(x,2), X);
return z;

+    case t_FFELT: return FF_inv(x);
case t_POL: return gred_rfrac_simple(gen_1,x);
case t_SER: return gdiv(gen_1,x);

@@ -2708,7 +2709,8 @@

switch(typ(x))
{
-    case t_INT: case t_REAL: case t_INTMOD: case t_PADIC: case t_SER:
+    case t_INT: case t_REAL: case t_INTMOD: case t_FFELT:
+    case t_PADIC: case t_SER:
return gen_1;

case t_FRAC:
@@ -2753,7 +2755,7 @@

switch(typ(x))
{
-    case t_INT: case t_REAL: case t_INTMOD:
+    case t_INT: case t_REAL: case t_INTMOD: case t_FFELT:
case t_PADIC: case t_POL: case t_SER:
return gcopy(x);

@@ -2798,6 +2800,9 @@
gel(y,1) = lift0(gel(x,1),v);
gel(y,2) = lift0(gel(x,2),v); return y;

+    case t_FFELT:
+      return gcopy(x);
+
return gtrunc(x);

@@ -3153,6 +3158,8 @@
if (typ(y[1]) != t_POL) y[1] = x[1]; /* invalid object otherwise */
gel(y,2) = simplify_i(gel(x,2)); return y;

+    case t_FFELT: return gcopy(x);
+
case t_POL:
lx = lg(x); if (lx==2) return gen_0;
if (lx==3) return simplify_i(gel(x,2));
Index: src/basemath/polarit2.c
===================================================================
RCS file: /home/cvs/pari/src/basemath/polarit2.c,v
retrieving revision 1.443
diff -u -r1.443 polarit2.c
--- src/basemath/polarit2.c	7 Mar 2007 15:15:26 -0000	1.443
+++ src/basemath/polarit2.c	13 Mar 2007 19:57:47 -0000
@@ -1728,16 +1728,16 @@
static long
poltype(GEN x, GEN *ptp, GEN *ptpol, long *ptpa)
{
-  long t[15];
+  long t[16];
long tx = typ(x),lx,i,j,s,pa=BIGINT;
-  GEN pcx=NULL, p=NULL,pol=NULL,p1,p2;
+  GEN pcx=NULL, p=NULL,pol=NULL,ff=NULL,p1,p2;

if (is_scalar_t(tx))
{
if (tx == t_POLMOD) return 0;
x = scalarpol(x,0);
}
-  for (i=2; i<15; i++) t[i]=0;
+  for (i=2; i<16; i++) t[i]=0;
/* t[0..1] unused. Other values, if set, indicate a coefficient of type
* t[2] : t_REAL
* t[3] : t_INTMOD
@@ -1751,7 +1751,8 @@
* t[12]: t_POLMOD of rationals (t_INT/t_FRAC)
* t[13]: t_POLMOD of t_INTMOD
-   * t[14]: t_POLMOD of t_PADIC */
+   * t[14]: t_POLMOD of t_PADIC
+   * t[15]: t_FFELT */
lx = lg(x);
for (i=2; i<lx; i++)
{
@@ -1766,6 +1767,12 @@
case t_INTMOD:
assign_or_fail(gel(p1,1),p);
t[3]=1; break;
+      case t_FFELT:
+        if (ff==NULL) ff=p1;
+        else if (!FF_samefield(p1,ff)) return 0;
+        p2=FF_p(p1);
+        assign_or_fail(p2,p);
+        t[15]=1; break;
case t_COMPLEX:
if (!pcx) pcx = mkpoln(3, gen_1,gen_0,gen_1); /* x^2 + 1 */
for (j=1; j<=2; j++)
@@ -1866,6 +1873,12 @@
i = t[12]? t_POLMOD: (t[9]? t_QUAD: t_COMPLEX);
return typs(i, t_INT);
}
+  if (t[15])
+  {
+    if (t[8]) return 0;
+    *ptp=p; *ptpol=ff;
+    return t_FFELT;
+  }
if (t[3]) { *ptp=p; return t_INTMOD; }
if (t[8]) { *ptp=p; *ptpa=pa; return t_PADIC; }
return t_INT;
@@ -2154,6 +2167,8 @@
gel(y,2) = const_col(lx-1, gen_1); return y;

+
+	case t_FFELT: return FFX_factor(x,pol);

default:
{
@@ -4522,3 +4537,29 @@
}
return gerepilecopy(ltop, sol);
}
+GEN ffgen(GEN T)
+{
+  GEN ff=cgetg(5,t_FFELT);
+  GEN p,junk;
+  long ljunk;
+  if (typ(T)!=t_POL || degpol(T)<1)
+    pari_err(typeer,"ffgen");
+  if (poltype(T,&p,&junk,&ljunk)!=t_INTMOD)
+    pari_err(typeer,"ffgen");
+  if (lgefint(p)==3)
+  {
+    ff[1]=itou(p);
+    gel(ff,2)=polx_Flx(evalvarn(varn(T)));
+    gel(ff,3)=ZX_to_Flx(lift(T),ff[1]);
+    gel(ff,4)=icopy(p);
+
+  }
+  else
+  {
+    ff[1]=0;
+    gel(ff,2)=pol_x(varn(T));
+    gel(ff,3)=lift(T);
+    gel(ff,4)=icopy(p);
+  }
+  return ff;
+}
Index: src/basemath/trans1.c
===================================================================
RCS file: /home/cvs/pari/src/basemath/trans1.c,v
retrieving revision 1.221
diff -u -r1.221 trans1.c
--- src/basemath/trans1.c	5 Feb 2007 08:16:02 -0000	1.221
+++ src/basemath/trans1.c	4 Mar 2007 21:11:06 -0000
@@ -311,6 +311,8 @@
y = cgetg(3,t_INTMOD); gel(y,1) = icopy(gel(x,1));
gel(y,2) = gen_1; return y;

+    case t_FFELT: return FF_1(x);
+
case t_POLMOD:
y = cgetg(3,t_POLMOD);
gel(y,1) = gcopy(gel(x,1));
@@ -649,6 +651,7 @@
y = cgetg(3,t_INTMOD); gel(y,1) = icopy(gel(x,1));
gel(y,2) = Fp_pow(gel(x,2), n, gel(x,1));
return y;
+    case t_FFELT: return FF_pow(x,n);
case t_PADIC: return powp(x, n);

case t_INT:
@@ -784,8 +787,9 @@
if (tn == t_FRAC)
{
GEN z, d = gel(n,2), a = gel(n,1);
-    if (tx == t_INTMOD)
+    switch (tx)
{
+    case t_INTMOD:
if (!BSW_psp(gel(x,1))) pari_err(talker,"gpow: modulus %Z is not prime",x[1]);
y = cgetg(3,t_INTMOD); gel(y,1) = icopy(gel(x,1));
av = avma;
@@ -793,12 +797,14 @@
if (!z) pari_err(talker,"gpow: nth-root does not exist");
gel(y,2) = gerepileuptoint(av, Fp_pow(z, a, gel(x,1)));
return y;
-    }
-    else if (tx == t_PADIC)
-    {
+
z = equaliu(d, 2)? padic_sqrt(x): padic_sqrtn(x, d, NULL);
if (!z) pari_err(talker, "gpow: nth-root does not exist");
return gerepileupto(av, powgi(z, a));
+
+    case t_FFELT:
+      return gerepileupto(av,FF_pow(FF_sqrtn(x,d,NULL),a));
}
}
i = (long) precision(n); if (i) prec=i;
@@ -978,6 +984,8 @@

+    case t_FFELT: return FF_sqrt(x);
+
default:
av = avma; if (!(y = toser_i(x))) break;
return gerepileupto(av, ser_powfrac(y, ghalf, prec));
@@ -1158,7 +1166,8 @@
pari_err(talker,"nth-root does not exist in gsqrtn");
}
return y;
-
+  case t_FFELT: return FF_sqrtn(x,n,zetan);
+
case t_INT: case t_FRAC: case t_REAL: case t_COMPLEX:
i = precision(x); if (i) prec = i;
if (tx==t_INT && is_pm1(x) && signe(x) > 0)
===================================================================
retrieving revision 1.624
diff -u -r1.624 paridecl.h
--- src/headers/paridecl.h	13 Mar 2007 19:28:30 -0000	1.624
+++ src/headers/paridecl.h	13 Mar 2007 19:29:47 -0000
@@ -72,9 +72,12 @@
GEN     FlxX_to_ZXX(GEN B);
GEN     FlxY_Flx_div(GEN x, GEN y, ulong p);
GEN     FlxYqQ_pow(GEN x, GEN n, GEN S, GEN T, ulong p);
+GEN     Flxq_charpoly(GEN x, GEN T, ulong p);
GEN     Flxq_inv(GEN x,GEN T,ulong p);
GEN     Flxq_invsafe(GEN x, GEN T, ulong p);
+GEN     Flxq_minpoly(GEN x, GEN T, ulong p);
GEN     Flxq_mul(GEN y,GEN x,GEN T,ulong p);
+ulong   Flxq_norm(GEN x, GEN T, ulong p);
GEN     Flxq_pow(GEN x, GEN n, GEN T, ulong p);
GEN     Flxq_powers(GEN x, long l, GEN T, ulong p);
GEN     Flxq_sqr(GEN y,GEN T,ulong p);
@@ -1006,6 +1009,36 @@
void    writebin(char *name, GEN x);
void    writetex(const char *s, GEN g);

+/* ffelt.c */
+GEN     FF_1(GEN a);
+GEN     FF_Z_Z_muldiv(GEN x, GEN y, GEN z);
+GEN     FF_Z_add(GEN a, GEN b);
+GEN     FF_Z_mul(GEN a, GEN b);
+GEN     FF_add(GEN a, GEN b);
+GEN     FF_charpoly(GEN x);
+int     FF_cmp0(GEN x);
+int     FF_cmp1(GEN x);
+int     FF_cmp_1(GEN x);
+GEN     FF_div(GEN a, GEN b);
+int     FF_equal(GEN a, GEN b);
+GEN     FF_inv(GEN a);
+GEN     FF_minpoly(GEN x);
+GEN     FF_mul(GEN a, GEN b);
+GEN     FF_mul2n(GEN a, long n);
+GEN     FF_neg(GEN a);
+GEN     FF_neg_i(GEN a);
+GEN     FF_norm(GEN x);
+GEN     FF_pow(GEN x, GEN n);
+int     FF_samefield(GEN x, GEN y);
+GEN     FF_sqr(GEN a);
+GEN     FF_sqrt(GEN a);
+GEN     FF_sqrtn(GEN x, GEN n, GEN *zetan);
+GEN     FF_to_FpXQ(GEN x);
+GEN     FF_trace(GEN x);
+GEN     FF_zero(GEN a);
+GEN     FFX_factor(GEN f, GEN ff);
+GEN     Z_FF_div(GEN a, GEN b);
+
/* galconj.c */

GEN     checkgal(GEN gal);
@@ -1581,6 +1614,7 @@
GEN     factorback0(GEN fa,GEN e, GEN nf);
GEN     factorbackelt(GEN fa, GEN e, GEN nf);
GEN     factpol(GEN x, long hint);
+GEN     ffgen(GEN T);
GEN     gbezout(GEN x, GEN y, GEN *u, GEN *v);
GEN     gcd0(GEN x, GEN y,long flag);
GEN     gdeflate(GEN x, long v, long d);
===================================================================
retrieving revision 1.8
diff -u -r1.8 paritype.h
--- src/headers/paritype.h	1 Sep 2004 23:48:37 -0000	1.8
+++ src/headers/paritype.h	3 Mar 2007 17:30:49 -0000
@@ -20,6 +20,7 @@
t_REAL   =  2,
t_INTMOD =  3,
t_FRAC   =  4,
+  t_FFELT  =  5,
t_COMPLEX=  6,
Index: src/kernel/none/level1.h
===================================================================
RCS file: /home/cvs/pari/src/kernel/none/level1.h,v
retrieving revision 1.121
diff -u -r1.121 level1.h
--- src/kernel/none/level1.h	4 Oct 2006 14:11:42 -0000	1.121
+++ src/kernel/none/level1.h	11 Mar 2007 22:58:05 -0000
@@ -86,6 +86,7 @@
ulong  Fl_neg(ulong x, ulong p);
ulong  Fl_sqr(ulong a, ulong p);
ulong  Fl_sub(ulong a, ulong b, ulong p);
+GEN    FF_p(GEN x);
int    dvdii(GEN x, GEN y);
int    dvdiiz(GEN x, GEN y, GEN z);
int    dvdis(GEN x, long y);
@@ -1257,6 +1258,12 @@
return Fl_mul(a, Fl_inv(b, p), p);
}

+INLINE GEN
+FF_p(GEN x)
+{
+  return gel(x,4);
+}
+
INLINE long
expi(GEN x)
{
Index: src/language/es.c
===================================================================
RCS file: /home/cvs/pari/src/language/es.c,v
retrieving revision 1.236
diff -u -r1.236 es.c
--- src/language/es.c	7 Mar 2007 00:52:03 -0000	1.236
+++ src/language/es.c	13 Mar 2007 13:55:42 -0000
@@ -1291,6 +1291,7 @@
case t_REAL   : s="t_REAL";    break;
case t_INTMOD : s="t_INTMOD";  break;
case t_FRAC   : s="t_FRAC";    break;
+    case t_FFELT  : s="t_FFELT";   break;
case t_COMPLEX: s="t_COMPLEX"; break;
@@ -1384,6 +1385,12 @@
blancs(bl); pariputs("den = "); voir2(gel(x,2),nb,bl);
break;

+    case t_FFELT:
+      blancs(bl); pariputs("pol = "); voir2(gel(x,2),nb,bl);
+      blancs(bl); pariputs("mod = "); voir2(gel(x,3),nb,bl);
+      blancs(bl); pariputs("p   = "); voir2(gel(x,4),nb,bl);
+      break;
+
case t_COMPLEX:
blancs(bl); pariputs("real = "); voir2(gel(x,1),nb,bl);
blancs(bl); pariputs("imag = "); voir2(gel(x,2),nb,bl);
@@ -1642,6 +1649,8 @@
return !signe(g);
case t_COMPLEX:
return isnull(gel(g,1)) && isnull(gel(g,2));
+    case t_FFELT:
+      return FF_cmp0(g);
return isnull(gel(g,2)) && isnull(gel(g,3));
case t_FRAC: case t_RFRAC:
@@ -1691,6 +1700,8 @@
return (signe(g)<0)? -1: 1;
case t_FRAC: case t_RFRAC:
return isfactor(gel(g,1));
+    case t_FFELT:
+      return isfactor(FF_to_FpXQ(g));
case t_COMPLEX:
if (isnull(gel(g,1))) return isfactor(gel(g,2));
if (isnull(gel(g,2))) return isfactor(gel(g,1));
@@ -1967,6 +1978,10 @@
bruti(gel(g,2),T,1); comma_sp(T);
bruti(gel(g,1),T,1); pariputc(')'); break;

+    case t_FFELT:
+      break;
+
case t_FRAC: case t_RFRAC:
r = isfactor(gel(g,1)); if (!r) pariputc('(');
Index: src/language/init.c
===================================================================
RCS file: /home/cvs/pari/src/language/init.c,v
retrieving revision 1.330
diff -u -r1.330 init.c
--- src/language/init.c	3 Nov 2006 08:23:02 -0000	1.330
+++ src/language/init.c	3 Mar 2007 17:31:45 -0000
@@ -1203,7 +1203,7 @@
/*                                                                 */
/*******************************************************************/
/* lontyp[tx] = 0 (non recursive type) or number of codewords for type tx */
-const  long lontyp[] = { 0,0,0,1,1,1,1,2,1,1, 2,2,0,1,1,1,1,1,1,1, 2,0,0 };
+const  long lontyp[] = { 0,0,0,1,1,2,1,2,1,1, 2,2,0,1,1,1,1,1,1,1, 2,0,0 };
#define LG(x, tx) tx == t_LIST? lgeflist(x): lg(x)

/* x is a t_INT equal to 0 ? tx == t_INT && lx == 2 */
--- /dev/null	2006-05-11 11:25:12.000000000 +0200
+++ src/basemath/ffelt.c	2007-03-12 21:47:02.000000000 +0100
@@ -0,0 +1,587 @@
+/* \$Id: ffelt.c,v 1.60 2006/09/29 13:07:40 kb Exp \$
+
+Copyright (C) 2000-2003  The PARI group.
+
+This file is part of the PARI/GP package.
+
+PARI/GP is free software; you can redistribute it and/or modify it under the
+terms of the GNU General Public License as published by the Free Software
+Foundation. It is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY WHATSOEVER.
+
+Check the License for details. You should have received a copy of it, along
+with the package; see the file 'COPYING'. If not, write to the Free Software
+Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
+
+#include "pari.h"
+#include "paripriv.h"
+
+/*************************************************************************/
+/**                                                                     **/
+/**                   Routines for handling FFELT                       **/
+/**                                                                     **/
+/*************************************************************************/
+
+INLINE void
+_getFF(GEN x, GEN *T, GEN *p, ulong *pp)
+{
+  *T=gel(x,3);
+  *p=gel(x,4);
+  *pp=(ulong)x[1];
+}
+
+
+INLINE GEN
+_initFF(GEN x, GEN *T, GEN *p, ulong *pp)
+{
+  _getFF(x,T,p,pp);
+  return cgetg(5,t_FFELT);
+}
+
+INLINE void
+_checkFF(GEN x, GEN y, const char *s)
+{
+  if (x[1]!=y[1] || !equalii(gel(x,4),gel(y,4)) || !gequal(gel(x,3),gel(y,3)))
+    pari_err(operi,s,x,y);
+}
+
+
+INLINE GEN
+_mkFF(GEN x, GEN z, GEN r)
+{
+  z[1]=x[1];
+  gel(z,2)=r;
+  gel(z,3)=gcopy(gel(x,3));
+  gel(z,4)=icopy(gel(x,4));
+  return z;
+}
+
+INLINE GEN
+_mkFF_i(GEN x, GEN z, GEN r)
+{
+  z[1]=x[1];
+  gel(z,2)=r;
+  gel(z,3)=gel(x,3);
+  gel(z,4)=gel(x,4);
+  return z;
+}
+
+
+/* Return true if x and y are defined in the same field */
+
+int
+FF_samefield(GEN x, GEN y)
+{
+  return x[1] == y[1] && equalii(gel(x,4),gel(y,4))
+                      && gequal(gel(x,3),gel(y,3));
+}
+
+int
+FF_equal(GEN x, GEN y)
+{
+  return x[1] == y[1] && equalii(gel(x,4),gel(y,4))
+                      && gequal(gel(x,3),gel(y,3))
+                      && gequal(gel(x,2),gel(y,2));
+}
+
+int
+FF_cmp0(GEN x)
+{
+  return lgpol(gel(x,2))==0;
+}
+
+int
+FF_cmp1(GEN x)
+{
+  switch(x[1])
+  {
+  case 0:
+    return gcmp1(gel(x,2));
+  default:
+    return degpol(gel(x,2))==0 && mael(x,2,2)==1;
+  }
+}
+
+int
+FF_cmp_1(GEN x)
+{
+  GEN p=gel(x,4);
+  int b;
+  switch(x[1])
+  {
+  case 0:
+    {
+      pari_sp ltop=avma;
+      avma=ltop;
+      break;
+    }
+  default:
+    b=degpol(gel(x,2))==0 && mael(x,2,2)==x[1]-1;
+  }
+  return b;
+}
+
+GEN
+FF_zero(GEN x)
+{
+  ulong pp;
+  GEN r, T, p, z=_initFF(x,&T,&p,&pp);
+  switch(x[1])
+  {
+  case 0:
+    r=zeropol(varn(T));
+    break;
+  default:
+    r=zero_Flx(T[1]);
+  }
+  return _mkFF(x,z,r);
+}
+
+GEN
+FF_1(GEN x)
+{
+  ulong pp;
+  GEN r, T, p, z=_initFF(x,&T,&p,&pp);
+  switch(x[1])
+  {
+  case 0:
+    r=pol_1(varn(T));
+    break;
+  default:
+    r=Fl_to_Flx(1UL,T[1]);
+  }
+  return _mkFF(x,z,r);
+}
+
+GEN
+FF_to_FpXQ(GEN x)
+{
+  switch(x[1])
+  {
+  case 0:
+    return gel(x,2);
+  default:
+    return Flx_to_ZX(gel(x,2));
+  }
+}
+
+GEN
+FF_add(GEN x, GEN y)
+{
+  ulong pp;
+  GEN r, T, p, z=_initFF(x,&T,&p,&pp);
+  _checkFF(x,y,"+");
+  switch(x[1])
+  {
+  case 0:
+    {
+      pari_sp av=avma;
+      break;
+    }
+  default:
+  }
+  return _mkFF(x,z,r);
+}
+
+GEN
+FF_Z_add(GEN x, GEN y)
+{
+  ulong pp;
+  GEN r, T, p, z=_initFF(x,&T,&p,&pp);
+  switch(x[1])
+  {
+  case 0:
+    {
+      pari_sp av=avma;
+      break;
+    }
+  default:
+  }
+  return _mkFF(x,z,r);
+}
+
+GEN
+FF_neg(GEN x)
+{
+  ulong pp;
+  GEN r, T, p, z=_initFF(x,&T,&p,&pp);
+  switch(x[1])
+  {
+  case 0:
+    r=FpX_neg(gel(x,2),p);
+    break;
+  default:
+    r=Flx_neg(gel(x,2),pp);
+  }
+  return _mkFF(x,z,r);
+}
+
+GEN
+FF_neg_i(GEN x)
+{
+  ulong pp;
+  GEN r, T, p, z=_initFF(x,&T,&p,&pp);
+  switch(pp)
+  {
+  case 0:
+    r=FpX_neg(gel(x,2),p);
+    break;
+  default:
+    r=Flx_neg(gel(x,2),pp);
+  }
+  return _mkFF_i(x,z,r);
+}
+
+GEN
+FF_mul(GEN x, GEN y)
+{
+  ulong pp;
+  GEN r, T, p, z=_initFF(x,&T,&p,&pp);
+  _checkFF(x,y,"*");
+  switch(x[1])
+  {
+  case 0:
+    {
+      pari_sp av=avma;
+      r=gerepileupto(av,FpXQ_mul(gel(x,2),gel(y,2),T,p));
+      break;
+    }
+  default:
+    r=Flxq_mul(gel(x,2),gel(y,2),T,pp);
+  }
+  return _mkFF(x,z,r);
+}
+
+GEN
+FF_Z_mul(GEN x, GEN y)
+{
+  ulong pp;
+  GEN r, T, p, z=_initFF(x,&T,&p,&pp);
+  switch(x[1])
+  {
+  case 0:
+    {
+      pari_sp av=avma;
+      r=gerepileupto(av,FpX_Fp_mul(gel(x,2),modii(y,p),p));
+      break;
+    }
+  default:
+    r=Flx_Fl_mul(gel(x,2),umodiu(y,pp),pp);
+  }
+  return _mkFF(x,z,r);
+}
+
+GEN
+FF_Z_Z_muldiv(GEN x, GEN a, GEN b)
+{
+  ulong pp;
+  GEN r, T, p, z=_initFF(x,&T,&p,&pp);
+  pari_sp av=avma;
+  switch(x[1])
+  {
+  case 0:
+    r=gerepileupto(av,FpX_Fp_mul(gel(x,2),Fp_div(a,b,p),p));
+    break;
+  default:
+    r=gerepileupto(av,Flx_Fl_mul(gel(x,2),Fl_div(umodiu(a,pp),umodiu(b,pp),pp),pp));
+  }
+  return _mkFF(x,z,r);
+}
+
+GEN
+FF_sqr(GEN x)
+{
+  ulong pp;
+  GEN r, T, p, z=_initFF(x,&T,&p,&pp);
+  switch(x[1])
+  {
+  case 0:
+    {
+      pari_sp av=avma;
+      r=gerepileupto(av,FpXQ_sqr(gel(x,2),T,p));
+      break;
+    }
+  default:
+    r=Flxq_sqr(gel(x,2),T,pp);
+  }
+  return _mkFF(x,z,r);
+}
+
+GEN
+FF_mul2n(GEN x, long n)
+{
+  ulong pp;
+  GEN r, T, p, z=_initFF(x,&T,&p,&pp);
+  pari_sp av=avma;
+  switch(x[1])
+  {
+  case 0:
+    {
+      GEN p1;
+      if (n>0) p1=remii(int2n(n),p);
+      else p1=Fp_inv(remii(int2n(-n),p),p);
+      r=gerepileupto(av,FpX_Fp_mul(gel(x,2),p1,p));
+    }
+    break;
+  default:
+    {
+      ulong l1;
+      if (n>0) l1=umodiu(int2n(n),pp);
+      else l1=Fl_inv(umodiu(int2n(-n),pp),pp);
+      r=gerepileupto(av,Flx_Fl_mul(gel(x,2),l1,pp));
+    }
+  }
+  return _mkFF(x,z,r);
+}
+
+GEN
+FF_inv(GEN x)
+{
+  ulong pp;
+  GEN r, T, p, z=_initFF(x,&T,&p,&pp);
+  pari_sp av=avma;
+  switch(x[1])
+  {
+  case 0:
+    r=gerepileupto(av,FpXQ_inv(gel(x,2),T,p));
+    break;
+  default:
+    r=Flxq_inv(gel(x,2),T,pp);
+  }
+  return _mkFF(x,z,r);
+}
+
+GEN
+FF_div(GEN x, GEN y)
+{
+  ulong pp;
+  GEN r, T, p, z=_initFF(x,&T,&p,&pp);
+  pari_sp av=avma;
+  _checkFF(x,y,"/");
+  switch(x[1])
+  {
+  case 0:
+    r=gerepileupto(av,FpXQ_mul(gel(x,2), FpXQ_inv(gel(y,2),T,p),T,p));
+    break;
+  default:
+    r=gerepileupto(av,Flxq_mul(gel(x,2), Flxq_inv(gel(y,2),T,pp),T,pp));
+  }
+  return _mkFF(x,z,r);
+}
+
+GEN
+Z_FF_div(GEN n, GEN x)
+{
+  ulong pp;
+  GEN r, T, p, z=_initFF(x,&T,&p,&pp);
+  pari_sp av=avma;
+  switch(x[1])
+  {
+  case 0:
+    r=gerepileupto(av,FpX_Fp_mul(FpXQ_inv(gel(x,2),T,p),modii(n,p),p));
+    break;
+  default:
+    r=gerepileupto(av,Flx_Fl_mul(Flxq_inv(gel(x,2),T,pp),umodiu(n,pp),pp));
+  }
+  return _mkFF(x,z,r);
+}
+
+GEN
+FF_sqrtn(GEN x, GEN n, GEN *zetan)
+{
+  ulong pp;
+  GEN r, T, p, y=_initFF(x,&T,&p,&pp);
+  switch (x[1])
+  {
+  case 0:
+    r=FpXQ_sqrtn(gel(x,2),n,T,p,zetan);
+    if (!r)
+      pari_err(talker,"nth-root does not exist in FF_sqrtn");
+    break;
+  default:
+    r=FpXQ_sqrtn(Flx_to_ZX(gel(x,2)),n,Flx_to_ZX(T),p,zetan);
+    if (!r)
+      pari_err(talker,"nth-root does not exist in FF_sqrtn");
+    r=ZX_to_Flx(r,pp);
+  }
+  _mkFF(x, y, r);
+  if (zetan)
+  {
+    GEN z = cgetg(lg(y),t_FFELT);
+    if (x[1]) *zetan=ZX_to_Flx(*zetan,pp);
+    *zetan=_mkFF(x, z, *zetan);
+  }
+  return y;
+}
+
+GEN
+FF_sqrt(GEN x)
+{
+  return FF_sqrtn(x,gen_2,NULL);
+}
+
+GEN
+FF_pow(GEN x, GEN n)
+{
+  ulong pp;
+  GEN r, T, p, z=_initFF(x,&T,&p,&pp);
+  switch(x[1])
+   {
+   case 0:
+     r = FpXQ_pow(gel(x,2), n, T, p);
+     break;
+   default:
+     r = Flxq_pow(gel(x,2), n, T, pp);
+   }
+  return _mkFF(x,z,r);
+}
+
+GEN
+FF_norm(GEN x)
+{
+  ulong pp;
+  GEN T,p;
+  _getFF(x,&T,&p,&pp);
+  switch (x[1])
+  {
+  case 0:
+    return FpXQ_norm(gel(x,2),T,p);
+  default:
+    return utoi(Flxq_norm(gel(x,2),T,pp));
+  }
+}
+
+GEN
+FF_trace(GEN x)
+{
+  ulong pp;
+  GEN r,T,p;
+  pari_sp av;
+  _getFF(x,&T,&p,&pp);
+  av = avma;
+  switch(x[1])
+  {
+  case 0:
+    r = quicktrace(gel(x,2), polsym(T, degpol(T)-1));
+    break;
+  default:
+    r = quicktrace(Flx_to_ZX(gel(x,2)), polsym(Flx_to_ZX(T), degpol(T)-1));
+  }
+  return gerepileupto(av, modii(r,p));
+}
+
+GEN
+FF_charpoly(GEN x)
+{
+  ulong pp;
+  GEN T,p;
+  pari_sp av=avma;
+  _getFF(x,&T,&p,&pp);
+  switch(x[1])
+  {
+  case 0:
+    return gerepileupto(av,FpXQ_charpoly(gel(x,2), T, p));
+  default:
+    return gerepileupto(av,Flx_to_ZX(Flxq_charpoly(gel(x,2), T, pp)));
+  }
+}
+
+GEN
+FF_minpoly(GEN x)
+{
+  ulong pp;
+  GEN T,p;
+  pari_sp av=avma;
+  _getFF(x,&T,&p,&pp);
+  switch(x[1])
+  {
+  case 0:
+    return gerepileupto(av,FpXQ_minpoly(gel(x,2), T, p));
+  default:
+    return gerepileupto(av,Flx_to_ZX(Flxq_minpoly(gel(x,2), T, pp)));
+  }
+}
+
+static GEN
+to_FF(GEN x, GEN ff)
+{
+  if (typ(x) == t_INT) return x;
+  else
+  {
+    GEN z=cgetg(5, t_FFELT);
+    GEN r;
+    switch(x[1])
+    {
+    case 0:
+      r=x;
+      break;
+    default:
+      r=ZX_to_Flx(x,ff[1]);
+    }
+    return _mkFF_i(ff,z,r);
+  }
+}
+
+static GEN
+to_FF_pol(GEN x, GEN ff)
+{
+  long i, lx, tx = typ(x);
+  if (tx != t_POL) pari_err(typeer,"to_FF_pol");
+  lx = lg(x);
+  for (i=2; i<lx; i++) gel(x,i) = to_FF(gel(x,i), ff);
+  return x;
+}
+
+static GEN
+to_FF_fact(GEN P, GEN E, GEN ff, pari_sp av)
+{
+  GEN y = cgetg(3,t_MAT), u, v, zf;
+  long j, l = lg(P), nbf = lg(P);
+
+  u = cgetg(nbf,t_COL); gel(y,1) = u;
+  v = cgetg(nbf,t_COL); gel(y,2) = v;
+  for (j=1; j<l; j++)
+  {
+    gel(u,j) = simplify_i(gel(P,j)); /* may contain pols of degree 0 */
+    gel(v,j) = utoi((ulong)E[j]);
+  }
+  y = gerepilecopy(av, y); u = gel(y,1);
+  zf = FF_zero(ff);
+  for (j=1; j<nbf; j++) gel(u,j) = to_FF_pol(gel(u,j), zf);
+  return y;
+}
+
+/*Warning: FFX are polynomials whose coefficients are compatible with FF:
+ * t_INT t_INTMOD, t_FFELT*/
+
+static GEN
+FFX_to_FqX(GEN x, GEN T, GEN p)
+{
+  long i, l = lg(x);
+  GEN z = cgetg(l, t_POL); z[1] = x[1];
+  for (i = 2; i < l; i++)
+    if (typ(gel(x,i))==t_FFELT)
+      gel(z,i) = simplify_i(FF_to_FpXQ(gel(x,i)));
+    else
+      gel(z,i) = simplify_i(Rg_to_FpXQ(gel(x,i), T,p));
+  return normalizepol_i(z, l);
+}
+
+/* Factor P over the field of definition of x */
+GEN
+FFX_factor(GEN P, GEN x)
+{
+  ulong pp;
+  GEN r, T, p;
+  pari_sp av=avma;
+  _getFF(x,&T,&p,&pp);
+  if (x[1]) T=Flx_to_ZX(T);
+  r = FqX_factor(FFX_to_FqX(P, T,p), T,p);