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 */
nfDBTest(number a,const char * f,const int l,const coeffs r)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 */
nfIsZero(number a,const coeffs r)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 */
nfIsMOne(number a,const coeffs r)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 */
nfGreaterZero(number k,const coeffs r)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 */
nfMult(number a,number b,const coeffs r)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 */
nfInit(long i,const coeffs r)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 */
nfParameter(int i,const coeffs)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 */
nfParDeg(number n,const coeffs r)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 */
nfInt(number & n,const coeffs r)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 */
nfAdd(number a,number b,const coeffs R)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 */
nfNeg(number c,const coeffs r)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 */
nfSub(number a,number b,const coeffs r)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 */
nfIsOne(number a,const coeffs r)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 */
nfDiv(number a,number b,const coeffs r)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 */
nfInvers(number c,const coeffs r)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 */
nfGreater(number a,number b,const coeffs r)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 */
nfEqual(number a,number b,const coeffs r)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 */
nfWriteLong(number a,const coeffs r)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 {
427 StringAppendS(n_ParameterNames(r)[0]);
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 */
nfWriteShort(number a,const coeffs r)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 {
461 StringAppendS(n_ParameterNames(r)[0]);
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 */
nfPower(number a,int i,number * result,const coeffs r)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 */
nfEati(const char * s,int * i,const coeffs r)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 */
nfRead(const char * s,number * a,const coeffs r)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
549 STATIC_VAR int nfMinPoly[16];
550
nfShowMipo(const coeffs r)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
nfReadMipo(char * s)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 */
nfReadTable(const int c,const coeffs r)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 */
nfMapP(number c,const coeffs,const coeffs dst)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 */
703 STATIC_VAR int nfMapGG_factor;
nfMapGG(number c,const coeffs src,const coeffs)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 */
nfMapGGrev(number c,const coeffs src,const coeffs)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
nfMapMPZ(number c,const coeffs,const coeffs dst)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
nfInitMPZ(mpz_t m,const coeffs cf)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
nfMapViaInt(number c,const coeffs src,const coeffs dst)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 */
nfSetMap(const coeffs src,const coeffs dst)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
nfKillChar(coeffs r)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
nfCoeffName(const coeffs r)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
nfRandom(siRandProc p,number,number,const coeffs cf)829 static number nfRandom(siRandProc p,number ,number, const coeffs cf)
830 {
831 return (number)(long)(p() %(cf->m_nfCharQ+1));
832 }
833
nfCoeffWrite(const coeffs r,BOOLEAN details)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
nfCoeffIsEqual(const coeffs r,n_coeffType n,void * parameter)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 }
nfInitChar(coeffs r,void * parameter)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 ((IsPrime(p->GFChar)==p->GFChar)&&(p->GFDegree==1)) /* for oscar-system/Singular.jl/issues/177 */
867 {
868 return npInitChar(r,(void*)(long)p->GFChar);
869 }
870 if(p->GFChar > (2<<15))
871 {
872 #ifndef SING_NDEBUG
873 WarnS("illegal characteristic");
874 #endif
875 return TRUE;
876 }
877
878 const double check= log ((double) (p->GFChar));
879
880 #define sixteenlog2 11.09035489
881 if( (p->GFDegree * check) > sixteenlog2 )
882 {
883 #ifndef SING_NDEBUG
884 Warn("Sorry: illegal size: %u ^ %u", p->GFChar, p->GFDegree );
885 #endif
886 return TRUE;
887 }
888
889 r->is_field=TRUE;
890 r->is_domain=TRUE;
891 r->rep=n_rep_gf;
892 //r->cfInitChar=npInitChar;
893 r->cfKillChar=nfKillChar;
894 r->nCoeffIsEqual=nfCoeffIsEqual;
895 r->cfCoeffName=nfCoeffName;
896
897 r->cfMult = nfMult;
898 r->cfSub = nfSub;
899 r->cfAdd = nfAdd;
900 r->cfDiv = nfDiv;
901 //r->cfIntMod= ndIntMod;
902 r->cfExactDiv= nfDiv;
903 r->cfInit = nfInit;
904 r->cfInitMPZ = nfInitMPZ;
905 //r->cfSize = ndSize;
906 r->cfInt = nfInt;
907 #ifdef HAVE_RINGS
908 //r->cfDivComp = NULL; // only for ring stuff
909 //r->cfIsUnit = NULL; // only for ring stuff
910 //r->cfGetUnit = NULL; // only for ring stuff
911 //r->cfExtGcd = NULL; // only for ring stuff
912 // r->cfDivBy = NULL; // only for ring stuff
913 #endif
914 r->cfInpNeg = nfNeg;
915 r->cfInvers= nfInvers;
916 //r->cfCopy = ndCopy;
917 //r->cfRePart = ndCopy;
918 //r->cfImPart = ndReturn0;
919
920 r->cfWriteLong = nfWriteLong;
921 r->cfRead = nfRead;
922 //r->cfNormalize=ndNormalize;
923 r->cfGreater = nfGreater;
924 r->cfEqual = nfEqual;
925 r->cfIsZero = nfIsZero;
926 r->cfIsOne = nfIsOne;
927 r->cfIsMOne = nfIsMOne;
928 r->cfGreaterZero = nfGreaterZero;
929 r->cfPower = nfPower;
930 //r->cfGcd = ndGcd;
931 //r->cfLcm = ndGcd;
932 //r->cfDelete= ndDelete;
933 r->cfSetMap = nfSetMap;
934 //r->cfName = ndName;
935 // debug stuff
936 r->cfCoeffWrite=nfCoeffWrite;
937
938 r->cfParDeg = nfParDeg;
939
940 r->cfRandom = nfRandom;
941
942 #ifdef LDEBUG
943 r->cfDBTest=nfDBTest;
944 #endif
945
946
947 const char * name = p->GFPar_name;
948
949 r->m_nfCharQ = 0;
950 r->m_nfCharP = p->GFChar;
951 r->m_nfCharQ1 = 0;
952
953 r->iNumberOfParameters = 1;
954 r->cfParameter = nfParameter;
955
956 char ** pParameterNames = (char **) omAlloc(sizeof(char *));
957 assume( pParameterNames != NULL );
958 pParameterNames[0] = omStrDup(name);
959 assume( pParameterNames[0] != NULL );
960
961 r->pParameterNames = (const char**)pParameterNames;
962
963 r->m_nfPlus1Table= NULL;
964
965 if (strlen(name) > 1)
966 r->cfWriteShort = nfWriteLong;
967 else
968 r->cfWriteShort = nfWriteShort;
969
970 r->has_simple_Alloc=TRUE;
971 r->has_simple_Inverse=TRUE;
972
973 int c = (int)pow ((double)p->GFChar, (double)p->GFDegree);
974
975 nfReadTable(c, r);
976
977 if( r->m_nfPlus1Table == NULL )
978 {
979 Werror("reading table for field with %d elements failed",c);
980 return TRUE;
981 }
982
983
984 assume (r -> m_nfCharQ > 0);
985
986 r->ch = r->m_nfCharP;
987 assume( r->m_nfPlus1Table != NULL );
988
989 return FALSE;
990 }
991
992