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

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