| Bill Allombert on Sat, 01 Sep 2007 18:21:14 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
| [patch] FFELT format for finite fields of characteristic 2 |
Hello PARI dev, This (-p1) patch implements a new FFELT format for finite field of characteristic 2. Example of use: a=ffgen(ffinit(2,32,a)); a^15 This patch also adds two new class of functions, F2x and F2xq. F2x objects are defined as follows: An F2x is a t_VECSMALL: x[0] = codeword x[1] = evalvarn(variable number) (signe is not stored). x[2] = a_0...a_31 x[3] = a_32..a_63, etc. on 32bit systems. x[2] = a_0...a_63 x[3] = a_64..a_127, etc. on 64bit systems. where the a_i are bits. Note: F2x(0)=Flx(0 mod 2) ans F2x(1)=Flx(1 mod 2) Limitation: 1) Only straightforward algorithms are implemented. 2) Resultants are not implemented. Cheers, Bill.
Index: parigp3/doc/usersch4.tex
===================================================================
--- parigp3.orig/doc/usersch4.tex 2007-09-01 14:45:01.000000000 +0200
+++ parigp3/doc/usersch4.tex 2007-09-01 14:46:33.000000000 +0200
@@ -1202,6 +1202,11 @@
modulo $p$, and the degree of $A$ is strictly less than the degree of $T$.
This represents the element $A\pmod{T}$ in $\F_l[X]/T$.
+The format \tet{t_FF_F2xq}:\kbd{A=z[2]} and \kbd{T=z[3]} are \kbd{F2x},
+\kbd{l=z[4]} is the \typ{INT} $2$, $T$ is irreducible
+modulo $2$, and the degree of $A$ is strictly less than the degree of $T$.
+This represents the element $A\pmod{T}$ in $\F_2[X]/T$.
+
\subsec{Type \typ{COMPLEX} (complex number)}:%
\kbdsidx{t_COMPLEX}\sidx{complex number}
\kbd{z[1]} points to the real part, and \kbd{z[2]} to the imaginary part.
Index: parigp3/src/basemath/F2x.c
===================================================================
--- /dev/null 1970-01-01 00:00:00.000000000 +0000
+++ parigp3/src/basemath/F2x.c 2007-09-01 17:57:13.000000000 +0200
@@ -0,0 +1,612 @@
+/* $Id: F2x.c,v 1.78 2007/03/06 20:47:09 bill Exp $
+
+Copyright (C) 2007 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"
+
+/* Not so fast arithmetic with polynomials over F_2 */
+
+/***********************************************************************/
+/** **/
+/** F2x **/
+/** **/
+/***********************************************************************/
+/* F2x objects are defined as follows:
+ An F2x is a t_VECSMALL:
+ x[0] = codeword
+ x[1] = evalvarn(variable number) (signe is not stored).
+ x[2] = a_0...a_31 x[3] = a_32..a_63, etc. on 32bit
+ x[2] = a_0...a_63 x[3] = a_64..a_127, etc. on 64bit
+
+ where the a_i are bits.
+
+ signe(x) is not valid. Use degpol(x)>=0 instead.
+ Note: F2x(0)=Flx(0 mod 2) ans F2x(1)=Flx(1 mod 2)
+*/
+
+GEN
+pol1_F2x(long sv) { return mkvecsmall2(sv, 1); }
+
+GEN
+polx_F2x(long sv) { return mkvecsmall2(sv, 2); }
+
+INLINE long
+F2x_degree_lg(GEN x, long l)
+{
+ if (l==2) return -1;
+ else return ((l-3)<<TWOPOTBITS_IN_LONG)+BITS_IN_LONG-1-bfffo(x[l-1]);
+}
+
+long
+F2x_degree(GEN x)
+{
+ return F2x_degree_lg(x, lg(x));
+}
+
+INLINE ulong
+F2x_get_coeff(GEN x,long v)
+{
+ ulong u=(ulong)x[2+(v>>TWOPOTBITS_IN_LONG)];
+ return (u>>(v&(BITS_IN_LONG-1)))&1UL;
+}
+
+INLINE void
+F2x_set_coeff(GEN x,long v)
+{
+ ulong* u=(ulong*)&x[2+(v>>TWOPOTBITS_IN_LONG)];
+ *u^=1UL<<(v&(BITS_IN_LONG-1UL));
+}
+
+GEN
+F2x_to_ZX(GEN x)
+{
+ long l=3+F2x_degree(x);
+ GEN z=cgetg(l,t_POL);
+ long i,j,k;
+ for(i=2,k=2;i<lg(x);i++)
+ for(j=0; j<BITS_IN_LONG && k<l; j++,k++)
+ gel(z,k)=(x[i]&(1UL<<j))?gen_1:gen_0;
+ z[1]=evalsigne(l>=0)|x[1];
+ return z;
+}
+
+GEN
+F2x_to_Flx(GEN x)
+{
+ long l=3+F2x_degree(x);
+ GEN z=cgetg(l,t_VECSMALL);
+ long i,j,k;
+ z[1]=x[1];
+ for(i=2,k=2;i<lg(x);i++)
+ for(j=0;j<BITS_IN_LONG && k<l; j++,k++)
+ z[k]=(x[i]>>j)&1UL;
+ return z;
+}
+
+GEN
+ZX_to_F2x(GEN x)
+{
+ long l=(lgpol(x)+BITS_IN_LONG-1)>>TWOPOTBITS_IN_LONG;
+ GEN z=cgetg(2+l,t_VECSMALL);
+ long i,j,k;
+ z[1]=((ulong)x[1])&VARNBITS;
+ for(i=2, k=1,j=BITS_IN_LONG;i<lg(x);i++,j++)
+ {
+ if (j==BITS_IN_LONG)
+ {
+ j=0; k++; z[k]=0;
+ }
+ if (mod2(gel(x,i)))
+ z[k]|=1UL<<j;
+ }
+ return F2x_renormalize(z,2+l);
+}
+
+GEN
+Flx_to_F2x(GEN x)
+{
+ long l=(lgpol(x)+BITS_IN_LONG-1)>>TWOPOTBITS_IN_LONG;
+ GEN z=cgetg(2+l,t_VECSMALL);
+ long i,j,k;
+ z[1]=x[1];
+ for(i=2, k=1,j=BITS_IN_LONG;i<lg(x);i++,j++)
+ {
+ if (j==BITS_IN_LONG)
+ {
+ j=0; k++; z[k]=0;
+ }
+ if (x[i])
+ z[k]|=(1<<j);
+ }
+ return F2x_renormalize(z,2+l);
+}
+
+GEN
+F2x_add(GEN x, GEN y)
+{
+ long i,lz;
+ GEN z;
+ long lx=lg(x);
+ long ly=lg(y);
+ if (ly>lx) swapspec(x,y, lx,ly);
+ lz = lx; z = cgetg(lz, t_VECSMALL); z[1]=x[1];
+ for (i=2; i<ly; i++) z[i] = x[i]^y[i];
+ for ( ; i<lx; i++) z[i] = x[i];
+ return F2x_renormalize(z, lz);
+}
+
+GEN
+F2x_addspec(GEN x, GEN y, long lx, long ly)
+{
+ long i,lz;
+ GEN z;
+
+ if (ly>lx) swapspec(x,y, lx,ly);
+ lz = lx+2; z = cgetg(lz, t_VECSMALL) + 2;
+ for (i=0; i<ly; i++) z[i] = x[i]^y[i];
+ for ( ; i<lx; i++) z[i] = x[i];
+ z -= 2; return F2x_renormalize(z, lz);
+}
+
+GEN
+F2x_1_add(GEN y)
+{
+ GEN z;
+ long lz, i;
+ if (!lgpol(y))
+ return pol1_F2x(y[1]);
+ lz=lg(y);
+ z=cgetg(lz,t_VECSMALL);
+ z[1] = y[1];
+ z[2] = y[2]^1UL;
+ for(i=3;i<lz;i++)
+ z[i] = y[i];
+ if (lz==3) z = F2x_renormalize(z,lz);
+ return z;
+}
+
+static GEN
+F2x_addshift(GEN x, GEN y, long d)
+{
+ GEN xd,yd,zd = (GEN)avma;
+ long a,lz,ny = lgpol(y), nx = lgpol(x);
+ long vs = x[1];
+
+ x += 2; y += 2; a = ny-d;
+ if (a <= 0)
+ {
+ lz = (a>nx)? ny+2: nx+d+2;
+ (void)new_chunk(lz); xd = x+nx; yd = y+ny;
+ while (xd > x) *--zd = *--xd;
+ x = zd + a;
+ while (zd > x) *--zd = 0;
+ }
+ else
+ {
+ xd = new_chunk(d); yd = y+d;
+ x = F2x_addspec(x,yd,nx,a);
+ lz = (a>nx)? ny+2: lg(x)+d;
+ x += 2; while (xd > x) *--zd = *--xd;
+ }
+ while (yd > y) *--zd = *--yd;
+ *--zd = vs;
+ *--zd = evaltyp(t_VECSMALL) | evallg(lz); return zd;
+}
+
+/* shift polynomial + gerepile */
+/* Do not set evalvarn*/
+static GEN
+F2x_shiftip(pari_sp av, GEN x, long v)
+{
+ long i, lx = lg(x), ly;
+ GEN y;
+ if (!v || lx==2) return gerepileuptoleaf(av, x);
+ avma = av; ly = lx + v;
+ x += lx; y = new_chunk(ly) + ly; /*cgetg could overwrite x!*/
+ for (i = 2; i<lx; i++) *--y = *--x;
+ for (i = 0; i< v; i++) *--y = 0;
+ y -= 2; y[0] = evaltyp(t_VECSMALL) | evallg(ly);
+ return y;
+}
+
+static GEN
+F2x_mul1(ulong x, ulong y)
+{
+ ulong x1=(x&HIGHMASK)>>BITS_IN_HALFULONG;
+ ulong x2=x&LOWMASK;
+ ulong y1=(y&HIGHMASK)>>BITS_IN_HALFULONG;
+ ulong y2=y&LOWMASK;
+ ulong r1,r2,rr;
+ GEN z;
+ ulong i;
+ rr=r1=r2=0UL;
+ if (x2)
+ for(i=0;i<BITS_IN_HALFULONG;i++)
+ if (x2&(1UL<<i))
+ {
+ r2^=y2<<i;
+ rr^=y1<<i;
+ }
+ if (x1)
+ for(i=0;i<BITS_IN_HALFULONG;i++)
+ if (x1&(1UL<<i))
+ {
+ r1^=y1<<i;
+ rr^=y2<<i;
+ }
+ r2^=(rr&LOWMASK)<<BITS_IN_HALFULONG;
+ r1^=(rr&HIGHMASK)>>BITS_IN_HALFULONG;
+ z=cgetg((r1?4:3),t_VECSMALL);
+ z[2]=r2;
+ if (r1) z[3]=r1;
+ return z;
+}
+
+GEN F2x_mul(GEN x, GEN y);
+
+/* fast product (Karatsuba) of polynomials a,b. These are not real GENs, a+2,
+ * b+2 were sent instead. na, nb = number of terms of a, b.
+ * Only c, c0, c1, c2 are genuine GEN.
+ */
+GEN
+F2x_mulspec(GEN a, GEN b, long na, long nb)
+{
+ GEN a0,c,c0;
+ long n0, n0a, i, v = 0;
+ pari_sp av;
+
+ while (na && !a[0]) { a++; na-=1; v++; }
+ while (nb && !b[0]) { b++; nb-=1; v++; }
+ if (na < nb) swapspec(a,b, na,nb);
+ if (!nb) return zero_Flx(0);
+
+ av = avma;
+ if (na <=1) return F2x_shiftip(av,F2x_mul1(*a,*b),v);
+ i=(na>>1); n0=na-i; na=i;
+ a0=a+n0; n0a=n0;
+ while (n0a && !a[n0a-1]) n0a--;
+
+ if (nb > n0)
+ {
+ GEN b0,c1,c2;
+ long n0b;
+
+ nb -= n0; b0 = b+n0; n0b = n0;
+ while (n0b && !b[n0b-1]) n0b--;
+ c = F2x_mulspec(a,b,n0a,n0b);
+ c0 = F2x_mulspec(a0,b0,na,nb);
+
+ c2 = F2x_addspec(a0,a,na,n0a);
+ c1 = F2x_addspec(b0,b,nb,n0b);
+
+ c1 = F2x_mul(c1,c2);
+ c2 = F2x_add(c0,c);
+
+ c2 = F2x_add(c1,c2);
+ c0 = F2x_addshift(c0,c2,n0);
+ }
+ else
+ {
+ c = F2x_mulspec(a,b,n0a,nb);
+ c0 = F2x_mulspec(a0,b,na,nb);
+ }
+ c0 = F2x_addshift(c0,c,n0);
+ return F2x_shiftip(av,c0, v);
+}
+
+GEN
+F2x_mul(GEN x, GEN y)
+{
+ GEN z = F2x_mulspec(x+2,y+2, lgpol(x),lgpol(y));
+ z[1] = x[1]; return z;
+}
+
+GEN
+F2x_sqr(GEN x)
+{
+ const ulong sq[]={0,1,4,5,16,17,20,21,64,65,68,69,80,81,84,85};
+ long i,ii,j,jj;
+ long lx=lg(x), lz=2+((lx-2)<<1);
+ GEN z;
+ z = cgetg(lz, t_VECSMALL); z[1]=x[1];
+ for (j=2,jj=2;j<lx;j++,jj++)
+ {
+ z[jj]=0;
+ ulong x1=((ulong)x[j]&HIGHMASK)>>BITS_IN_HALFULONG;
+ ulong x2=(ulong)x[j]&LOWMASK;
+ if (x2)
+ for(i=0,ii=0;i<BITS_IN_HALFULONG;i+=4,ii+=8)
+ z[jj]|=sq[(x2>>i)&15UL]<<ii;
+ z[++jj]=0;
+ if (x1)
+ for(i=0,ii=0;i<BITS_IN_HALFULONG;i+=4,ii+=8)
+ z[jj]|=sq[(x1>>i)&15UL]<<ii;
+ }
+ return F2x_renormalize(z, lz);
+}
+
+INLINE void
+F2x_addshiftip(GEN x, GEN y, ulong d)
+{
+ ulong dl=d>>TWOPOTBITS_IN_LONG;
+ ulong db=d&(BITS_IN_LONG-1UL);
+ ulong i;
+ if (db)
+ {
+ ulong dc=BITS_IN_LONG-db;
+ ulong r=0;
+ for(i=2; i<lg(y); i++)
+ {
+ x[i+dl] ^= (((ulong)y[i])<<db)|r;
+ r = ((ulong)y[i])>>dc;
+ }
+ if (r) x[i+dl] ^= r;
+ }
+ else
+ for(i=2; i<lg(y); i++)
+ x[i+dl] ^= y[i];
+}
+
+/* separate from F2x_divrem for maximal speed. */
+GEN
+F2x_rem(GEN x, GEN y)
+{
+ long dx,dy;
+ long lx=lg(x);
+ dy = F2x_degree(y); if (!dy) return zero_Flx(x[1]);
+ dx = F2x_degree_lg(x,lx);
+ x = vecsmall_copy(x);
+ while (dx>=dy)
+ {
+ F2x_addshiftip(x,y,dx-dy);
+ if (x[lx-1]==0) lx--;
+ dx=F2x_degree_lg(x,lx);
+ }
+ return F2x_renormalize(x, lx);
+}
+
+GEN
+F2x_divrem(GEN x, GEN y, GEN *pr)
+{
+ GEN z;
+ long dx,dy,dz,i;
+ long vs=x[1];
+ long lx=lg(x);
+
+ if (pr == ONLY_REM) return F2x_rem(x, y);
+ dy = F2x_degree(y);
+ if (!dy)
+ {
+ z = vecsmall_copy(x);
+ if (pr) *pr = zero_Flx(vs);
+ return z;
+ }
+ dx = F2x_degree_lg(x,lx);
+ dz = dx-dy;
+ if (dz < 0)
+ {
+ z = zero_Flx(vs);
+ if (pr) *pr = vecsmall_copy(x);
+ return z;
+ }
+ z = cgetg(lg(x)-lg(y)+3, t_VECSMALL); z[1] = vs;
+ x = vecsmall_copy(x);
+ for (i=2; i<lg(z); i++) z[i]=0;
+ while (dx>=dy)
+ {
+ F2x_set_coeff(z,dx-dy);
+ F2x_addshiftip(x,y,dx-dy);
+ if (x[lx-1]==0) lx--;
+ dx = F2x_degree_lg(x,lx);
+ }
+ z = F2x_renormalize(z, lg(z));
+ if (!pr) { cgiv(x); return z; }
+ x = F2x_renormalize(x, lx);
+ *pr = x; return z;
+}
+
+GEN
+F2x_gcd(GEN a, GEN b)
+{
+ pari_sp av=avma;
+ GEN c;
+ if (lg(b) > lg(a)) swap(a, b);
+ while (lgpol(b))
+ {
+ c = F2x_rem(a,b);
+ a = b; b = c;
+ }
+ return gerepileuptoleaf(av,a);
+}
+
+GEN
+F2x_extgcd(GEN a, GEN b, GEN *ptu, GEN *ptv)
+{
+ GEN q,z,u,v, x = a, y = b;
+
+ u = zero_Flx(a[1]);
+ v = pol1_F2x(a[1]); /* v = 1 */
+ while (lgpol(y))
+ {
+ q = F2x_divrem(x,y,&z);
+ x = y; y = z; /* (x,y) = (y, x - q y) */
+ z = F2x_add(u, F2x_mul(q,v));
+ u = v; v = z; /* (u,v) = (v, u - q v) */
+ }
+ z = F2x_add(x, F2x_mul(b,u));
+ z = F2x_div(z,a);
+ *ptu = z;
+ *ptv = u; return x;
+}
+
+GEN
+F2xq_mul(GEN x,GEN y,GEN pol)
+{
+ GEN z = F2x_mul(x,y);
+ return F2x_rem(z,pol);
+}
+
+GEN
+F2xq_sqr(GEN x,GEN pol)
+{
+ GEN z = F2x_sqr(x);
+ return F2x_rem(z,pol);
+}
+
+GEN
+F2xq_invsafe(GEN x, GEN T)
+{
+ GEN U, V;
+ GEN z = F2x_extgcd(x, T, &U, &V);
+ if (degpol(z)) return NULL;
+ return U;
+}
+
+GEN
+F2xq_inv(GEN x,GEN T)
+{
+ pari_sp av=avma;
+ GEN U = F2xq_invsafe(x, T);
+ if (!U) pari_err(talker,"non invertible polynomial in F2xq_inv");
+ return gerepileuptoleaf(av, U);
+}
+
+GEN
+F2xq_div(GEN x,GEN y,GEN T)
+{
+ pari_sp av = avma;
+ return gerepileuptoleaf(av, F2xq_mul(x,F2xq_inv(y,T),T));
+}
+
+static GEN
+_F2xq_sqr(void *data, GEN x)
+{
+ GEN pol = (GEN) data;
+ return F2xq_sqr(x, pol);
+}
+
+static GEN
+_F2xq_mul(void *data, GEN x, GEN y)
+{
+ GEN pol = (GEN) data;
+ return F2xq_mul(x,y, pol);
+}
+
+GEN
+F2xq_pow(GEN x, GEN n, GEN pol)
+{
+ pari_sp av=avma;
+ GEN y;
+
+ if (!signe(n)) return pol1_F2x(x[1]);
+ if (is_pm1(n)) /* +/- 1 */
+ return (signe(n) < 0)? F2xq_inv(x,pol): vecsmall_copy(x);
+
+ if (signe(n) < 0) x = F2xq_inv(x,pol);
+ y = leftright_pow(x, n, (void*)pol, &_F2xq_sqr, &_F2xq_mul);
+ return gerepileupto(av, y);
+}
+
+static GEN
+_F2xq_pow(void *data, GEN x, GEN n)
+{
+ GEN pol = (GEN) data;
+ return F2xq_pow(x,n, pol);
+}
+
+GEN
+random_F2x(long d, long vs)
+{
+ long i, l = 3 + (d>>TWOPOTBITS_IN_LONG);
+ GEN y = cgetg(l,t_VECSMALL); y[1] = vs;
+ for (i=2; i<l; i++) y[i] = pari_rand();
+ y[l-1] &= (1UL<<(d&(BITS_IN_LONG-1UL)))-1UL;
+ return F2x_renormalize(y,l);
+}
+
+static GEN
+_F2xq_rand(void *data)
+{
+ pari_sp av=avma;
+ GEN pol = (GEN) data;
+ long d = F2x_degree(pol);
+ GEN z;
+ do
+ {
+ avma = av;
+ z = random_F2x(d,pol[1]);
+ } while (lgpol(z)==0);
+ return z;
+}
+
+const static struct bb_group F2xq_star={_F2xq_mul,_F2xq_pow,_F2xq_rand,vecsmall_lexcmp,Flx_cmp1};
+
+GEN
+F2xq_order(GEN a, GEN ord, GEN T)
+{
+ return gen_eltorder(a,ord,(void*)T,&F2xq_star);
+}
+
+GEN
+F2xq_log(GEN a, GEN g, GEN ord, GEN T)
+{
+ return gen_PH_log(a,g,ord,(void*)T,&F2xq_star,NULL);
+}
+
+GEN
+F2xq_sqrtn(GEN a, GEN n, GEN T, GEN *zeta)
+{
+ if (!lgpol(a))
+ {
+ if (zeta)
+ *zeta=pol1_F2x(T[1]);
+ return zero_Flx(T[1]);
+ }
+ return gen_Shanks_sqrtn(a,n,addis(powuu(2,F2x_degree(T)),-1),zeta,(void*)T,&F2xq_star);
+}
+
+GEN
+gener_F2xq(GEN T, GEN *po)
+{
+ long i, j, vT = T[1], f = F2x_degree(T);
+ GEN g, L, L2, o, q = subis(powuu(2,f), 1);
+ pari_sp av0 = avma, av;
+
+ L = cgetg(1, t_VECSMALL);
+ o = factor_pn_1(gen_2,f);
+ L2 = shallowcopy( gel(o, 1) );
+ for (i = j = 1; i < lg(L2); i++)
+ {
+ if (equaliu(gel(L2,i),2)) continue;
+ gel(L2,j++) = diviiexact(q, gel(L2,i));
+ }
+ setlg(L2, j);
+ for (av = avma;; avma = av)
+ {
+ g = random_F2x(f, vT);
+ if (F2x_degree(g) < 1) continue;
+ for (i = 1; i < j; i++)
+ {
+ GEN a = F2xq_pow(g, gel(L2,i), T);
+ if (!degpol(a) && (((ulong)a[2])&1UL) == 1UL) break;
+ }
+ if (i == j) break;
+ }
+ if (!po) g = gerepilecopy(av0, g);
+ else {
+ *po = o; gerepileall(av0, 2, &g, po);
+ }
+ return g;
+}
Index: parigp3/src/basemath/FF.c
===================================================================
--- parigp3.orig/src/basemath/FF.c 2007-08-27 23:23:17.000000000 +0200
+++ parigp3/src/basemath/FF.c 2007-09-01 13:03:15.000000000 +0200
@@ -169,6 +169,8 @@
{
case t_FF_FpXQ:
return gel(x,2);
+ case t_FF_F2xq:
+ return F2x_to_ZX(gel(x,2));
default:
return Flx_to_ZX(gel(x,2));
}
@@ -188,6 +190,9 @@
r=gerepileupto(av,FpX_add(gel(x,2),gel(y,2),p));
break;
}
+ case t_FF_F2xq:
+ r=F2x_add(gel(x,2),gel(y,2));
+ break;
default:
r=Flx_add(gel(x,2),gel(y,2),pp);
}
@@ -207,6 +212,9 @@
r=gerepileupto(av,FpX_Fp_add(gel(x,2),modii(y,p),p));
break;
}
+ case t_FF_F2xq:
+ r=mpodd(y)?F2x_1_add(gel(x,2)):vecsmall_copy(gel(x,2));
+ break;
default:
r=Flx_Fl_add(gel(x,2),umodiu(y,pp),pp);
}
@@ -223,6 +231,9 @@
case t_FF_FpXQ:
r=FpX_neg(gel(x,2),p);
break;
+ case t_FF_F2xq:
+ r=vecsmall_copy(gel(x,2));
+ break;
default:
r=Flx_neg(gel(x,2),pp);
}
@@ -239,6 +250,9 @@
case t_FF_FpXQ:
r=FpX_neg(gel(x,2),p);
break;
+ case t_FF_F2xq:
+ r=gel(x,2);
+ break;
default:
r=Flx_neg(gel(x,2),pp);
}
@@ -259,6 +273,9 @@
r=gerepileupto(av,FpXQ_mul(gel(x,2),gel(y,2),T,p));
break;
}
+ case t_FF_F2xq:
+ r=F2xq_mul(gel(x,2),gel(y,2),T);
+ break;
default:
r=Flxq_mul(gel(x,2),gel(y,2),T,pp);
}
@@ -278,6 +295,9 @@
r=gerepileupto(av,FpX_Fp_mul(gel(x,2),modii(y,p),p));
break;
}
+ case t_FF_F2xq:
+ r=mpodd(y)?vecsmall_copy(gel(x,2)):zero_Flx(mael(x,2,1));
+ break;
default:
r=Flx_Fl_mul(gel(x,2),umodiu(y,pp),pp);
}
@@ -295,6 +315,10 @@
case t_FF_FpXQ:
r=gerepileupto(av,FpX_Fp_mul(gel(x,2),Fp_div(a,b,p),p));
break;
+ case t_FF_F2xq:
+ if (mpodd(b)==0) pari_err(gdiver);
+ r=mpodd(a)?vecsmall_copy(gel(x,2)):zero_Flx(mael(x,2,1));
+ break;
default:
r=gerepileupto(av,Flx_Fl_mul(gel(x,2),Fl_div(umodiu(a,pp),umodiu(b,pp),pp),pp));
}
@@ -314,6 +338,9 @@
r=gerepileupto(av,FpXQ_sqr(gel(x,2),T,p));
break;
}
+ case t_FF_F2xq:
+ r=F2xq_sqr(gel(x,2),T);
+ break;
default:
r=Flxq_sqr(gel(x,2),T,pp);
}
@@ -336,6 +363,10 @@
r=gerepileupto(av,FpX_Fp_mul(gel(x,2),p1,p));
}
break;
+ case t_FF_F2xq:
+ if (n<0) pari_err(gdiver);
+ r=n==0?vecsmall_copy(gel(x,2)):zero_Flx(mael(x,2,1));
+ break;
default:
{
ulong l1;
@@ -358,6 +389,9 @@
case t_FF_FpXQ:
r=gerepileupto(av,FpXQ_inv(gel(x,2),T,p));
break;
+ case t_FF_F2xq:
+ r=F2xq_inv(gel(x,2),T);
+ break;
default:
r=Flxq_inv(gel(x,2),T,pp);
}
@@ -376,6 +410,9 @@
case t_FF_FpXQ:
r=gerepileupto(av,FpXQ_div(gel(x,2),gel(y,2),T,p));
break;
+ case t_FF_F2xq:
+ r=gerepileupto(av,F2xq_div(gel(x,2),gel(y,2),T));
+ break;
default:
r=gerepileupto(av,Flxq_div(gel(x,2),gel(y,2),T,pp));
}
@@ -393,6 +430,10 @@
case t_FF_FpXQ:
r=gerepileupto(av,FpX_Fp_mul(FpXQ_inv(gel(x,2),T,p),modii(n,p),p));
break;
+ case t_FF_F2xq:
+ r=F2xq_inv(gel(x,2),T); /*Check for division by 0*/
+ if(!mpodd(n)) {avma=av; r=zero_Flx(mael(x,2,1));}
+ break;
default:
r=gerepileupto(av,Flx_Fl_mul(Flxq_inv(gel(x,2),T,pp),umodiu(n,pp),pp));
}
@@ -409,6 +450,9 @@
case t_FF_FpXQ:
r=FpXQ_sqrtn(gel(x,2),n,T,p,zetan);
break;
+ case t_FF_F2xq:
+ r=F2xq_sqrtn(gel(x,2),n,T,zetan);
+ break;
default:
r=Flxq_sqrtn(gel(x,2),n,T,pp,zetan);
}
@@ -439,6 +483,9 @@
case t_FF_FpXQ:
r = FpXQ_pow(gel(x,2), n, T, p);
break;
+ case t_FF_F2xq:
+ r = F2xq_pow(gel(x,2), n, T);
+ break;
default:
r = Flxq_pow(gel(x,2), n, T, pp);
}
@@ -455,6 +502,8 @@
{
case t_FF_FpXQ:
return FpXQ_norm(gel(x,2),T,p);
+ case t_FF_F2xq:
+ return lgpol(gel(x,2))?gen_1:gen_0;
default:
return utoi(Flxq_norm(gel(x,2),T,pp));
}
@@ -473,6 +522,9 @@
case t_FF_FpXQ:
r = quicktrace(gel(x,2), polsym(T, degpol(T)-1));
break;
+ case t_FF_F2xq:
+ r = quicktrace(F2x_to_ZX(gel(x,2)), polsym(F2x_to_ZX(T), F2x_degree(T)-1));
+ break;
default:
r = quicktrace(Flx_to_ZX(gel(x,2)), polsym(Flx_to_ZX(T), degpol(T)-1));
}
@@ -490,6 +542,9 @@
{
case t_FF_FpXQ:
return gerepileupto(av,FpXQ_charpoly(gel(x,2), T, p));
+ case t_FF_F2xq:
+ return gerepileupto(av,Flx_to_ZX(Flxq_charpoly(F2x_to_Flx(gel(x,2)),
+ F2x_to_Flx(T), 2UL)));
default:
return gerepileupto(av,Flx_to_ZX(Flxq_charpoly(gel(x,2), T, pp)));
}
@@ -506,6 +561,9 @@
{
case t_FF_FpXQ:
return gerepileupto(av,FpXQ_minpoly(gel(x,2), T, p));
+ case t_FF_F2xq:
+ return gerepileupto(av,Flx_to_ZX(Flxq_minpoly(F2x_to_Flx(gel(x,2)),
+ F2x_to_Flx(T), 2UL)));
default:
return gerepileupto(av,Flx_to_ZX(Flxq_minpoly(gel(x,2), T, pp)));
}
@@ -536,15 +594,19 @@
GEN r, T, p;
_getFF(x,&T,&p,&pp);
_checkFF(x,g,"log");
- if (!ord) ord = factor_pn_1(p,degpol(T));
- else
- if (!is_Z_factor(ord)) err(typeer, "FF_log");
+ if (ord && !is_Z_factor(ord)) err(typeer, "FF_log");
switch(x[1])
{
case t_FF_FpXQ:
+ if (!ord) ord = factor_pn_1(p,degpol(T));
r = FpXQ_log(gel(x,2), gel(g,2), ord, T, p);
break;
+ case t_FF_F2xq:
+ if (!ord) ord = factor_pn_1(gen_2,F2x_degree(T));
+ r = F2xq_log(gel(x,2), gel(g,2), ord, T);
+ break;
default:
+ if (!ord) ord = factor_pn_1(p,degpol(T));
r = Flxq_log(gel(x,2), gel(g,2), ord, T, pp);
}
return gerepileuptoint(av, r);
@@ -557,13 +619,18 @@
ulong pp;
GEN r, T,p;
_getFF(x,&T,&p,&pp);
- if (!o) o = factor_pn_1(p,degpol(T));
switch(x[1])
{
case t_FF_FpXQ:
+ if (!o) o = factor_pn_1(p,degpol(T));
r = FpXQ_order(gel(x,2), o, T, p);
break;
+ case t_FF_F2xq:
+ if (!o) o = factor_pn_1(gen_2,F2x_degree(T));
+ r = F2xq_order(gel(x,2), o, T);
+ break;
default:
+ if (!o) o = factor_pn_1(p,degpol(T));
r = Flxq_order(gel(x,2), o, T, pp);
}
if (!o) r = gerepileuptoint(av,r);
@@ -580,6 +647,9 @@
case t_FF_FpXQ:
r = gener_FpXQ(T, p, o);
break;
+ case t_FF_F2xq:
+ r = gener_F2xq(T, o);
+ break;
default:
r = gener_Flxq(T, pp, o);
}
@@ -599,6 +669,9 @@
case t_FF_FpXQ:
r=x;
break;
+ case t_FF_F2xq:
+ r=ZX_to_F2x(x);
+ break;
default:
r=ZX_to_Flx(x,pp);
}
@@ -659,7 +732,16 @@
GEN r, T, p;
pari_sp av=avma;
_getFF(x,&T,&p,&pp);
- if (x[1]) T=Flx_to_ZX(T);
+ switch(x[1])
+ {
+ case t_FF_FpXQ:
+ break;
+ case t_FF_F2xq:
+ T=F2x_to_ZX(T);
+ break;
+ default:
+ 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);
}
Index: parigp3/src/basemath/Flx.c
===================================================================
--- parigp3.orig/src/basemath/Flx.c 2007-08-30 11:30:09.000000000 +0200
+++ parigp3/src/basemath/Flx.c 2007-09-01 13:03:15.000000000 +0200
@@ -253,7 +253,7 @@
return Flx_renormalize(y,d);
}
-static int
+int
Flx_cmp1(GEN x)
{
return degpol(x)==0 && x[2]==1;
Index: parigp3/src/basemath/polarit2.c
===================================================================
--- parigp3.orig/src/basemath/polarit2.c 2007-08-25 23:42:06.000000000 +0200
+++ parigp3/src/basemath/polarit2.c 2007-09-01 13:03:15.000000000 +0200
@@ -4506,11 +4506,22 @@
{
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);
+ if (pp==2)
+ {
+ ff[1]=t_FF_F2xq;
+ gel(ff,2)=polx_F2x(sv);
+ gel(ff,3)=ZX_to_F2x(lift(T));
+ mael(ff,3,1)=sv;
+ gel(ff,4)=gen_2;
+ }
+ else
+ {
+ 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
{
Index: parigp3/src/headers/paricom.h
===================================================================
--- parigp3.orig/src/headers/paricom.h 2007-08-30 11:30:10.000000000 +0200
+++ parigp3/src/headers/paricom.h 2007-09-01 14:38:39.000000000 +0200
@@ -354,11 +354,13 @@
#define FpX_div(x,y,p) (FpX_divrem((x),(y),(p), NULL))
#define FpX_rem(x,y,p) (FpX_divrem((x),(y),(p), ONLY_REM))
#define Flx_div(x,y,p) (Flx_divrem((x),(y),(p), NULL))
+#define F2x_div(x,y) (F2x_divrem((x),(y), NULL))
#define FpV_FpC_mul(x,y,p) FpV_dotproduct((x),(y),(p))
#define FpX_renormalize ZX_renormalize
#define FpXX_renormalize ZX_renormalize
#define FpXQX_renormalize ZX_renormalize
+#define F2x_renormalize Flx_renormalize
#define ZX_ZXY_resultant(a,b) ZX_ZXY_rnfequation((a),(b),NULL)
Index: parigp3/src/headers/paridecl.h
===================================================================
--- parigp3.orig/src/headers/paridecl.h 2007-08-30 11:30:10.000000000 +0200
+++ parigp3/src/headers/paridecl.h 2007-09-01 13:03:16.000000000 +0200
@@ -19,6 +19,24 @@
/* */
/*******************************************************************/
+/* F2x.c */
+GEN F2x_1_add(GEN y);
+GEN F2x_add(GEN x, GEN y);
+long F2x_degree(GEN x);
+GEN F2x_to_Flx(GEN x);
+GEN F2x_to_ZX(GEN x);
+GEN F2xq_div(GEN x,GEN y,GEN T);
+GEN F2xq_inv(GEN x, GEN T);
+GEN F2xq_log(GEN a, GEN g, GEN ord, GEN T);
+GEN F2xq_mul(GEN x, GEN y, GEN pol);
+GEN F2xq_order(GEN a, GEN ord, GEN T);
+GEN F2xq_pow(GEN x, GEN n, GEN pol);
+GEN F2xq_sqr(GEN x,GEN pol);
+GEN F2xq_sqrtn(GEN a, GEN n, GEN T, GEN *zeta);
+GEN ZX_to_F2x(GEN x);
+GEN gener_F2xq(GEN T, GEN *po);
+GEN polx_F2x(long sv);
+
/* Flx.c */
GEN Fl_to_Flx(ulong x, long sv);
@@ -34,6 +52,7 @@
GEN Flx_Fl_add(GEN y, ulong x, ulong p);
GEN Flx_Fl_mul(GEN y, ulong x, ulong p);
GEN Flx_add(GEN x, GEN y, ulong p);
+int Flx_cmp1(GEN x);
GEN Flx_deflate(GEN x0, long d);
GEN Flx_deriv(GEN z, ulong p);
GEN Flx_div_by_X_x(GEN a, ulong x, ulong p, ulong *rem);
@@ -51,7 +70,6 @@
GEN Flx_neg_inplace(GEN x, ulong p);
GEN Flx_normalize(GEN z, ulong p);
GEN Flx_pow(GEN x, long n, ulong p);
-GEN random_Flx(long d1, long v, ulong p);
GEN Flx_recip(GEN x);
GEN Flx_red(GEN z, ulong p);
GEN Flx_rem_montgomery(GEN x, GEN mg, GEN T, ulong p);
@@ -109,6 +127,7 @@
GEN ZXXV_to_FlxXV(GEN V, ulong p, long v);
GEN gener_Flxq(GEN T, ulong p, GEN *o);
GEN polx_Flx(long sv);
+GEN random_Flx(long d1, long v, ulong p);
GEN zero_Flx(long sv);
/* FpX.c */
Index: parigp3/src/headers/paripriv.h
===================================================================
--- parigp3.orig/src/headers/paripriv.h 2007-08-29 09:32:02.000000000 +0200
+++ parigp3/src/headers/paripriv.h 2007-09-01 13:03:16.000000000 +0200
@@ -371,7 +371,7 @@
/* Finite field */
-enum { t_FF_FpXQ = 0, t_FF_Flxq =1 };
+enum { t_FF_FpXQ = 0, t_FF_Flxq = 1, t_FF_F2xq = 2 };
#include "parinf.h"