| Bill Allombert on Fri, 05 Oct 2007 11:47:03 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
| [patch v2] FFELT format for finite fields of characteristic 2 |
On Sat, Sep 01, 2007 at 06:13:56PM +0200, Bill Allombert wrote: > Hello PARI dev, > > Example of use: > a=ffgen(ffinit(2,32,a)); > a^15 > > This patch also adds two new classes 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. Please find a cleaner version of this patch, with documentations for the F2x and F2xq classes of functions. Cheers, Bill.
Index: doc/usersch4.tex
===================================================================
RCS file: /home/cvs/pari/doc/usersch4.tex,v
retrieving revision 1.119
diff -u -r1.119 usersch4.tex
--- doc/usersch4.tex 10 Sep 2007 00:35:02 -0000 1.119
+++ doc/usersch4.tex 5 Oct 2007 09:32:19 -0000
@@ -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: doc/usersch5.tex
===================================================================
RCS file: /home/cvs/pari/doc/usersch5.tex,v
retrieving revision 1.329
diff -u -r1.329 usersch5.tex
--- doc/usersch5.tex 4 Oct 2007 20:01:23 -0000 1.329
+++ doc/usersch5.tex 5 Oct 2007 09:32:21 -0000
@@ -2518,6 +2518,9 @@
\fun{GEN}{Flx_red}{GEN z, ulong p} converts from \kbd{zx} with
non-negative coefficients to \kbd{Flx} (by reducing them mod \kbd{p}).
+\fun{int}{Flx_cmp1}{GEN x} returns 1 (true) if the \kbd{Flx x} is equal to~1,
+0~(false) otherwise.
+
\fun{GEN}{Flx_add}{GEN x, GEN y, ulong p}
\fun{GEN}{Flx_Fl_add}{GEN y, ulong x, ulong p}
@@ -2742,6 +2745,72 @@
\fun{GEN}{FlxqM_ker}{GEN x, GEN T, ulong p}
+\subsec{\kbd{F2x}} An \kbd{F2x}~\kbd{z} is a \typ{VECSMALL}
+representing a polynomial over $\F_2[X]$. Specifically
+\kbd{z[0]} is the usual codeword, \kbd{z[1] = evalvarn($v$)} for some
+variable $v$ and the coefficients are given by the bits of remaining
+words by increasing degree.
+
+\subsubsec{Basic operations}
+
+\fun{GEN}{Flx_to_F2x}{GEN x}
+
+\fun{GEN}{ZX_to_F2x}{GEN x}
+
+\fun{GEN}{F2x_to_Flx}{GEN x}
+
+\fun{GEN}{F2x_to_ZX}{GEN x}
+
+\fun{GEN}{pol1_F2x}{long sv} returns the \kbd{F2x} in variable $s$ constant to
+$1$.
+
+\fun{GEN}{polx_F2x}{long sv} returns the variable $v$ as degree~1~\kbd{F2x}.
+
+\fun{GEN}{random_F2x}{long d, long sv} returns a random \kbd{F2x}
+in variable \kbd{v}, of degree less than~\kbd{d}.
+
+\fun{long}{F2x_degree}{GEN x} returns the degree of the \kbd{F2x x}. The degree of $0$ is defined as $-1$.
+
+\fun{int}{F2x_cmp1}{GEN x}
+
+\fun{GEN}{F2x_1_add}{GEN y} returns \kbd{y+1} where \kbd{y} is a \kbd{Flx}.
+
+\fun{GEN}{F2x_add}{GEN x, GEN y}
+
+\fun{GEN}{F2x_mul}{GEN x, GEN y}
+
+\fun{GEN}{F2x_sqr}{GEN x}
+
+\fun{GEN}{F2x_divrem}{GEN x, GEN y, GEN *pr}
+
+\fun{GEN}{F2x_rem}{GEN x, GEN y}
+
+\fun{GEN}{F2x_extgcd}{GEN a, GEN b, GEN *ptu, GEN *ptv}
+
+\fun{GEN}{F2x_gcd}{GEN a, GEN b}
+
+\subsec{\kbd{F2xq}}. See \kbd{FpXQ} operations.
+
+\fun{GEN}{F2xq_mul}{GEN x, GEN y, GEN pol}
+
+\fun{GEN}{F2xq_sqr}{GEN x,GEN pol}
+
+\fun{GEN}{F2xq_div}{GEN x,GEN y,GEN T}
+
+\fun{GEN}{F2xq_inv}{GEN x, GEN T}
+
+\fun{GEN}{F2xq_invsafe}{GEN x, GEN T}
+
+\fun{GEN}{F2xq_pow}{GEN x, GEN n, GEN pol}
+
+\fun{GEN}{F2xq_log}{GEN a, GEN g, GEN ord, GEN T}
+
+\fun{GEN}{F2xq_order}{GEN a, GEN ord, GEN T}
+
+\fun{GEN}{F2xq_sqrtn}{GEN a, GEN n, GEN T, GEN *zeta}
+
+\fun{GEN}{gener_F2xq}{GEN T, GEN *po}
+
\subsec{\kbd{QX}}.
\fun{GEN}{QXQ_inv}{GEN A, GEN B} returns the inverse of \kbd{A} modulo \kbd{B}
Index: src/basemath/FF.c
===================================================================
RCS file: /home/cvs/pari/src/basemath/FF.c,v
retrieving revision 1.10
diff -u -r1.10 FF.c
--- src/basemath/FF.c 4 Oct 2007 20:01:23 -0000 1.10
+++ src/basemath/FF.c 5 Oct 2007 09:32:21 -0000
@@ -150,6 +150,9 @@
case t_FF_FpXQ:
r=pol_1(varn(T));
break;
+ case t_FF_F2xq:
+ r=pol1_F2x(T[1]);
+ break;
default:
r=pol1_Flx(T[1]);
}
@@ -186,6 +189,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));
}
@@ -205,6 +210,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);
}
@@ -224,6 +232,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);
}
@@ -240,6 +251,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);
}
@@ -256,6 +270,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);
}
@@ -276,6 +293,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);
}
@@ -295,6 +315,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);
}
@@ -312,6 +335,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));
}
@@ -331,6 +358,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);
}
@@ -353,6 +383,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;
@@ -375,6 +409,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);
}
@@ -393,6 +430,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));
}
@@ -410,6 +450,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));
}
@@ -426,6 +470,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);
}
@@ -456,6 +503,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);
}
@@ -472,6 +522,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));
}
@@ -490,6 +542,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));
}
@@ -507,6 +562,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)));
}
@@ -523,6 +581,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)));
}
@@ -553,15 +614,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);
@@ -574,13 +639,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);
@@ -597,6 +667,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);
}
@@ -616,6 +689,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);
}
@@ -676,7 +752,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: src/basemath/Flx.c
===================================================================
RCS file: /home/cvs/pari/src/basemath/Flx.c,v
retrieving revision 1.104
diff -u -r1.104 Flx.c
--- src/basemath/Flx.c 4 Oct 2007 20:01:23 -0000 1.104
+++ src/basemath/Flx.c 5 Oct 2007 09:32:21 -0000
@@ -258,7 +258,7 @@
return Flx_renormalize(y,d);
}
-static int
+int
Flx_cmp1(GEN x)
{
return degpol(x)==0 && x[2]==1;
Index: src/basemath/polarit2.c
===================================================================
RCS file: /home/cvs/pari/src/basemath/polarit2.c,v
retrieving revision 1.472
diff -u -r1.472 polarit2.c
--- src/basemath/polarit2.c 27 Sep 2007 21:21:31 -0000 1.472
+++ src/basemath/polarit2.c 5 Oct 2007 09:32:22 -0000
@@ -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: src/headers/paricom.h
===================================================================
RCS file: /home/cvs/pari/src/headers/paricom.h,v
retrieving revision 1.117
diff -u -r1.117 paricom.h
--- src/headers/paricom.h 18 Sep 2007 08:49:55 -0000 1.117
+++ src/headers/paricom.h 5 Oct 2007 09:32:23 -0000
@@ -344,10 +344,15 @@
#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 FpV_FpC_mul(x,y,p) FpV_dotproduct((x),(y),(p))
+#define F2x_div(x,y) (F2x_divrem((x),(y), NULL))
+
+#define pol1_F2x(x) (pol1_Flx((x)))
+#define F2x_cmp1(x) (Flx_cmp1((x)))
#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: src/headers/paridecl.h
===================================================================
RCS file: /home/cvs/pari/src/headers/paridecl.h,v
retrieving revision 1.716
diff -u -r1.716 paridecl.h
--- src/headers/paridecl.h 4 Oct 2007 20:01:23 -0000 1.716
+++ src/headers/paridecl.h 5 Oct 2007 09:32:23 -0000
@@ -19,6 +19,34 @@
/* */
/*******************************************************************/
+/* F2x.c */
+
+GEN F2x_1_add(GEN y);
+GEN F2x_add(GEN x, GEN y);
+long F2x_degree(GEN x);
+GEN F2x_divrem(GEN x, GEN y, GEN *pr);
+GEN F2x_extgcd(GEN a, GEN b, GEN *ptu, GEN *ptv);
+GEN F2x_gcd(GEN a, GEN b);
+GEN F2x_mul(GEN x, GEN y);
+GEN F2x_rem(GEN x, GEN y);
+GEN F2x_sqr(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_invsafe(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 Flx_to_F2x(GEN x);
+GEN ZX_to_F2x(GEN x);
+GEN gener_F2xq(GEN T, GEN *po);
+GEN polx_F2x(long sv);
+GEN random_F2x(long d, long vs);
+
/* Flx.c */
GEN Fl_to_Flx(ulong x, long sv);
@@ -34,6 +62,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);
Index: src/headers/paripriv.h
===================================================================
RCS file: /home/cvs/pari/src/headers/paripriv.h,v
retrieving revision 1.168
diff -u -r1.168 paripriv.h
--- src/headers/paripriv.h 18 Sep 2007 08:49:55 -0000 1.168
+++ src/headers/paripriv.h 5 Oct 2007 09:32:24 -0000
@@ -365,7 +365,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"