source: git/libpolys/coeffs/ffields.cc @ 7bb7da5

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