source: git/libpolys/coeffs/ffields.cc @ d4fa60

spielwiese
Last change on this file since d4fa60 was d4fa60, checked in by Martin Lee <martinlee84@…>, 12 years ago
chg: added cfInit_bigint for GF
  • Property mode set to 100644
File size: 20.2 KB
Line 
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/* $Id$ */
5/*
6* ABSTRACT: finite fields with a none-prime number of elements (via tables)
7*/
8
9#include "config.h"
10
11#include <omalloc/omalloc.h>
12
13#include <misc/auxiliary.h>
14#include <misc/mylimits.h>
15
16#include <reporter/reporter.h>
17#include <resources/feFopen.h>
18
19#include <coeffs/coeffs.h>
20#include <coeffs/numbers.h>
21#include <coeffs/ffields.h>
22#include <coeffs/longrat.h>
23
24#include <string.h>
25#include <math.h>
26
27BOOLEAN nfGreaterZero (number k, const coeffs r);
28number  nfMult        (number a, number b, const coeffs r);
29number  nfInit        (long i, const coeffs r);
30number  nfParameter   (int i, const coeffs r);
31int     nfInt         (number &n, const coeffs r);
32number  nfAdd         (number a, number b, const coeffs r);
33number  nfSub         (number a, number b, const coeffs r);
34void    nfPower       (number a, int i, number * result, const coeffs r);
35BOOLEAN nfIsZero      (number a, const coeffs r);
36BOOLEAN nfIsOne       (number a, const coeffs r);
37BOOLEAN nfIsMOne      (number a, const coeffs r);
38number  nfDiv         (number a, number b, const coeffs r);
39number  nfNeg         (number c, const coeffs r);
40number  nfInvers      (number c, const coeffs r);
41BOOLEAN nfGreater     (number a, number b, const coeffs r);
42BOOLEAN nfEqual       (number a, number b, const coeffs r);
43const char *  nfRead  (const char *s, number *a, const coeffs r);
44#ifdef LDEBUG
45BOOLEAN nfDBTest      (number a, const char *f, const int l, const coeffs r);
46#endif
47//void    nfSetChar     (const coeffs r);
48
49nMapFunc nfSetMap     (const coeffs src, const coeffs dst);
50char *  nfName        (number n, const coeffs r);
51void    nfReadTable   (const int c, const coeffs r);
52
53void    nfCoeffWrite(const coeffs r, BOOLEAN details);
54void    nfShowMipo(const coeffs r);
55
56
57
58/// Our Type!
59static const n_coeffType ID = n_GF;
60
61//unsigned short *nfPlus1Table=NULL; /* the table i=log(z^i) -> log(z^i+1) */
62
63const double sixteenlog2= 11.09035489;
64/* the q's from the table 'fftable' */
65unsigned short fftable[]={
66    4,  8, 16, 32, 64, 128, 256, 512,1024,2048,4096,8192,16384, 32768,
67/*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  2^15*/
68    9, 27, 81,243,729,2187, 6561,19683,59049,
69/*3^2 3^3 3^4 3^5 3^6  3^7  3^8   3^9  3^10*/
70   25,125,625,3125,15625,
71/*5^2 5^3 5^4 5^5  5^6*/
72   49,343,2401,16807,
73/*7^2 7^3  7^4 7^5*/
74   121,1331, 14641,
75/*11^2 11^3  11^4*/
76  169, 2197, 28561,
77/*13^2 13^3  13^4*/
78  289, 4913,
79/*17^2 17^3*/
80  361, 6859,
81/*19^2 19^3*/
82  529, 12167,
83/*23^2 23^3*/
84  841, 24389,
85/*29^2 29^3*/
86  961, 29791,
87/*31^2 31^3*/
88  1369, 50653,
89/*37^2  37^3*/
90  1681, /*41^2*/
91  1849, /*43^2*/
92  2209, /*47^2*/
93  2809, /*53^2*/
94  3481, /*59^2*/
95  3721, /*61^2*/
96  4489, /*67^2*/
97  5041, /*71^2*/
98  5329, /*73^2*/
99  6241, /*79^2*/
100  6889, /*83^2*/
101  7921, /*89^2*/
102  9409, /*97^2*/
103  10201, /*101^2*/
104  10609, /*103^2*/
105  11449, /*107^2*/
106  11881, /*109^2*/
107  12769, /*113^2*/
108  16129, /*127^2*/
109  17161, /*131^2*/
110  18769, /*137^2*/
111  19321, /*139^2*/
112  22201, /*149^2*/
113  22801, /*151^2*/
114  24649, /*157^2*/
115  26569, /*163^2*/
116  27889, /*167^2*/
117  29929, /*173^2*/
118  32041, /*179^2*/
119  32761, /*181^2*/
120  36481, /*191^2*/
121  37249, /*193^2*/
122  38809, /*197^2*/
123  39601, /*199^2*/
124  49729, /*223^2*/
125  44521, /*211^2*/
126  51529, /*227^2*/
127  52441, /*229^2*/
128  54289, /*233^2*/
129  57121, /*239^2*/
130  58081, /*241^2*/
131  63001, /*251^2*/
132  0 };
133
134/*1
135* numbers in GF(p^n):
136* let nfCharQ=q=nfCharP^n=p^n
137* GF(q)\{0} will be generated by powers of an element Z
138* Z^i will be represented by the int i, 1 by the int 0, 0 by the int q=nfChar
139*/
140
141#ifdef LDEBUG
142/*2
143* debugging: is a a valid representation of a number ?
144*/
145BOOLEAN nfDBTest (number a, const char *f, const int l, const coeffs r)
146{
147  assume( r->m_nfPlus1Table != NULL );
148  if (((long)a<0L) || ((long)a>(long)r->m_nfCharQ))
149  {
150    Print("wrong %d in %s:%d\n",(int)((long)a),f,l);
151    return FALSE;
152  }
153  int i=0;
154  do
155  {
156    if (r->m_nfPlus1Table[i]>r->m_nfCharQ)
157    {
158      Print("wrong table %d=%d in %s:%d\n",i,r->m_nfPlus1Table[i],f,l);
159      return FALSE;
160    }
161    i++;
162  } while (i<r->m_nfCharQ);
163  return TRUE;
164}
165#define nfTest(N, R) nfDBTest(N,__FILE__,__LINE__, R)
166#endif
167
168/*2
169* k >= 0 ?
170*/
171BOOLEAN nfGreaterZero (number k, const coeffs r)
172{
173#ifdef LDEBUG
174  nfTest(k, r);
175#endif
176  return !nfIsZero(k, r) && !nfIsMOne(k, r);
177}
178
179/*2
180* a*b
181*/
182number nfMult (number a,number b, const coeffs r)
183{
184#ifdef LDEBUG
185  nfTest(a, r);
186  nfTest(b, r);
187#endif
188  if (((long)a == (long)r->m_nfCharQ) || ((long)b == (long)r->m_nfCharQ))
189    return (number)(long)r->m_nfCharQ;
190  /*else*/
191  int i=(int)((long)a+(long)b);
192  if (i>=r->m_nfCharQ1) i-=r->m_nfCharQ1;
193#ifdef LDEBUG
194  nfTest((number)(long)i, r);
195#endif
196  return (number)(long)i;
197}
198
199/*2
200* int -> number
201*/
202number nfInit (long i, const coeffs r)
203{
204  assume( r->m_nfPlus1Table != NULL );
205  // Hmm .. this is just to prevent initialization
206  // from nfInitChar to go into an infinite loop
207  if (i==0) return (number)(long)r->m_nfCharQ;
208  while (i <  0)    i += r->m_nfCharP;
209  while (i >= r->m_nfCharP) i -= r->m_nfCharP;
210  if (i==0) return (number)(long)r->m_nfCharQ;
211  unsigned short c=0;
212  while (i>1)
213  {
214    c=r->m_nfPlus1Table[c];
215    i--;
216  }
217#ifdef LDEBUG
218  nfTest((number)(long)c, r);
219#endif
220  return (number)(long)c;
221}
222
223/*
224* the generating element `z`
225*/
226number nfParameter (int i, const coeffs)
227{
228  assume(i==1);
229 
230  if( i == 1 )
231    return (number)1;
232
233  return NULL;
234}
235
236/*2
237* the degree of the "alg. number"
238*/
239static int nfParDeg(number n, const coeffs r)
240{
241#ifdef LDEBUG
242  nfTest(n, r);
243#endif
244  if((long)r->m_nfCharQ == (long)n) return -1;
245  return (int)((long)n);
246}
247
248/*2
249* number -> int
250*/
251int nfInt (number &, const coeffs )
252{
253  return 0;
254}
255
256/*2
257* a + b
258*/
259number nfAdd (number a, number b, const coeffs R)
260{
261/*4 z^a+z^b=z^b*(z^(a-b)+1), if a>=b; *
262*          =z^a*(z^(b-a)+1)  if a<b  */
263#ifdef LDEBUG
264  nfTest(a, R);
265  nfTest(b, R);
266#endif
267  if ((long)R->m_nfCharQ == (long)a) return b;
268  if ((long)R->m_nfCharQ == (long)b) return a;
269  long zb,zab,r;
270  if ((long)a >= (long)b)
271  {
272    zb = (long)b;
273    zab = (long)a-(long)b;
274  }
275  else
276  {
277    zb = (long)a;
278    zab = (long)b-(long)a;
279  }
280#ifdef LDEBUG
281  nfTest((number)zab, R);
282#endif
283  if (R->m_nfPlus1Table[zab]==R->m_nfCharQ) r=(long)R->m_nfCharQ; /*if z^(a-b)+1 =0*/
284  else
285  {
286    r= zb+(long)R->m_nfPlus1Table[zab];
287    if(r>=(long)R->m_nfCharQ1) r-=(long)R->m_nfCharQ1;
288  }
289#ifdef LDEBUG
290  nfTest((number)r, R);
291#endif
292  return (number)r;
293}
294
295/*2
296* a - b
297*/
298number nfSub (number a, number b, const coeffs r)
299{
300  number mb = nfNeg(b, r);
301  return nfAdd(a,mb,r);
302}
303
304/*2
305* a == 0 ?
306*/
307BOOLEAN nfIsZero (number  a, const coeffs r)
308{
309#ifdef LDEBUG
310  nfTest(a, r);
311#endif
312  return (long)r->m_nfCharQ == (long)a;
313}
314
315/*2
316* a == 1 ?
317*/
318BOOLEAN nfIsOne (number a, const coeffs r)
319{
320#ifdef LDEBUG
321  nfTest(a, r);
322#endif
323  return 0L == (long)a;
324}
325
326/*2
327* a == -1 ?
328*/
329BOOLEAN nfIsMOne (number a, const coeffs r)
330{
331#ifdef LDEBUG
332  nfTest(a, r);
333#endif
334  if (0L == (long)a) return FALSE; /* special handling of char 2*/
335  return (long)r->m_nfM1 == (long)a;
336}
337
338/*2
339* a / b
340*/
341number nfDiv (number a,number b, const coeffs r)
342{
343#ifdef LDEBUG
344  nfTest(b, r);
345#endif
346  if ((long)b==(long)r->m_nfCharQ)
347  {
348    WerrorS(nDivBy0);
349    return (number)((long)r->m_nfCharQ);
350  }
351#ifdef LDEBUG
352  nfTest(a, r);
353#endif
354  if ((long)a==(long)r->m_nfCharQ)
355    return (number)((long)r->m_nfCharQ);
356  /*else*/
357  long s = (long)a - (long)b;
358  if (s < 0L)
359    s += (long)r->m_nfCharQ1;
360#ifdef LDEBUG
361  nfTest((number)s, r);
362#endif
363  return (number)s;
364}
365
366/*2
367* 1 / c
368*/
369number  nfInvers (number c, const coeffs r)
370{
371#ifdef LDEBUG
372  nfTest(c, r);
373#endif
374  if ((long)c==(long)r->m_nfCharQ)
375  {
376    WerrorS(nDivBy0);
377    return (number)((long)r->m_nfCharQ);
378  }
379#ifdef LDEBUG
380  nfTest(((number)((long)r->m_nfCharQ1-(long)c)), r);
381#endif
382  return (number)((long)r->m_nfCharQ1-(long)c);
383}
384
385/*2
386* -c
387*/
388number nfNeg (number c, const coeffs r)
389{
390/*4 -z^c=z^c*(-1)=z^c*nfM1*/
391#ifdef LDEBUG
392  nfTest(c, r);
393#endif
394  if ((long)r->m_nfCharQ == (long)c) return c;
395  long i=(long)c+(long)r->m_nfM1;
396  if (i>=(long)r->m_nfCharQ1) i-=(long)r->m_nfCharQ1;
397#ifdef LDEBUG
398  nfTest((number)i, r);
399#endif
400  return (number)i;
401}
402
403/*2
404* a > b ?
405*/
406BOOLEAN nfGreater (number a,number b, const coeffs r)
407{
408#ifdef LDEBUG
409  nfTest(a, r);
410  nfTest(b, r);
411#endif
412  return (long)a != (long)b;
413}
414
415/*2
416* a == b ?
417*/
418BOOLEAN nfEqual (number a,number b, const coeffs r)
419{
420#ifdef LDEBUG
421  nfTest(a, r);
422  nfTest(b, r);
423#endif
424  return (long)a == (long)b;
425}
426
427/*2
428* write via StringAppend
429*/
430static void nfWriteLong (number &a, const coeffs r)
431{
432#ifdef LDEBUG
433  nfTest(a, r);
434#endif
435  if ((long)a==(long)r->m_nfCharQ)  StringAppendS("0");
436  else if ((long)a==0L)   StringAppendS("1");
437  else if (nfIsMOne(a, r))   StringAppendS("-1");
438  else
439  {
440    StringAppendS(n_ParameterNames(r)[0]);
441    if ((long)a!=1L)
442    {
443      StringAppend("^%d",(int)((long)a)); // long output!
444    }
445  }
446}
447
448
449/*2
450* write (shortert output) via StringAppend
451*/
452static void nfWriteShort (number &a, const coeffs r)
453{
454#ifdef LDEBUG
455  nfTest(a, r);
456#endif
457  if ((long)a==(long)r->m_nfCharQ)  StringAppendS("0");
458  else if ((long)a==0L)   StringAppendS("1");
459  else if (nfIsMOne(a, r))   StringAppendS("-1");
460  else
461  {
462    StringAppendS(n_ParameterNames(r)[0]);
463    if ((long)a!=1L)
464    {
465      StringAppend("%d",(int)((long)a));
466    }
467  }
468}
469
470/*2
471*
472*/
473char * nfName(number a, const coeffs r)
474{
475#ifdef LDEBUG
476  nfTest(a, r);
477#endif
478  char *s;
479  const char * const nf_Parameter=n_ParameterNames(r)[0];
480  if (((long)a==(long)r->m_nfCharQ) || ((long)a==0L)) return NULL;
481  else if ((long)a==1L)
482  {
483    return omStrDup(nf_Parameter);
484  }
485  else
486  {
487    s=(char *)omAlloc(4+strlen(nf_Parameter));
488    sprintf(s,"%s%d",nf_Parameter,(int)((long)a));
489  }
490  return s;
491}
492/*2
493* c ^ i with i>=0
494*/
495void nfPower (number a, int i, number * result, const coeffs r)
496{
497#ifdef LDEBUG
498  nfTest(a, r);
499#endif
500  if (i==0)
501  {
502    //*result=nfInit(1);
503    *result = (number)0L;
504  }
505  else if (i==1)
506  {
507    *result = a;
508  }
509  else
510  {
511    nfPower(a,i-1,result, r);
512    *result = nfMult(a,*result, r);
513  }
514#ifdef LDEBUG
515  nfTest(*result, r);
516#endif
517}
518
519/*4
520* read an integer (with reduction mod p)
521*/
522static const char* nfEati(const char *s, int *i, const coeffs r)
523{
524  if (*s >= '0' && *s <= '9')
525  {
526    *i = 0;
527    do
528    {
529      *i *= 10;
530      *i += *s++ - '0';
531      if (*i > (MAX_INT_VAL / 10)) *i = *i % r->m_nfCharP;
532    }
533    while (*s >= '0' && *s <= '9');
534    if (*i >= r->m_nfCharP) *i = *i % r->m_nfCharP;
535  }
536  else *i = 1;
537  return s;
538}
539
540/*2
541* read a number
542*/
543const char * nfRead (const char *s, number *a, const coeffs r)
544{
545  int i;
546  number z;
547  number n;
548
549  s = nfEati(s, &i, r);
550  z=nfInit(i, r);
551  *a=z;
552  if (*s == '/')
553  {
554    s++;
555    s = nfEati(s, &i, r);
556    n=nfInit(i, r);
557    *a = nfDiv(z,n,r);
558  }
559  const char * const nf_Parameter = n_ParameterNames(r)[0];
560  const int N = strlen(nf_Parameter);
561  if (strncmp(s,nf_Parameter, N)==0)
562  {
563    s += N;
564    if ((*s >= '0') && (*s <= '9'))
565    {
566      s=eati(s,&i);
567      while (i>=r->m_nfCharQ1) i-=r->m_nfCharQ1;
568    }
569    else
570      i=1;
571    z=(number)(long)i;
572    *a=nfMult(*a,z,r);
573  }
574#ifdef LDEBUG
575  nfTest(*a, r);
576#endif
577  return s;
578}
579
580#ifdef HAVE_FACTORY
581int gf_tab_numdigits62 ( int q );
582int convertback62 ( char * p, int n );
583#else
584static int gf_tab_numdigits62 ( int q )
585{
586    if ( q < 62 )          return 1;
587    else  if ( q < 62*62 ) return 2;
588    /*else*/               return 3;
589}
590
591static int convback62 ( char c )
592{
593    if ( c >= '0' && c <= '9' )
594        return int(c) - int('0');
595    else  if ( c >= 'A' && c <= 'Z' )
596        return int(c) - int('A') + 10;
597    else
598        return int(c) - int('a') + 36;
599}
600
601static int convertback62 ( char * p, int n )
602{
603    int r = 0;
604    for ( int j = 0; j < n; j++ )
605        r = r * 62 + convback62( p[j] );
606    return r;
607}
608#endif
609
610int nfMinPoly[16];
611
612void nfShowMipo(const coeffs r)
613{
614  int i=nfMinPoly[0];
615  int j=0;
616  loop
617  {
618    j++;
619    if (nfMinPoly[j]!=0)
620      StringAppend("%d*%s^%d",nfMinPoly[j],n_ParameterNames(r)[0],i);
621    i--;
622    if(i<0) break;
623    if (nfMinPoly[j]!=0)
624      StringAppendS("+");
625  }
626}
627
628static void nfReadMipo(char *s)
629{
630  const char *l=strchr(s,';')+1;
631  char *n;
632  int i=strtol(l,&n,10);
633  l=n;
634  int j=1;
635  nfMinPoly[0]=i;
636  while(i>=0)
637  {
638    nfMinPoly[j]=strtol(l,&n,10);
639    if (l==n) break;
640    l=n;
641    j++;
642    i--;
643  }
644  if (i>=0)
645  {
646    WerrorS("error in reading minpoly from gftables");
647  }
648}
649
650/*2
651* init global variables from files 'gftables/%d'
652*/
653void nfReadTable(const int c, const coeffs r)
654{
655  //Print("GF(%d)\n",c);
656  if ((c==r->m_nfCharQ)||(c==-r->m_nfCharQ))
657    /*this field is already set*/  return;
658  int i=0;
659 
660  while ((fftable[i]!=c) && (fftable[i]!=0)) 
661    i++;
662 
663  if (fftable[i]==0)
664  {
665    Werror("illegal GF-table size: %d", c);
666    return;
667  }
668
669  if (r->m_nfCharQ > 1)
670  {
671    omFreeSize( (ADDRESS)r->m_nfPlus1Table,r->m_nfCharQ*sizeof(unsigned short) );
672    r->m_nfPlus1Table=NULL;
673  }
674  if ((c>1) || (c<0))
675  {
676    if (c>1) r->m_nfCharQ = c;
677    else     r->m_nfCharQ = -c;
678    char buf[100];
679    sprintf(buf,"gftables/%d",r->m_nfCharQ);
680    FILE * fp = feFopen(buf,"r",NULL,TRUE);
681    if (fp==NULL)
682    {
683      return;
684    }
685    if(!fgets( buf, sizeof(buf), fp)) return;
686    if(strcmp(buf,"@@ factory GF(q) table @@\n")!=0)
687    {
688      goto err;
689    }
690    if(!fgets( buf, sizeof(buf), fp))
691    {
692      goto err;
693    }
694    int q;
695    sscanf(buf,"%d %d",&r->m_nfCharP,&q);
696    nfReadMipo(buf);
697    r->m_nfCharQ1=r->m_nfCharQ-1;
698    //Print("nfCharQ=%d,nfCharQ1=%d,mipo=>>%s<<\n",nfCharQ,nfCharQ1,buf);
699    r->m_nfPlus1Table= (unsigned short *)omAlloc( (r->m_nfCharQ)*sizeof(unsigned short) );
700    int digs = gf_tab_numdigits62( r->m_nfCharQ );
701    char * bufptr;
702    int i = 1;
703    int k;
704    while ( i < r->m_nfCharQ )
705    {
706      fgets( buf, sizeof(buf), fp);
707      //( strlen( buffer ) == (size_t)digs * 30, "illegal table" );
708      bufptr = buf;
709      k = 0;
710      while ( (i < r->m_nfCharQ) && (k < 30) )
711      {
712        r->m_nfPlus1Table[i] = convertback62( bufptr, digs );
713        if(r->m_nfPlus1Table[i]>r->m_nfCharQ)
714        {
715          Print("wrong entry %d: %d(%c%c%c)\n",i,r->m_nfPlus1Table[i],bufptr[0],bufptr[1],bufptr[2]);
716        }
717        bufptr += digs;
718        if (r->m_nfPlus1Table[i]==r->m_nfCharQ)
719        {
720          if(i==r->m_nfCharQ1)
721          {
722            r->m_nfM1=0;
723          }
724          else
725          {
726            r->m_nfM1=i;
727          }
728        }
729        i++; k++;
730      }
731    }
732    r->m_nfPlus1Table[0]=r->m_nfPlus1Table[r->m_nfCharQ1];
733  }
734  else
735    r->m_nfCharQ=0;
736#ifdef LDEBUG
737  nfTest((number)0, r);
738#endif
739  return;
740err:
741  Werror("illegal GF-table %d",r->m_nfCharQ);
742}
743
744/*2
745* map Z/p -> GF(p,n)
746*/
747number nfMapP(number c, const coeffs, const coeffs dst)
748{
749  return nfInit((int)((long)c), dst);
750}
751
752/*2
753* map GF(p,n1) -> GF(p,n2), n1 < n2, n1 | n2
754*/
755int nfMapGG_factor;
756number nfMapGG(number c, const coeffs src, const coeffs)
757{
758  int i=(long)c;
759  i*= nfMapGG_factor;
760  while (i >src->m_nfCharQ1) i-=src->m_nfCharQ1;
761  return (number)((long)i);
762}
763/*2
764* map GF(p,n1) -> GF(p,n2), n1 > n2, n2 | n1
765*/
766number nfMapGGrev(number c, const coeffs src, const coeffs)
767{
768  int ex=(int)((long)c);
769  if ((ex % nfMapGG_factor)==0)
770    return (number)(((long)ex) / ((long)nfMapGG_factor));
771  else
772    return (number)(long)src->m_nfCharQ; /* 0 */
773}
774
775/*2
776* set map function nMap ... -> GF(p,n)
777*/
778nMapFunc nfSetMap(const coeffs src, const coeffs dst)
779{
780  if (nCoeff_is_GF(src,src->m_nfCharQ))
781  {
782    return ndCopyMap;   /* GF(p,n) -> GF(p,n) */
783  }
784  if (nCoeff_is_GF(src))
785  {
786    const coeffs r = dst;
787    int q=src->ch;
788    if ((src->m_nfCharQ % q)==0) /* GF(p,n1) -> GF(p,n2), n2 > n1 */
789    {
790      // check if n2 is a multiple of n1
791      int n1=1;
792      int qq=r->m_nfCharP;
793      while(qq!=q) { qq *= r->m_nfCharP; n1++; }
794      int n2=1;
795      qq=r->m_nfCharP;
796      while(qq!=src->m_nfCharQ) { qq *= r->m_nfCharP; n2++; }
797      //Print("map %d^%d -> %d^%d\n",r->m_nfCharP,n1,r->m_nfCharP,n2);
798      if ((n2 % n1)==0)
799      {
800        int save_ch=r->m_nfCharQ;
801        nfReadTable(src->m_nfCharQ, r);
802        int nn=r->m_nfPlus1Table[0];
803        nfReadTable(save_ch, r);
804        nfMapGG_factor= r->m_nfPlus1Table[0] / nn;
805        //Print("nfMapGG_factor=%d (%d / %d)\n",nfMapGG_factor, r->m_nfPlus1Table[0], nn);
806        return nfMapGG;
807      }
808      else if ((n1 % n2)==0)
809      {
810        nfMapGG_factor= (n1/n2);
811        return nfMapGGrev;
812      }
813      else
814        return NULL;
815    }
816  }
817  if (nCoeff_is_Zp(src,src->m_nfCharP))
818  {
819    return nfMapP;    /* Z/p -> GF(p,n) */
820  }
821  return NULL;     /* default */
822}
823
824static BOOLEAN nfCoeffIsEqual(const coeffs, n_coeffType, void*);
825
826static void nfKillChar(coeffs r)
827{
828  char** p = (char**)n_ParameterNames(r);
829
830  const int P = n_NumberOfParameters(r);
831 
832  for( int i = 1; i <= P; i++ )
833    if (p[i-1] != NULL) 
834      omFree( (ADDRESS)p[i-1] );
835 
836  omFreeSize((ADDRESS)p, P * sizeof(char*)); 
837}
838
839BOOLEAN nfInitChar(coeffs r,  void * parameter)
840{
841  //r->cfInitChar=npInitChar;
842  r->cfKillChar=nfKillChar;
843  r->nCoeffIsEqual=nfCoeffIsEqual;
844
845  r->cfMult  = nfMult;
846  r->cfSub   = nfSub;
847  r->cfAdd   = nfAdd;
848  r->cfDiv   = nfDiv;
849  r->cfIntDiv= nfDiv;
850  //r->cfIntMod= ndIntMod;
851  r->cfExactDiv= nfDiv;
852  r->cfInit = nfInit;
853  //r->cfSize  = ndSize;
854  r->cfInt  = nfInt;
855  #ifdef HAVE_RINGS
856  //r->cfDivComp = NULL; // only for ring stuff
857  //r->cfIsUnit = NULL; // only for ring stuff
858  //r->cfGetUnit = NULL; // only for ring stuff
859  //r->cfExtGcd = NULL; // only for ring stuff
860  // r->cfDivBy = NULL; // only for ring stuff
861  #endif
862  r->cfNeg   = nfNeg;
863  r->cfInvers= nfInvers;
864  //r->cfCopy  = ndCopy;
865  //r->cfRePart = ndCopy;
866  //r->cfImPart = ndReturn0;
867 
868  r->cfWriteLong = nfWriteLong;
869  r->cfInit_bigint = nlModP;
870  r->cfRead = nfRead;
871  //r->cfNormalize=ndNormalize;
872  r->cfGreater = nfGreater;
873  r->cfEqual = nfEqual;
874  r->cfIsZero = nfIsZero;
875  r->cfIsOne = nfIsOne;
876  r->cfIsMOne = nfIsMOne;
877  r->cfGreaterZero = nfGreaterZero;
878  r->cfPower = nfPower;
879  //r->cfGcd  = ndGcd;
880  //r->cfLcm  = ndGcd;
881  //r->cfDelete= ndDelete;
882  r->cfSetMap = nfSetMap;
883  //r->cfName = ndName;
884  // debug stuff
885  r->cfCoeffWrite=nfCoeffWrite;
886   
887  r->cfParDeg = nfParDeg;
888
889#ifdef LDEBUG
890  r->cfDBTest=nfDBTest;
891#endif
892 
893  // the variables:
894  r->nNULL = (number)0;
895  assume( getCoeffType(r) == n_GF );
896
897  GFInfo* p = (GFInfo *)(parameter);
898  assume (p->GFChar > 0);
899  assume (p->GFDegree > 0);
900
901  const char * name = p->GFPar_name;
902 
903  r->m_nfCharQ = 0;
904  r->m_nfCharP = p->GFChar;
905  r->m_nfCharQ1 = 0;
906
907  r->iNumberOfParameters = 1;
908  r->cfParameter = nfParameter;
909
910  char ** pParameterNames = (char **) omAlloc0(sizeof(char *));
911  pParameterNames[0] = omStrDup(name); //TODO use omAlloc for allocating memory and use strcpy?
912
913  assume( pParameterNames != NULL );
914  assume( pParameterNames[0] != NULL );
915 
916  r->pParameterNames = pParameterNames;
917  // NOTE: r->m_nfParameter was replaced by n_ParameterNames(r)[0]
918
919  // TODO: nfKillChar MUST destroy r->pParameterNames[0] (0-term. string) && r->pParameterNames (array of size 1)
920
921  r->m_nfPlus1Table= NULL;
922
923  if (strlen(name) > 1)
924    r->cfWriteShort = nfWriteLong;
925  else
926    r->cfWriteShort = nfWriteShort;
927
928  r->has_simple_Alloc=TRUE;
929  r->has_simple_Inverse=TRUE;
930
931  if(p->GFChar > (2<<15))
932  {
933    Werror("illegal characteristic");
934    return TRUE;
935  }
936
937  const double check= log ((double) (p->GFChar)); 
938
939  if( (p->GFDegree * check) > sixteenlog2 )
940  {
941    Werror("Sorry: illegal size: %u ^ %u", p->GFChar, p->GFDegree );
942    return TRUE;
943  }
944
945  int c = pow (p->GFChar, p->GFDegree);
946
947  nfReadTable(c, r);
948 
949  if( r->m_nfPlus1Table == NULL )
950  {
951    Werror("Sorry: cannot init lookup table!");
952    return TRUE;
953  }
954 
955 
956  assume (r -> m_nfCharQ > 0);
957
958  r->ch = r->m_nfCharP; 
959  assume( r->m_nfPlus1Table != NULL );
960 
961  return FALSE;
962 
963}
964
965void    nfCoeffWrite  (const coeffs r, BOOLEAN details)
966{
967  // m_nfCharQ = p^k where p is the characteristic (r->CharP) and k is GFDegree
968  Print("//   # ground field : %d\n",r->m_nfCharQ);
969  Print("//   primitive element : %s\n", n_ParameterNames(r)[0]);
970  if ( details )
971  {
972    StringSetS("//   minpoly        : ");
973    nfShowMipo(r);
974    PrintS(StringAppendS("\n"));
975  }
976  else PrintS("//   minpoly        : ...\n"); 
977}
978
979static BOOLEAN nfCoeffIsEqual (const coeffs r, n_coeffType n, void * parameter)
980{
981  if (n==n_GF) {
982    GFInfo* p = (GFInfo *)(parameter);
983    int c = pow (p->GFChar, p->GFDegree);
984    if ((c == r->m_nfCharQ) && (strcmp(n_ParameterNames(r)[0], p->GFPar_name) == 0))
985      return TRUE;
986  }
987  return FALSE;
988}
Note: See TracBrowser for help on using the repository browser.