| Bill Allombert on Sat, 24 Mar 2007 00:38:33 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
| PARI/GP support for finite fields element v2 |
Hello PARI-dev, Please find an improved version of my patch (in attachment) that add support for 'finite field elements' to PARI/GP. This version add the following GP function to deal with the multiplicative group of finite fields: fflog, fforder, ffprimroot ? a=ffgen(ffinit(2,8),a) %1 = a ? b=ffprimroot(a) %2 = a^7 + a^6 + a^4 + a ? fflog(a,b) %3 = 168 ? minpoly(b) %4 = Mod(1, 2)*x^8 + Mod(1, 2)*x^7 + Mod(1, 2)*x^5 + Mod(1, 2)*x^3 + Mod(1, 2) Cheers, Bill.
Index: CHANGES
===================================================================
RCS file: /home/cvs/pari/CHANGES,v
retrieving revision 1.1702
diff -u -r1.1702 CHANGES
--- CHANGES 23 Mar 2007 20:47:51 -0000 1.1702
+++ CHANGES 23 Mar 2007 22:16:23 -0000
@@ -97,6 +97,9 @@
BA 18- [toplevel benchmark] ffisom
BA 19- library functions Fp_order, FpXQ_order, FpXQ_log, FpXQ_sqrtn,
Flxq_order, Flxq_log, Flxq_sqrtn
+BA 20- New PARI type t_FFELT and support functions (FF_*) for finite field
+ elements.
+BA 21- functions ffgen, fforder, fflog, ffprimroot for finite field elements.
Removed
1- obsolete functions readexpr(), readexpr_nobreak()
Index: src/basemath/alglin2.c
===================================================================
RCS file: /home/cvs/pari/src/basemath/alglin2.c,v
retrieving revision 1.236
diff -u -r1.236 alglin2.c
--- src/basemath/alglin2.c 21 Mar 2007 15:01:30 -0000 1.236
+++ src/basemath/alglin2.c 21 Mar 2007 16:42:42 -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:
return gadd(x, gconj(x));
Index: src/basemath/gen1.c
===================================================================
RCS file: /home/cvs/pari/src/basemath/gen1.c,v
retrieving revision 1.183
diff -u -r1.183 gen1.c
--- src/basemath/gen1.c 15 Mar 2007 23:32:18 -0000 1.183
+++ src/basemath/gen1.c 15 Mar 2007 23:36:06 -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_PADIC: return addQp(x,y);
case t_QUAD: return addRq(x, y);
+ case t_FFELT: return FF_Z_add(y,x);
}
case t_REAL:
@@ -838,6 +840,10 @@
p1 = Fp_div(gel(y,1), gel(y,2), 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);
+ return FF_Z_add(y,gel(x,2));
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);
case t_QUAD:
@@ -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);
case t_PADIC:
@@ -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);
+
case t_QUAD: y=cgetg(4,t_QUAD); y[1]=x[1];
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);
+
case t_PADIC:
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.444
diff -u -r1.444 polarit2.c
--- src/basemath/polarit2.c 15 Mar 2007 23:32:18 -0000 1.444
+++ src/basemath/polarit2.c 23 Mar 2007 22:52:15 -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[11]: t_QUAD of t_PADIC
* 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_PADIC: return factorpadic4(x,p,pa);
+
+ case t_FFELT: return FFX_factor(x,pol);
default:
{
@@ -4522,3 +4537,56 @@
}
return gerepilecopy(ltop, sol);
}
+
+GEN ffgen(GEN T, long v)
+{
+ 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 (v<0) v=varn(T);
+ if (lgefint(p)==3)
+ {
+ ulong pp=p[2];
+ long sv=evalvarn(v);
+ ff[1]=t_FF_Flxq;
+ gel(ff,2)=polx_Flx(sv);
+ gel(ff,3)=ZX_to_Flx(lift(T),pp);
+ mael(ff,3,1)=sv;
+ gel(ff,4)=icopy(p);
+ }
+ else
+ {
+ ff[1]=t_FF_FpXQ;
+ gel(ff,2)=pol_x(v);
+ gel(ff,3)=lift(T);
+ setvarn(gel(ff,3),v);
+ gel(ff,4)=icopy(p);
+ }
+ return ff;
+}
+
+GEN fforder(GEN x, GEN o)
+{
+ if (typ(x)!=t_FFELT || (o && typ(o)!=t_INT))
+ pari_err(typeer,"fforder");
+ return FF_order(x,o);
+}
+
+GEN ffprimroot(GEN x)
+{
+ if (typ(x)!=t_FFELT)
+ pari_err(typeer,"ffprimroot");
+ return FF_primroot(x);
+}
+
+GEN fflog(GEN x, GEN g)
+{
+ if (typ(x)!=t_FFELT || typ(g)!=t_FFELT)
+ pari_err(typeer,"fflog");
+ return FF_log(x,g);
+}
+
Index: src/basemath/trans1.c
===================================================================
RCS file: /home/cvs/pari/src/basemath/trans1.c,v
retrieving revision 1.224
diff -u -r1.224 trans1.c
--- src/basemath/trans1.c 23 Mar 2007 20:47:54 -0000 1.224
+++ src/basemath/trans1.c 23 Mar 2007 20:48:00 -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)
- {
+
+ case 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_PADIC:
return padic_sqrt(x);
+ 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)
Index: src/headers/paridecl.h
===================================================================
RCS file: /home/cvs/pari/src/headers/paridecl.h,v
retrieving revision 1.641
diff -u -r1.641 paridecl.h
--- src/headers/paridecl.h 23 Mar 2007 20:47:54 -0000 1.641
+++ src/headers/paridecl.h 23 Mar 2007 22:50:05 -0000
@@ -1067,6 +1067,39 @@
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_log(GEN a, GEN b);
+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_order(GEN x, GEN o);
+GEN FF_pow(GEN x, GEN n);
+GEN FF_primroot(GEN x);
+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);
@@ -1639,6 +1672,10 @@
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, long v);
+GEN fflog(GEN x, GEN g);
+GEN fforder(GEN x, GEN o);
+GEN ffprimroot(GEN x);
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);
Index: src/headers/paripriv.h
===================================================================
RCS file: /home/cvs/pari/src/headers/paripriv.h,v
retrieving revision 1.136
diff -u -r1.136 paripriv.h
--- src/headers/paripriv.h 23 Mar 2007 20:47:54 -0000 1.136
+++ src/headers/paripriv.h 23 Mar 2007 20:57:38 -0000
@@ -307,6 +307,10 @@
GEN vandermondeinversemod(GEN L, GEN T, GEN den, GEN mod);
GEN ZX_monic_factorpadic(GEN f, GEN p, long prec);
+/* Finite field */
+
+enum { t_FF_FpXQ = 0, t_FF_Flxq =1 };
+
#include "parinf.h"
/* Allocation / gerepile */
Index: src/headers/paritype.h
===================================================================
RCS file: /home/cvs/pari/src/headers/paritype.h,v
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,
t_PADIC = 7,
t_QUAD = 8,
Index: src/kernel/none/level1.h
===================================================================
RCS file: /home/cvs/pari/src/kernel/none/level1.h,v
retrieving revision 1.122
diff -u -r1.122 level1.h
--- src/kernel/none/level1.h 18 Mar 2007 22:40:50 -0000 1.122
+++ src/kernel/none/level1.h 18 Mar 2007 22:51:10 -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);
@@ -1255,6 +1256,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;
case t_PADIC : s="t_PADIC"; break;
case t_QUAD : s="t_QUAD"; 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);
case t_QUAD:
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:
+ bruti(FF_to_FpXQ(g),T,addsign);
+ break;
+
case t_FRAC: case t_RFRAC:
r = isfactor(gel(g,1)); if (!r) pariputc('(');
bruti(gel(g,1),T,addsign);
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/FF.c 2007-03-23 23:06:56.000000000 +0100
@@ -0,0 +1,641 @@
+/* $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=mael(x,4,2);
+}
+
+
+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 t_FF_FpXQ:
+ return gcmp1(gel(x,2));
+ default:
+ return degpol(gel(x,2))==0 && mael(x,2,2)==1;
+ }
+}
+
+int
+FF_cmp_1(GEN x)
+{
+ ulong pp;
+ GEN T, p;
+ _getFF(x,&T,&p,&pp);
+ int b;
+ switch(x[1])
+ {
+ case t_FF_FpXQ:
+ {
+ pari_sp ltop=avma;
+ b=gequal(gel(x,2),addis(p,-1));
+ avma=ltop;
+ break;
+ }
+ default:
+ b=(degpol(gel(x,2))==0 && mael(x,2,2)==pp-1);
+ }
+ return b;
+}
+
+GEN
+FF_zero(GEN x)
+{
+ ulong pp;
+ GEN r, T, p, z=_initFF(x,&T,&p,&pp);
+ switch(x[1])
+ {
+ case t_FF_FpXQ:
+ 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 t_FF_FpXQ:
+ 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 t_FF_FpXQ:
+ 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 t_FF_FpXQ:
+ {
+ pari_sp av=avma;
+ r=gerepileupto(av,FpX_add(gel(x,2),gel(y,2),p));
+ break;
+ }
+ default:
+ r=Flx_add(gel(x,2),gel(y,2),pp);
+ }
+ 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 t_FF_FpXQ:
+ {
+ pari_sp av=avma;
+ r=gerepileupto(av,FpX_Fp_add(gel(x,2),modii(y,p),p));
+ break;
+ }
+ default:
+ r=Flx_Fl_add(gel(x,2),umodiu(y,pp),pp);
+ }
+ 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 t_FF_FpXQ:
+ 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(x[1])
+ {
+ case t_FF_FpXQ:
+ 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 t_FF_FpXQ:
+ {
+ 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 t_FF_FpXQ:
+ {
+ 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 t_FF_FpXQ:
+ 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 t_FF_FpXQ:
+ {
+ 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 t_FF_FpXQ:
+ {
+ 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 t_FF_FpXQ:
+ 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 t_FF_FpXQ:
+ r=gerepileupto(av,FpXQ_div(gel(x,2),gel(y,2),T,p));
+ break;
+ default:
+ r=gerepileupto(av,Flxq_div(gel(x,2),gel(y,2),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 t_FF_FpXQ:
+ 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 t_FF_FpXQ:
+ r=FpXQ_sqrtn(gel(x,2),n,T,p,zetan);
+ break;
+ default:
+ r=Flxq_sqrtn(gel(x,2),n,T,pp,zetan);
+ }
+ if (!r)
+ pari_err(talker,"nth-root does not exist in FF_sqrtn");
+ _mkFF(x, y, r);
+ if (zetan)
+ {
+ GEN z = cgetg(lg(y),t_FFELT);
+ *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 t_FF_FpXQ:
+ 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 t_FF_FpXQ:
+ 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 t_FF_FpXQ:
+ 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 t_FF_FpXQ:
+ 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 t_FF_FpXQ:
+ return gerepileupto(av,FpXQ_minpoly(gel(x,2), T, p));
+ default:
+ return gerepileupto(av,Flx_to_ZX(Flxq_minpoly(gel(x,2), T, pp)));
+ }
+}
+
+GEN
+FF_log(GEN x, GEN g)
+{
+ pari_sp av=avma;
+ ulong pp;
+ GEN r,ord,T,p;
+ _getFF(x,&T,&p,&pp);
+ _checkFF(x,g,"log");
+ switch(x[1])
+ {
+ case t_FF_FpXQ:
+ ord = addis(powiu(p,degpol(T)),-1);
+ r = FpXQ_log(gel(x,2), gel(g,2), ord, T, p);
+ default:
+ ord = addis(powuu(pp,degpol(T)),-1);
+ r = Flxq_log(gel(x,2), gel(g,2), ord, T, pp);
+ }
+ return gerepileuptoint(av, r);
+}
+
+GEN
+FF_order(GEN x, GEN o)
+{
+ pari_sp av=avma;
+ ulong pp;
+ GEN r, T,p;
+ _getFF(x,&T,&p,&pp);
+ switch(x[1])
+ {
+ case t_FF_FpXQ:
+ if (!o) o = addis(powiu(p,degpol(T)),-1);
+ r = FpXQ_order(gel(x,2), o, T, p);
+ break;
+ default:
+ if (!o) o = addis(powuu(pp,degpol(T)),-1);
+ r = Flxq_order(gel(x,2), o, T, pp);
+ }
+ if (!o) r = gerepileuptoint(av,r);
+ return r;
+}
+
+GEN
+FF_primroot(GEN x)
+{
+ ulong pp;
+ GEN r,T,p,z=_initFF(x,&T,&p,&pp);
+ switch(x[1])
+ {
+ case t_FF_FpXQ:
+ r = gener_FpXQ(T, p);
+ break;
+ default:
+ r = gener_Flxq(T, pp);
+ }
+ return _mkFF(x,z,r);
+}
+
+static GEN
+to_FF(GEN x, GEN ff)
+{
+ if (typ(x) == t_INT) return x;
+ else
+ {
+ ulong pp;
+ GEN r, T, p, z=_initFF(ff,&T,&p,&pp);
+ switch(ff[1])
+ {
+ case t_FF_FpXQ:
+ r=x;
+ break;
+ default:
+ r=ZX_to_Flx(x,pp);
+ }
+ 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);
+ return to_FF_fact(gel(r,1),gel(r,2), x,av);
+}
--- /dev/null 2006-05-11 11:25:12.000000000 +0200
+++ src/functions/number_theoretical/ffgen 2007-03-23 23:54:45.000000000 +0100
@@ -0,0 +1,8 @@
+Function: ffgen
+Section: number_theoretical
+C-Name: ffgen
+Prototype: GDn
+Help: ffgen(P,{v}): return the generator g=X mod P(X) of the finite field
+ defined by the polynomial P(X). If v is given, the variable name is used to
+ display g, else the variable of the polynomial P is used.
+
--- /dev/null 2006-05-11 11:25:12.000000000 +0200
+++ src/functions/number_theoretical/fflog 2007-03-23 23:00:02.000000000 +0100
@@ -0,0 +1,6 @@
+Function: fflog
+Section: number_theoretical
+C-Name: fflog
+Prototype: GG
+Help: fflog(x,g): return the discrete logarithm of the finite field element x in base g
+
--- /dev/null 2006-05-11 11:25:12.000000000 +0200
+++ src/functions/number_theoretical/fforder 2007-03-23 22:58:37.000000000 +0100
@@ -0,0 +1,7 @@
+Function: fforder
+Section: number_theoretical
+C-Name: fforder
+Prototype: GDG
+Help: fforder(x,{o}): multiplicative of the finite field element x. Optional o
+ is assumed to be a multiple of the order
+
--- /dev/null 2006-05-11 11:25:12.000000000 +0200
+++ src/functions/number_theoretical/ffprimroot 2007-03-20 23:47:37.000000000 +0100
@@ -0,0 +1,8 @@
+Function: ffprimroot
+Section: number_theoretical
+C-Name: ffprimroot
+Prototype: G
+Help: ffprimroot(x): return a primitive root of the multiplicative group of the
+ definition field of the finite field element x (not necessarily the same as
+ the field generated by x)
+