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