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