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