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