source: git/libpolys/coeffs/ffields.cc @ 560a3d

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