My Project
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 #include "coeffs/modulop.h"
20 
21 #include <cmath>
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 r )
241 {
242  unsigned short c=0;
243  unsigned short nn=(unsigned short)(long)n;
244  if (nn==r->m_nfCharQ) return 0;
245  long i=1; /* 1==a^0 */
246  while ((c!=nn)&&(i<r->m_nfCharP))
247  {
248  c=r->m_nfPlus1Table[c];
249  i++;
250  }
251  if (c==nn) return i;
252  else return 0;
253 }
254 
255 /*2
256 * a + b
257 */
258 static number nfAdd (number a, number b, const coeffs R)
259 {
260 /*4 z^a+z^b=z^b*(z^(a-b)+1), if a>=b; *
261 * =z^a*(z^(b-a)+1) if a<b */
262 #ifdef LDEBUG
263  nfTest(a, R);
264  nfTest(b, R);
265 #endif
266  if ((long)R->m_nfCharQ == (long)a) return b;
267  if ((long)R->m_nfCharQ == (long)b) return a;
268  long zb,zab,r;
269  if ((long)a >= (long)b)
270  {
271  zb = (long)b;
272  zab = (long)a-(long)b;
273  }
274  else
275  {
276  zb = (long)a;
277  zab = (long)b-(long)a;
278  }
279 #ifdef LDEBUG
280  nfTest((number)zab, R);
281 #endif
282  if (R->m_nfPlus1Table[zab]==R->m_nfCharQ) r=(long)R->m_nfCharQ; /*if z^(a-b)+1 =0*/
283  else
284  {
285  r= zb+(long)R->m_nfPlus1Table[zab];
286  if(r>=(long)R->m_nfCharQ1) r-=(long)R->m_nfCharQ1;
287  }
288 #ifdef LDEBUG
289  nfTest((number)r, R);
290 #endif
291  return (number)r;
292 }
293 
294 /*2
295 * -c
296 */
297 static number nfNeg (number c, const coeffs r)
298 {
299 /*4 -z^c=z^c*(-1)=z^c*nfM1*/
300 #ifdef LDEBUG
301  nfTest(c, r);
302 #endif
303  if ((long)r->m_nfCharQ == (long)c) return c;
304  long i=(long)c+(long)r->m_nfM1;
305  if (i>=(long)r->m_nfCharQ1) i-=(long)r->m_nfCharQ1;
306 #ifdef LDEBUG
307  nfTest((number)i, r);
308 #endif
309  return (number)i;
310 }
311 
312 /*2
313 * a - b
314 */
315 static number nfSub (number a, number b, const coeffs r)
316 {
317  number mb = nfNeg(b, r);
318  return nfAdd(a,mb,r);
319 }
320 
321 /*2
322 * a == 1 ?
323 */
324 static BOOLEAN nfIsOne (number a, const coeffs r)
325 {
326 #ifdef LDEBUG
327  nfTest(a, r);
328 #endif
329  return 0L == (long)a;
330 }
331 
332 /*2
333 * a / b
334 */
335 static number nfDiv (number a,number b, const coeffs r)
336 {
337 #ifdef LDEBUG
338  nfTest(b, r);
339 #endif
340  if ((long)b==(long)r->m_nfCharQ)
341  {
342  WerrorS(nDivBy0);
343  return (number)((long)r->m_nfCharQ);
344  }
345 #ifdef LDEBUG
346  nfTest(a, r);
347 #endif
348  if ((long)a==(long)r->m_nfCharQ)
349  return (number)((long)r->m_nfCharQ);
350  /*else*/
351  long s = (long)a - (long)b;
352  if (s < 0L)
353  s += (long)r->m_nfCharQ1;
354 #ifdef LDEBUG
355  nfTest((number)s, r);
356 #endif
357  return (number)s;
358 }
359 
360 /*2
361 * 1 / c
362 */
363 static number nfInvers (number c, const coeffs r)
364 {
365 #ifdef LDEBUG
366  nfTest(c, r);
367 #endif
368  if ((long)c==(long)r->m_nfCharQ)
369  {
370  WerrorS(nDivBy0);
371  return (number)((long)r->m_nfCharQ);
372  }
373 #ifdef LDEBUG
374  nfTest(((number)((long)r->m_nfCharQ1-(long)c)), r);
375 #endif
376  return (number)((long)r->m_nfCharQ1-(long)c);
377 }
378 
379 /*2
380 * a > b ?
381 */
382 static BOOLEAN nfGreater (number a,number b, const coeffs r)
383 {
384 #ifdef LDEBUG
385  nfTest(a, r);
386  nfTest(b, r);
387 #endif
388  return (long)a != (long)b;
389 }
390 
391 /*2
392 * a == b ?
393 */
394 static BOOLEAN nfEqual (number a,number b, const coeffs r)
395 {
396 #ifdef LDEBUG
397  nfTest(a, r);
398  nfTest(b, r);
399 #endif
400  return (long)a == (long)b;
401 }
402 
403 /*2
404 * write via StringAppend
405 */
406 static void nfWriteLong (number a, const coeffs r)
407 {
408 #ifdef LDEBUG
409  nfTest(a, r);
410 #endif
411  if ((long)a==(long)r->m_nfCharQ) StringAppendS("0");
412  else if ((long)a==0L) StringAppendS("1");
413  else if (nfIsMOne(a, r)) StringAppendS("-1");
414  else
415  {
416  int i=1; /* 1==a^0 */
417  unsigned short c=0;
418  unsigned short nn=(unsigned short)(long)a;
419  while ((c!=nn)&&(i<r->m_nfCharQ))
420  {
421  c=r->m_nfPlus1Table[c];
422  i++;
423  }
424  if (c==nn) StringAppend("%d",i);
425  else
426  {
428  if ((long)a!=1L)
429  {
430  StringAppend("^%d",(int)((long)a)); // long output!
431  }
432  }
433  }
434 }
435 
436 
437 /*2
438 * write (shortert output) via StringAppend
439 */
440 static void nfWriteShort (number a, const coeffs r)
441 {
442 #ifdef LDEBUG
443  nfTest(a, r);
444 #endif
445  if ((long)a==(long)r->m_nfCharQ) StringAppendS("0");
446  else if ((long)a==0L) StringAppendS("1");
447  else if (nfIsMOne(a, r)) StringAppendS("-1");
448  else
449  {
450  int i=1; /* 1==a^0 */
451  unsigned short c=0;
452  unsigned short nn=(unsigned short)(long)a;
453  while ((c!=nn)&&(i<r->m_nfCharQ))
454  {
455  c=r->m_nfPlus1Table[c];
456  i++;
457  }
458  if (c==nn) StringAppend("%d",i);
459  else
460  {
462  if ((long)a!=1L)
463  {
464  StringAppend("%d",(int)((long)a));
465  }
466  }
467  }
468 }
469 
470 /*2
471 * c ^ i with i>=0
472 */
473 static void nfPower (number a, int i, number * result, const coeffs r)
474 {
475 #ifdef LDEBUG
476  nfTest(a, r);
477 #endif
478  if (i==0)
479  {
480  *result = (number)0L;
481  }
482  else if (i==1)
483  {
484  *result = a;
485  }
486  else
487  {
488  long rl;
489  if ((long)a == (long)r->m_nfCharQ) rl=(long)r->m_nfCharQ;
490  else rl=((long)a*(long)i) % (long)r->m_nfCharQ1;
491  *result = (number)rl;
492  }
493 #ifdef LDEBUG
494  nfTest(*result, r);
495 #endif
496 }
497 
498 /*4
499 * read an integer (with reduction mod p)
500 */
501 static inline const char* nfEati(const char *s, int *i, const coeffs r)
502 {
503  return nEati((char *)s,i,r->m_nfCharP);
504 }
505 
506 /*2
507 * read a number
508 */
509 static const char * nfRead (const char *s, number *a, const coeffs r)
510 {
511  int i;
512  number z;
513  number n;
514 
515  s = nfEati(s, &i, r);
516  z=nfInit(i, r);
517  *a=z;
518  if (*s == '/')
519  {
520  s++;
521  s = nfEati(s, &i, r);
522  n=nfInit(i, r);
523  *a = nfDiv(z,n,r);
524  }
525  const char * const nf_Parameter = n_ParameterNames(r)[0];
526  const int N = strlen(nf_Parameter);
527  if (strncmp(s,nf_Parameter, N)==0)
528  {
529  s += N;
530  if ((*s >= '0') && (*s <= '9'))
531  {
532  s=eati(s,&i);
533  while (i>=r->m_nfCharQ1) i-=r->m_nfCharQ1;
534  }
535  else
536  i=1;
537  z=(number)(long)i;
538  *a=nfMult(*a,z,r);
539  }
540 #ifdef LDEBUG
541  nfTest(*a, r);
542 #endif
543  return s;
544 }
545 
546 int gf_tab_numdigits62 ( int q ); /*factory/gf_tabitil.cc */
547 int convertback62 ( char * p, int n ); /*factory/gf_tabitil.cc */
548 
550 
551 void nfShowMipo(const coeffs r)
552 {
553  int i=nfMinPoly[0];
554  int j=0;
555  loop
556  {
557  j++;
558  if (nfMinPoly[j]!=0)
559  StringAppend("%d*%s^%d",nfMinPoly[j],n_ParameterNames(r)[0],i);
560  i--;
561  if(i<0) break;
562  if (nfMinPoly[j]!=0)
563  StringAppendS("+");
564  }
565 }
566 
567 static void nfReadMipo(char *s)
568 {
569  const char *l=strchr(s,';')+1;
570  char *n;
571  int i=strtol(l,&n,10);
572  l=n;
573  int j=1;
574  nfMinPoly[0]=i;
575  while(i>=0)
576  {
577  nfMinPoly[j]=strtol(l,&n,10);
578  if (l==n) break;
579  l=n;
580  j++;
581  i--;
582  }
583  if (i>=0)
584  {
585  WerrorS("error in reading minpoly from gftables");
586  }
587 }
588 
589 /*2
590 * init global variables from files 'gftables/%d'
591 */
592 static void nfReadTable(const int c, const coeffs r)
593 {
594  //Print("GF(%d)\n",c);
595  if ((c==r->m_nfCharQ)||(c== -r->m_nfCharQ))
596  /*this field is already set*/ return;
597  int i=0;
598 
599  if ((c>255) ||(c!=IsPrime(c)))
600  {
601  while ((fftable[i]!=c) && (fftable[i]!=0))
602  i++;
603 
604  if (fftable[i]==0)
605  {
606  // illegal GF-table size: c
607  return;
608  }
609  }
610 
611  if (r->m_nfCharQ > 1)
612  {
613  omFreeSize( (ADDRESS)r->m_nfPlus1Table,(r->m_nfCharQ+1)*sizeof(unsigned short) );
614  r->m_nfPlus1Table=NULL;
615  }
616  if ((c>1) || (c<0))
617  {
618  if (c>1) r->m_nfCharQ = c;
619  else r->m_nfCharQ = -c;
620  char buf[100];
621  sprintf(buf,"gftables/%d",r->m_nfCharQ);
622  FILE * fp = feFopen(buf,"r",NULL,TRUE);
623  if (fp==NULL)
624  {
625  return;
626  }
627  if(!fgets( buf, sizeof(buf), fp)) return;
628  if(strcmp(buf,"@@ factory GF(q) table @@\n")!=0)
629  {
630  goto err;
631  }
632  if(!fgets( buf, sizeof(buf), fp))
633  {
634  goto err;
635  }
636  int q;
637  int res = -1;
638  do
639  {
640  res = sscanf(buf,"%d %d",&r->m_nfCharP,&q);
641  }
642  while((res < 0) and (errno == EINTR));
643 
644  nfReadMipo(buf);
645  r->m_nfCharQ1=r->m_nfCharQ-1;
646  //Print("nfCharQ=%d,nfCharQ1=%d,mipo=>>%s<<\n",nfCharQ,nfCharQ1,buf);
647  r->m_nfPlus1Table= (unsigned short *)omAlloc0( (r->m_nfCharQ+1)*sizeof(unsigned short) );
648  int digs = gf_tab_numdigits62( r->m_nfCharQ );
649  char * bufptr;
650  int i = 1;
651  int k;
652  while ( i < r->m_nfCharQ )
653  {
654  (void)fgets( buf, sizeof(buf), fp);
655  //( strlen( buffer ) == (size_t)digs * 30, "illegal table" );
656  bufptr = buf;
657  k = 0;
658  while ( (i < r->m_nfCharQ) && (k < 30) )
659  {
660  r->m_nfPlus1Table[i] = convertback62( bufptr, digs );
661  if(r->m_nfPlus1Table[i]>r->m_nfCharQ)
662  {
663  Print("wrong entry %d: %d(%c%c%c)\n",i,r->m_nfPlus1Table[i],bufptr[0],bufptr[1],bufptr[2]);
664  }
665  bufptr += digs;
666  if (r->m_nfPlus1Table[i]==r->m_nfCharQ)
667  {
668  if(i==r->m_nfCharQ1)
669  {
670  r->m_nfM1=0;
671  }
672  else
673  {
674  r->m_nfM1=i;
675  }
676  }
677  i++; k++;
678  }
679  }
680  r->m_nfPlus1Table[0]=r->m_nfPlus1Table[r->m_nfCharQ1];
681  }
682  else
683  r->m_nfCharQ=0;
684 #ifdef LDEBUG
685  nfTest((number)0, r);
686 #endif
687  return;
688 err:
689  Werror("illegal GF-table %d",r->m_nfCharQ);
690 }
691 
692 /*2
693 * map Z/p -> GF(p,n)
694 */
695 static number nfMapP(number c, const coeffs, const coeffs dst)
696 {
697  return nfInit((int)((long)c), dst);
698 }
699 
700 /*2
701 * map GF(p,n1) -> GF(p,n2), n1 < n2, n1 | n2
702 */
704 static number nfMapGG(number c, const coeffs src, const coeffs)
705 {
706  int i=(long)c;
707  i*= nfMapGG_factor;
708  while (i >src->m_nfCharQ1) i-=src->m_nfCharQ1;
709  return (number)((long)i);
710 }
711 /*2
712 * map GF(p,n1) -> GF(p,n2), n1 > n2, n2 | n1
713 */
714 static number nfMapGGrev(number c, const coeffs src, const coeffs)
715 {
716  int ex=(int)((long)c);
717  if ((ex % nfMapGG_factor)==0)
718  return (number)(((long)ex) / ((long)nfMapGG_factor));
719  else
720  return (number)(long)src->m_nfCharQ; /* 0 */
721 }
722 
723 static number nfMapMPZ(number c, const coeffs, const coeffs dst)
724 {
725  mpz_t tmp;
726  mpz_init(tmp);
727  mpz_mod_ui(tmp,(mpz_ptr)c,dst->m_nfCharP);
728  long l=mpz_get_si(tmp);
729  return nfInit(l,dst);
730 }
731 
732 static number nfInitMPZ(mpz_t m, const coeffs cf)
733 {
734  mpz_t tmp;
735  mpz_init(tmp);
736  mpz_mod_ui(tmp,m,cf->m_nfCharP);
737  long l=mpz_get_si(tmp);
738  return nfInit(l,cf);
739 }
740 
741 static number nfMapViaInt(number c, const coeffs src, const coeffs dst)
742 {
743  long i=src->cfInt(c,src);
744  if (i==0) return (number)(long)dst->m_nfCharQ;
745  while (i < 0) i += dst->m_nfCharP;
746  while (i >= dst->m_nfCharP) i -= dst->m_nfCharP;
747  return nfInit(i,dst);
748 }
749 
750 /*2
751 * set map function nMap ... -> GF(p,n)
752 */
753 static nMapFunc nfSetMap(const coeffs src, const coeffs dst)
754 {
755  if (nCoeff_is_GF(src))
756  {
757  const coeffs r = dst;
758  int q=src->ch;
759  if ((src->m_nfCharQ % q)==0) /* GF(p,n1) -> GF(p,n2), n2 > n1 */
760  {
761  // check if n2 is a multiple of n1
762  int n1=1;
763  int qq=r->m_nfCharP;
764  while(qq!=q) { qq *= r->m_nfCharP; n1++; }
765  int n2=1;
766  qq=r->m_nfCharP;
767  while(qq!=src->m_nfCharQ) { qq *= r->m_nfCharP; n2++; }
768  //Print("map %d^%d -> %d^%d\n",r->m_nfCharP,n1,r->m_nfCharP,n2);
769  if ((n2 % n1)==0)
770  {
771  int save_ch=r->m_nfCharQ;
772  nfReadTable(src->m_nfCharQ, r);
773  int nn=r->m_nfPlus1Table[0];
774  nfReadTable(save_ch, r);
775  nfMapGG_factor= r->m_nfPlus1Table[0] / nn;
776  //Print("nfMapGG_factor=%d (%d / %d)\n",nfMapGG_factor, r->m_nfPlus1Table[0], nn);
777  return nfMapGG;
778  }
779  else if ((n1 % n2)==0)
780  {
781  nfMapGG_factor= (n1/n2);
782  return nfMapGGrev;
783  }
784  else
785  return NULL;
786  }
787  }
788  if ((src->rep==n_rep_int) && nCoeff_is_Zp(src,dst->m_nfCharP))
789  {
790  return nfMapP; /* Z/p -> GF(p,n) */
791  }
792 
793  if (src->rep==n_rep_gap_rat) /*Q, bigint */
794  {
795  return nlModP; // FIXME? TODO? // extern number nlModP(number q, const coeffs Q, const coeffs Zp); // Map q \in QQ \to Zp // FIXME!
796  }
797  if (nCoeff_is_Z(src)) /* Z*/
798  {
799  return nfMapMPZ;
800  }
801  if (nCoeff_is_Zp(src) && (src->ch==dst->m_nfCharP)) /* Zp*/
802  {
803  return nfMapViaInt;
804  }
805 
806 
807  return NULL; /* default */
808 }
809 
810 static BOOLEAN nfCoeffIsEqual(const coeffs, n_coeffType, void*);
811 
812 static void nfKillChar(coeffs r)
813 {
814  char** p = (char**)n_ParameterNames(r);
815  /* only one parameter */
816  omFree( (ADDRESS)p[0] );
817  omFreeSize((ADDRESS)p, sizeof(char*));
818 }
819 
820 static char* nfCoeffName(const coeffs r)
821 {
822  STATIC_VAR char nfCoeffName_buf[32];
823  const char *p=n_ParameterNames(r)[0];
824  nfCoeffName_buf[31]='\0';
825  snprintf(nfCoeffName_buf,31,"%d,%s",r->m_nfCharQ,p);
826  return nfCoeffName_buf;
827 }
828 
829 static number nfRandom(siRandProc p,number ,number, const coeffs cf)
830 {
831  return (number)(long)(p() %(cf->m_nfCharQ+1));
832 }
833 
834 static void nfCoeffWrite (const coeffs r, BOOLEAN details)
835 {
836  // m_nfCharQ = p^k where p is the characteristic (r->CharP) and k is GFDegree
837  Print("ZZ/%d[%s]",r->m_nfCharQ,n_ParameterNames(r)[0]);
838  if ( details )
839  {
840  StringSetS("\n// minpoly : ");
841  nfShowMipo(r);
842  StringAppendS("");
843  char *s=StringEndS(); PrintS(s); omFree(s);
844  }
845  else PrintS("// minpoly : ...");
846 }
847 
848 static BOOLEAN nfCoeffIsEqual (const coeffs r, n_coeffType n, void * parameter)
849 {
850  if (n==n_GF) {
851  GFInfo* p = (GFInfo *)(parameter);
852  int c = (int)pow ((double)p->GFChar, (double)p->GFDegree);
853  if ((c == r->m_nfCharQ) && (strcmp(n_ParameterNames(r)[0], p->GFPar_name) == 0))
854  return TRUE;
855  }
856  return FALSE;
857 }
858 BOOLEAN nfInitChar(coeffs r, void * parameter)
859 {
860  // the variables:
861  assume( getCoeffType(r) == n_GF );
862 
863  GFInfo* p = (GFInfo *)(parameter);
864  assume (p->GFChar > 0);
865  assume (p->GFDegree > 0);
866  if(p->GFChar > (2<<15))
867  {
868 #ifndef SING_NDEBUG
869  WarnS("illegal characteristic");
870 #endif
871  return TRUE;
872  }
873 
874  const double check= log ((double) (p->GFChar));
875 
876  #define sixteenlog2 11.09035489
877  if( (p->GFDegree * check) > sixteenlog2 )
878  {
879 #ifndef SING_NDEBUG
880  Warn("Sorry: illegal size: %u ^ %u", p->GFChar, p->GFDegree );
881 #endif
882  return TRUE;
883  }
884 
885  r->is_field=TRUE;
886  r->is_domain=TRUE;
887  r->rep=n_rep_gf;
888  //r->cfInitChar=npInitChar;
889  r->cfKillChar=nfKillChar;
890  r->nCoeffIsEqual=nfCoeffIsEqual;
891  r->cfCoeffName=nfCoeffName;
892 
893  r->cfMult = nfMult;
894  r->cfSub = nfSub;
895  r->cfAdd = nfAdd;
896  r->cfDiv = nfDiv;
897  //r->cfIntMod= ndIntMod;
898  r->cfExactDiv= nfDiv;
899  r->cfInit = nfInit;
900  r->cfInitMPZ = nfInitMPZ;
901  //r->cfSize = ndSize;
902  r->cfInt = nfInt;
903  #ifdef HAVE_RINGS
904  //r->cfDivComp = NULL; // only for ring stuff
905  //r->cfIsUnit = NULL; // only for ring stuff
906  //r->cfGetUnit = NULL; // only for ring stuff
907  //r->cfExtGcd = NULL; // only for ring stuff
908  // r->cfDivBy = NULL; // only for ring stuff
909  #endif
910  r->cfInpNeg = nfNeg;
911  r->cfInvers= nfInvers;
912  //r->cfCopy = ndCopy;
913  //r->cfRePart = ndCopy;
914  //r->cfImPart = ndReturn0;
915 
916  r->cfWriteLong = nfWriteLong;
917  r->cfRead = nfRead;
918  //r->cfNormalize=ndNormalize;
919  r->cfGreater = nfGreater;
920  r->cfEqual = nfEqual;
921  r->cfIsZero = nfIsZero;
922  r->cfIsOne = nfIsOne;
923  r->cfIsMOne = nfIsMOne;
924  r->cfGreaterZero = nfGreaterZero;
925  r->cfPower = nfPower;
926  //r->cfGcd = ndGcd;
927  //r->cfLcm = ndGcd;
928  //r->cfDelete= ndDelete;
929  r->cfSetMap = nfSetMap;
930  //r->cfName = ndName;
931  // debug stuff
932  r->cfCoeffWrite=nfCoeffWrite;
933 
934  r->cfParDeg = nfParDeg;
935 
936  r->cfRandom = nfRandom;
937 
938 #ifdef LDEBUG
939  r->cfDBTest=nfDBTest;
940 #endif
941 
942 
943  const char * name = p->GFPar_name;
944 
945  r->m_nfCharQ = 0;
946  r->m_nfCharP = p->GFChar;
947  r->m_nfCharQ1 = 0;
948 
949  r->iNumberOfParameters = 1;
950  r->cfParameter = nfParameter;
951 
952  char ** pParameterNames = (char **) omAlloc(sizeof(char *));
953  assume( pParameterNames != NULL );
954  pParameterNames[0] = omStrDup(name);
955  assume( pParameterNames[0] != NULL );
956 
957  r->pParameterNames = (const char**)pParameterNames;
958 
959  r->m_nfPlus1Table= NULL;
960 
961  if (strlen(name) > 1)
962  r->cfWriteShort = nfWriteLong;
963  else
964  r->cfWriteShort = nfWriteShort;
965 
966  r->has_simple_Alloc=TRUE;
967  r->has_simple_Inverse=TRUE;
968 
969  int c = (int)pow ((double)p->GFChar, (double)p->GFDegree);
970 
971  nfReadTable(c, r);
972 
973  if( r->m_nfPlus1Table == NULL )
974  {
975  Werror("reading table for field with %d elements failed",c);
976  return TRUE;
977  }
978 
979 
980  assume (r -> m_nfCharQ > 0);
981 
982  r->ch = r->m_nfCharP;
983  assume( r->m_nfPlus1Table != NULL );
984 
985  return FALSE;
986 }
987 
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:119
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:56
int l
Definition: cfEzgcd.cc:100
int m
Definition: cfEzgcd.cc:128
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
int p
Definition: cfModGcd.cc:4078
CanonicalForm fp
Definition: cfModGcd.cc:4102
CanonicalForm cf
Definition: cfModGcd.cc:4083
CanonicalForm b
Definition: cfModGcd.cc:4103
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:839
static FORCE_INLINE BOOLEAN nCoeff_is_Z(const coeffs r)
Definition: coeffs.h:816
n_coeffType
Definition: coeffs.h:27
@ n_GF
\GF{p^n < 2^16}
Definition: coeffs.h:32
static FORCE_INLINE char const ** n_ParameterNames(const coeffs r)
Returns a (const!) pointer to (const char*) names of parameters.
Definition: coeffs.h:778
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:800
@ 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:75
const CanonicalForm int s
Definition: facAbsFact.cc:51
CanonicalForm res
Definition: facAbsFact.cc:60
int j
Definition: facHensel.cc:110
char name(const Variable &v)
Definition: factory.h:189
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 number nfMapViaInt(number c, const coeffs src, const coeffs dst)
Definition: ffields.cc:741
static BOOLEAN nfIsMOne(number a, const coeffs r)
Definition: ffields.cc:148
static number nfInitMPZ(mpz_t m, const coeffs cf)
Definition: ffields.cc:732
STATIC_VAR int nfMinPoly[16]
Definition: ffields.cc:549
static number nfAdd(number a, number b, const coeffs R)
Definition: ffields.cc:258
static number nfMapMPZ(number c, const coeffs, const coeffs dst)
Definition: ffields.cc:723
int convertback62(char *p, int n)
Definition: gf_tabutil.cc:50
STATIC_VAR int nfMapGG_factor
Definition: ffields.cc:703
static nMapFunc nfSetMap(const coeffs src, const coeffs dst)
Definition: ffields.cc:753
static void nfReadMipo(char *s)
Definition: ffields.cc:567
static number nfInit(long i, const coeffs r)
Definition: ffields.cc:191
void nfShowMipo(const coeffs r)
Show the mininimal polynom.... NOTE: this is used by char * sleftv::String(void *d,...
Definition: ffields.cc:551
BOOLEAN nfDBTest(number a, const char *f, const int l, const coeffs r)
Definition: ffields.cc:111
int gf_tab_numdigits62(int q)
Definition: gf_tabutil.cc:12
static void nfKillChar(coeffs r)
Definition: ffields.cc:812
static int nfParDeg(number n, const coeffs r)
Definition: ffields.cc:228
const unsigned short fftable[]
Definition: ffields.cc:31
static long nfInt(number &n, const coeffs r)
Definition: ffields.cc:240
#define sixteenlog2
static number nfMult(number a, number b, const coeffs r)
Definition: ffields.cc:171
static BOOLEAN nfGreaterZero(number k, const coeffs r)
Definition: ffields.cc:160
BOOLEAN nfInitChar(coeffs r, void *parameter)
Definition: ffields.cc:858
static void nfWriteShort(number a, const coeffs r)
Definition: ffields.cc:440
static char * nfCoeffName(const coeffs r)
Definition: ffields.cc:820
#define nfTest(N, R)
Definition: ffields.cc:131
static number nfSub(number a, number b, const coeffs r)
Definition: ffields.cc:315
static number nfRandom(siRandProc p, number, number, const coeffs cf)
Definition: ffields.cc:829
static BOOLEAN nfIsOne(number a, const coeffs r)
Definition: ffields.cc:324
static void nfCoeffWrite(const coeffs r, BOOLEAN details)
Definition: ffields.cc:834
static const char * nfEati(const char *s, int *i, const coeffs r)
Definition: ffields.cc:501
static const char * nfRead(const char *s, number *a, const coeffs r)
Definition: ffields.cc:509
static BOOLEAN nfGreater(number a, number b, const coeffs r)
Definition: ffields.cc:382
static number nfNeg(number c, const coeffs r)
Definition: ffields.cc:297
static BOOLEAN nfIsZero(number a, const coeffs r)
Definition: ffields.cc:137
static BOOLEAN nfCoeffIsEqual(const coeffs, n_coeffType, void *)
Definition: ffields.cc:848
static number nfMapGGrev(number c, const coeffs src, const coeffs)
Definition: ffields.cc:714
static BOOLEAN nfEqual(number a, number b, const coeffs r)
Definition: ffields.cc:394
static number nfMapP(number c, const coeffs, const coeffs dst)
Definition: ffields.cc:695
static void nfReadTable(const int c, const coeffs r)
Definition: ffields.cc:592
static void nfWriteLong(number a, const coeffs r)
Definition: ffields.cc:406
static number nfDiv(number a, number b, const coeffs r)
Definition: ffields.cc:335
static number nfParameter(int i, const coeffs)
Definition: ffields.cc:215
static number nfMapGG(number c, const coeffs src, const coeffs)
Definition: ffields.cc:704
static number nfInvers(number c, const coeffs r)
Definition: ffields.cc:363
static void nfPower(number a, int i, number *result, const coeffs r)
Definition: ffields.cc:473
#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:1577
#define assume(x)
Definition: mod2.h:389
#define LDEBUG
Definition: mod2.h:307
gmp_float log(const gmp_float &a)
Definition: mpr_complex.cc:343
The main handler for Singular numbers which are suitable for Singular polynomials.
char * nEati(char *s, int *i, int m)
divide by the first (leading) number and return it, i.e. make monic
Definition: numbers.cc:656
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:75