/**************************************** * Computer Algebra System SINGULAR * ****************************************/ /* $Id: ffields.cc,v 1.11 1997-05-02 15:10:12 Singular Exp $ */ /* * ABSTRACT: finite fields with a none-prime number of elements (via tables) */ #include #include #include "mod2.h" #include "tok.h" #include "febase.h" #include "mmemory.h" #include "numbers.h" #include "ffields.h" int nfCharQ=0; /* the number of elemts: q*/ int nfM1; /*representation of -1*/ static int nfCharP=0; /* the characteristic: p*/ static int nfCharQ1=0; /* q-1 */ CARDINAL *nfPlus1Table=NULL; /* the table i=log(z^i) -> log(z^i+1) */ char * nfParameter; /* the name of the primitive element */ /* the q's from the table 'fftable' */ short fftable[]={ 4, 8, 16, 32, 64, 128, 256, 512,1024,2048,4096,8192,16384, /*2^2 2^3 2^4 2^5 2^6 2^7 2^8 2^9 2^10 2^11 2^12 2^13 2^14*/ 9, 27, 81,243,729,2187, 6561,19683, /*3^2 3^3 3^4 3^5 3^6 3^7 3^8 3^9*/ 25,125,625,3125,15625, /*5^2 5^3 5^4 5^5 5^6*/ 49,343,2401,16807, /*7^2 7^3 7^4 7^5*/ 121,1331, 14641, /*11^2 11^3 11^4*/ 169, 2197, 28561, /*13^2 13^3 13^4*/ 289, 4913, /*17^2 17^3*/ 361, 6859, /*19^2 19^3*/ 529, 12167, /*23^2 23^3*/ 841, 24389, /*29^2 29^3*/ 961, 29791, /*31^2 31^3*/ 1369, /*37^2*/ 1681, /*41^2*/ 1849, /*43^2*/ 2209, /*47^2*/ 2809, /*53^2*/ 3481, /*59^2*/ 3721, /*61^2*/ 4489, /*67^2*/ 5041, /*71^2*/ 5329, /*73^2*/ 6241, /*79^2*/ 6889, /*83^2*/ 7921, /*89^2*/ 9409, /*97^2*/ 10201, /*101^2*/ 10609, /*103^2*/ 11449, /*107^2*/ 11881, /*109^2*/ 12769, /*113^2*/ 16129, /*127^2*/ 17161, /*131^2*/ 18769, /*137^2*/ 19321, /*139^2*/ 22201, /*149^2*/ 22801, /*151^2*/ 24649, /*157^2*/ 26569, /*163^2*/ 27889, /*167^2*/ 29929, /*173^2*/ 32041, /*179^2*/ 32761, /*181^2*/ 0 }; /*1 * numbers in GF(p^n): * let nfCharQ=q=nfCharP^n=p^n * GF(q)\{0} will be generated by powers of an element Z * Z^i will be represented by the int i, 1 by the int 0, 0 by the int q=nfChar */ #ifdef LDEBUG /*2 * debugging: is a a valid representation of a number ? */ BOOLEAN nfDBTest (number a, char *f, int l) { if (((int)a<0) || ((int)a>nfCharQ)) { Print("wrong %d in %s:%d\n",(int)a,f,l); return FALSE; } int i=0; do { if (nfPlus1Table[i]>nfCharQ) { Print("wrong table %d=%d in %s:%d\n",i,nfPlus1Table[i],f,l); return FALSE; } i++; } while (i= 0 ? */ BOOLEAN nfGreaterZero (number k) { #ifdef LDEBUG nfTest(k); #endif return !nfIsZero(k); } /*2 * a*b */ number nfMult (number a,number b) { #ifdef LDEBUG nfTest(a); nfTest(b); #endif if (((int)a == nfCharQ) || ((int)b == nfCharQ)) return (number)nfCharQ; /*else*/ int i=(int)a+(int)b; if (i>=nfCharQ1) i-=nfCharQ1; #ifdef LDEBUG nfTest((number)i); #endif return (number)i; } /*2 * int -> number */ number nfInit (int i) { while (i < 0) i += nfCharP; while (i >= nfCharP) i -= nfCharP; if (i==0) return (number)nfCharQ; int c=0; while (i>1) { c=nfPlus1Table[c]; i--; } #ifdef LDEBUG nfTest((number)c); #endif return (number)c; } /* * the generating element `z` */ number nfPar (int i) { return (number)1; } /*2 * the degree of the "alg. number" */ int nfParDeg(number n) { #ifdef LDEBUG nfTest(n); #endif if(nfCharQ == (int)n) return -1; return (int)n; } /*2 * number -> int */ int nfInt (number &n) { return 0; } /*2 * copy a number */ number nfCopy (number k) { #ifdef LDEBUG nfTest(k); #endif return k; } /*2 * a + b */ number nfAdd (number a, number b) { /*4 z^a+z^b=z^b*(z^(a-b)+1), if a>=b; * * =z^a*(z^(b-a)+1) if a= (int)b) { zb = (int)b; zab = (int)a-(int)b; } else { zb = (int)a; zab = (int)b-(int)a; } #ifdef LDEBUG nfTest((number)zab); #endif if (nfPlus1Table[zab]==nfCharQ) r=nfCharQ; /*if z^(a-b)+1 =0*/ else { r= zb+nfPlus1Table[zab]; if(r>=nfCharQ1) r-=nfCharQ1; } #ifdef LDEBUG nfTest((number)r); #endif return (number)r; } /*2 * a - b */ number nfSub (number a, number b) { number mb = nfNeg(b); return nfAdd(a,mb); } /*2 * a == 0 ? */ BOOLEAN nfIsZero (number a) { #ifdef LDEBUG nfTest(a); #endif return nfCharQ == (int)a; } /*2 * a == 1 ? */ BOOLEAN nfIsOne (number a) { #ifdef LDEBUG nfTest(a); #endif return 0 == (int)a; } /*2 * a == -1 ? */ BOOLEAN nfIsMOne (number a) { #ifdef LDEBUG nfTest(a); #endif return nfM1 == (int)a; } /*2 * a / b */ number nfDiv (number a,number b) { #ifdef LDEBUG nfTest(b); #endif if ((int)b==nfCharQ) { WerrorS("div. by 0"); return (number)nfCharQ; } #ifdef LDEBUG nfTest(a); #endif if ((int)a==nfCharQ) return (number)nfCharQ; /*else*/ int s = (int)a - (int)b; if (s < 0) s += nfCharQ1; #ifdef LDEBUG nfTest((number)s); #endif return (number)s; } /*2 * 1 / c */ number nfInvers (number c) { #ifdef LDEBUG nfTest(c); #endif if ((int)c==nfCharQ) { WerrorS("div. 1/0"); return (number)nfCharQ; } #ifdef LDEBUG nfTest(((number)(nfCharQ1-(int)c))); #endif return (number)(nfCharQ1-(int)c); } /*2 * -c */ number nfNeg (number c) { /*4 -z^c=z^c*(-1)=z^c*nfM1*/ #ifdef LDEBUG nfTest(c); #endif int i=(int)c+nfM1; if (i>=nfCharQ1) i-=nfCharQ1; #ifdef LDEBUG nfTest((number)i); #endif return (number)i; } /*2 * a > b ? */ BOOLEAN nfGreater (number a,number b) { #ifdef LDEBUG nfTest(a); nfTest(b); #endif return (int)a != (int)b; } /*2 * a == b ? */ BOOLEAN nfEqual (number a,number b) { #ifdef LDEBUG nfTest(a); nfTest(b); #endif return (int)a == (int)b; } /*2 * write via StringAppend */ void nfWrite (number &a) { #ifdef LDEBUG nfTest(a); #endif if ((int)a==nfCharQ) StringAppendS("0"); else if ((int)a==0) StringAppendS("1"); else { StringAppendS(nfParameter); if ((int)a!=1) { if(pShortOut==0) StringAppendS("^"); StringAppend("%d",(int)a); } } } /*2 * */ char * nfName(number a) { #ifdef LDEBUG nfTest(a); #endif char *s; if (((int)a==nfCharQ) || ((int)a==0)) return NULL; else if ((int)a==1) { return mstrdup(nfParameter); } else { s=(char *)AllocL(4+strlen(nfParameter)); sprintf(s,"%s%d",nfParameter,(int)a); } return s; } /*2 * c ^ i with i>=0 */ void nfPower (number a, int i, number * result) { #ifdef LDEBUG nfTest(a); #endif if (i==0) { //*result=nfInit(1); *result = (number)0; } else if (i==1) { //*result = nfCopy(a); *result = a; } else { nfPower(a,i-1,result); *result = nfMult(a,*result); } #ifdef LDEBUG nfTest(*result); #endif } /*4 * read an integer (with reduction mod p) */ static char* nfEati(char *s, int *i) { if (*s >= '0' && *s <= '9') { *i = 0; do { *i *= 10; *i += *s++ - '0'; if (*i > (INT_MAX / 10)) *i = *i % nfCharP; } while (*s >= '0' && *s <= '9'); if (*i >= nfCharP) *i = *i % nfCharP; } else *i = 1; return s; } /*2 * read a number */ char * nfRead (char *s, number *a) { int i; number z; number n; s = nfEati(s, &i); z=nfInit(i); *a=z; if (*s == '/') { s++; s = nfEati(s, &i); n=nfInit(i); *a = nfDiv(z,n); } if (strncmp(s,nfParameter,strlen(nfParameter))==0) { s+=strlen(nfParameter); if ((*s >= '0') && (*s <= '9')) { s=eati(s,&i); while (i>=nfCharQ1) i-=nfCharQ1; } else i=1; z=(number)i; *a=nfMult(*a,z); } #ifdef LDEBUG nfTest(*a); #endif return s; } #ifdef HAVE_FACTORY int gf_tab_numdigits62 ( int q ); int convertback62 ( char * p, int n ); #else static int gf_tab_numdigits62 ( int q ) { if ( q < 62 ) return 1; else if ( q < 62*62 ) return 2; /*else*/ return 3; } static int convback62 ( char c ) { if ( c >= '0' && c <= '9' ) return int(c) - int('0'); else if ( c >= 'A' && c <= 'Z' ) return int(c) - int('A') + 10; else return int(c) - int('a') + 36; } static int convertback62 ( char * p, int n ) { int r = 0; for ( int j = 0; j < n; j++ ) r = r * 62 + convback62( p[j] ); return r; } #endif int nfMinPoly[16]; void nfShowMipo() { int i=nfMinPoly[0]; int j=0; loop { j++; if (nfMinPoly[j]!=0) StringAppend("%d*%s^%d",nfMinPoly[j],nfParameter,i); i--; if(i<0) break; if (nfMinPoly[j]!=0) StringAppendS("+"); } } static void nfReadMipo(char *s) { char *l=strchr(s,';')+1; char *n; #ifdef HAVE_STRTOL int i=strtol(l,&n,10); #else int i; sscanf(l, "%d", &i); #endif l=n; int j=1; nfMinPoly[0]=i; while(i>=0) { #ifdef HAVE_STRTOL nfMinPoly[j]=strtol(l,&n,10); #else sscanf(l, "%d", &(nfMinPoly[j])); #endif if (l==n) break; l=n; j++; i--; } if (i>=0) { WerrorS("error in reading minpoly from gftables"); } } /*2 * init global variables from files 'gftables/%d' */ void nfSetChar(int c, char **param) { nfParameter=param[0]; if ((c==nfCharQ)||(c==-nfCharQ)) /*this field is already set*/ return; int i=0; while ((fftable[i]!=c) && (fftable[i]!=0)) i++; if (fftable[i]==0) return; if (nfCharQ > 1) { Free( (ADDRESS)nfPlus1Table,nfCharQ*sizeof(CARDINAL) ); nfPlus1Table=NULL; } if ((c>1) || (c<0)) { if (c>1) nfCharQ = c; else nfCharQ = -c; char buf[100]; sprintf(buf,"gftables/%d",nfCharQ); FILE * fp = feFopen(buf,"r",NULL,FALSE); if (fp==NULL) { sprintf(buf,"../gftables/%d",nfCharQ); fp = feFopen(buf,"r",NULL,TRUE); if (fp == NULL) { Werror("cannot find gftables/%d", nfCharQ); return; } } if(!fgets( buf, sizeof(buf), fp)) return; if(strcmp(buf,"@@ factory GF(q) table @@\n")!=0) { goto err; } if(!fgets( buf, sizeof(buf), fp)) { goto err; } int q; sscanf(buf,"%d %d",&nfCharP,&q); nfReadMipo(buf); nfCharQ1=nfCharQ-1; nfPlus1Table= (CARDINAL *)Alloc( (nfCharQ)*sizeof(CARDINAL) ); int digs = gf_tab_numdigits62( nfCharQ ); char * bufptr; int i = 1; int k; while ( i < nfCharQ ) { fgets( buf, sizeof(buf), fp); //( strlen( buffer ) == (size_t)digs * 30, "illegal table" ); bufptr = buf; k = 0; while ( (i < nfCharQ) && (k < 30) ) { nfPlus1Table[i] = convertback62( bufptr, digs ); if(nfPlus1Table[i]>nfCharQ) { Print("wrong entry %d: %d(%c%c%c)\n",i,nfPlus1Table[i],bufptr[0],bufptr[1],bufptr[2]); } bufptr += digs; if (nfPlus1Table[i]==nfCharQ) { if(i==nfCharQ1) { nfM1=0; } else { nfM1=i; } } i++; k++; } } nfPlus1Table[0]=nfPlus1Table[nfCharQ1]; } else nfCharQ=0; #ifdef LDEBUG nfTest((number)0); #endif return; err: Werror("illegal GF-table %d",nfCharQ); } /*2 * map Z/p -> GF(p,n) */ number nfMapP(number c) { return nfInit((int)c); } /*2 * set map function nMap ... -> GF(p,n) */ BOOLEAN nfSetMap(int c, char ** par, int nop, number minpol) { if (c==nfCharQ) { nMap=nfCopy; /* GF(p,n) -> GF(p,n) */ return TRUE; } if (c==nfCharP) { nMap=nfMapP; /* Z/p -> GF(p,n) */ return TRUE; } return FALSE; /* default */ } /*2 * dummy modulus: return 0 */ number nfIntMod(number a, number b) { return (number)nfCharQ; }