| 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:
return gadd(x, gconj(x));
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_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 = 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);
+ 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.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[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,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)
- {
+
+ 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.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);
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.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;
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/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;
+ b=gequal(gel(x,2),addis(p,-1));
+ 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;
+ 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 0:
+ {
+ 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 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);
+ 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-03 17:50:16.000000000 +0100
@@ -0,0 +1,7 @@
+Function: ffgen
+Section: number_theoretical
+C-Name: ffgen
+Prototype: G
+Help: ffelt(P): return the generator X mod P(X) of the finite field defined
+ by P.
+