My Project  UNKNOWN_GIT_VERSION
rmodulon.cc
Go to the documentation of this file.
1 /****************************************
2 * Computer Algebra System SINGULAR *
3 ****************************************/
4 /*
5 * ABSTRACT: numbers modulo n
6 */
7 #include "misc/auxiliary.h"
8 #include "omalloc/omalloc.h"
9 
10 #include "misc/mylimits.h"
11 #include "misc/prime.h" // IsPrime
12 #include "reporter/reporter.h"
13 
14 #include "coeffs/si_gmp.h"
15 #include "coeffs/coeffs.h"
16 #include "coeffs/modulop.h"
17 #include "coeffs/rintegers.h"
18 #include "coeffs/numbers.h"
19 
20 #include "coeffs/mpr_complex.h"
21 
22 #include "coeffs/longrat.h"
23 #include "coeffs/rmodulon.h"
24 
25 #include <string.h>
26 
27 #ifdef HAVE_RINGS
28 
29 void nrnWrite (number a, const coeffs);
30 #ifdef LDEBUG
31 BOOLEAN nrnDBTest (number a, const char *f, const int l, const coeffs r);
32 #endif
33 
34 extern omBin gmp_nrz_bin;
35 
36 static void nrnCoeffWrite (const coeffs r, BOOLEAN /*details*/)
37 {
38  size_t l = (size_t)mpz_sizeinbase(r->modBase, 10) + 2;
39  char* s = (char*) omAlloc(l);
40  s= mpz_get_str (s, 10, r->modBase);
41 
42  #ifdef TEST_ZN_AS_ZP
43  if (l<10)
44  {
45  if (nCoeff_is_Zn(r)) Print("ZZ/%s", s);
46  else if (nCoeff_is_Ring_PtoM(r)) Print("ZZ/(%s^%lu)", s, r->modExponent);
47  }
48  else
49  #endif
50  {
51  if (nCoeff_is_Zn(r)) Print("ZZ/bigint(%s)", s);
52  else if (nCoeff_is_Ring_PtoM(r)) Print("ZZ/(bigint(%s)^%lu)", s, r->modExponent);
53  }
54 
55  omFreeSize((ADDRESS)s, l);
56 }
57 
59 {
60  const char start[]="ZZ/bigint(";
61  const int start_len=strlen(start);
62  if (strncmp(s,start,start_len)==0)
63  {
64  s+=start_len;
65  mpz_t z;
66  mpz_init(z);
67  s=nEatLong(s,z);
68  ZnmInfo info;
69  info.base=z;
70  info.exp= 1;
71  while ((*s!='\0') && (*s!=')')) s++;
72  // expect ")" or ")^exp"
73  if (*s=='\0') { mpz_clear(z); return NULL; }
74  if (((*s)==')') && (*(s+1)=='^'))
75  {
76  s=s+2;
77  s=nEati(s,&(info.exp),0);
78  return nInitChar(n_Znm,(void*) &info);
79  }
80  else
81  return nInitChar(n_Zn,(void*) &info);
82  }
83  else return NULL;
84 }
85 
86 static char* nrnCoeffName_buff=NULL;
87 static char* nrnCoeffName(const coeffs r)
88 {
90  size_t l = (size_t)mpz_sizeinbase(r->modBase, 10) + 2;
91  char* s = (char*) omAlloc(l);
92  l+=22;
93  nrnCoeffName_buff=(char*)omAlloc(l);
94  s= mpz_get_str (s, 10, r->modBase);
95  int ll;
96  if (nCoeff_is_Zn(r))
97  ll=snprintf(nrnCoeffName_buff,l,"ZZ/bigint(%s)",s);
98  else if (nCoeff_is_Ring_PtoM(r))
99  ll=snprintf(nrnCoeffName_buff,l,"ZZ/bigint(%s)^%lu",s,r->modExponent);
100  assume(ll<(int)l); // otherwise nrnCoeffName_buff too small
101  omFreeSize((ADDRESS)s, l-22);
102  return nrnCoeffName_buff;
103 }
104 
105 static BOOLEAN nrnCoeffIsEqual(const coeffs r, n_coeffType n, void * parameter)
106 {
107  /* test, if r is an instance of nInitCoeffs(n,parameter) */
108  ZnmInfo *info=(ZnmInfo*)parameter;
109  return (n==r->type) && (r->modExponent==info->exp)
110  && (mpz_cmp(r->modBase,info->base)==0);
111 }
112 
113 static char* nrnCoeffString(const coeffs r)
114 {
115  size_t l = (size_t)mpz_sizeinbase(r->modBase, 10) +2;
116  char* b = (char*) omAlloc(l);
117  b= mpz_get_str (b, 10, r->modBase);
118  char* s = (char*) omAlloc(15+l);
119  if (nCoeff_is_Zn(r)) sprintf(s,"ZZ/%s",b);
120  else /*if (nCoeff_is_Ring_PtoM(r))*/ sprintf(s,"ZZ/(bigint(%s)^%lu)",b,r->modExponent);
121  omFreeSize(b,l);
122  return s;
123 }
124 
125 static void nrnKillChar(coeffs r)
126 {
127  mpz_clear(r->modNumber);
128  mpz_clear(r->modBase);
129  omFreeBin((void *) r->modBase, gmp_nrz_bin);
130  omFreeBin((void *) r->modNumber, gmp_nrz_bin);
131 }
132 
133 static coeffs nrnQuot1(number c, const coeffs r)
134 {
135  coeffs rr;
136  long ch = r->cfInt(c, r);
137  mpz_t a,b;
138  mpz_init_set(a, r->modNumber);
139  mpz_init_set_ui(b, ch);
140  mpz_t gcd;
141  mpz_init(gcd);
142  mpz_gcd(gcd, a,b);
143  if(mpz_cmp_ui(gcd, 1) == 0)
144  {
145  WerrorS("constant in q-ideal is coprime to modulus in ground ring");
146  WerrorS("Unable to create qring!");
147  return NULL;
148  }
149  if(r->modExponent == 1)
150  {
151  ZnmInfo info;
152  info.base = gcd;
153  info.exp = (unsigned long) 1;
154  rr = nInitChar(n_Zn, (void*)&info);
155  }
156  else
157  {
158  ZnmInfo info;
159  info.base = r->modBase;
160  int kNew = 1;
161  mpz_t baseTokNew;
162  mpz_init(baseTokNew);
163  mpz_set(baseTokNew, r->modBase);
164  while(mpz_cmp(gcd, baseTokNew) > 0)
165  {
166  kNew++;
167  mpz_mul(baseTokNew, baseTokNew, r->modBase);
168  }
169  //printf("\nkNew = %i\n",kNew);
170  info.exp = kNew;
171  mpz_clear(baseTokNew);
172  rr = nInitChar(n_Znm, (void*)&info);
173  }
174  mpz_clear(gcd);
175  return(rr);
176 }
177 
178 static number nrnCopy(number a, const coeffs)
179 {
180  mpz_ptr erg = (mpz_ptr) omAllocBin(gmp_nrz_bin);
181  mpz_init_set(erg, (mpz_ptr) a);
182  return (number) erg;
183 }
184 
185 /*
186  * create a number from int
187  */
188 static number nrnInit(long i, const coeffs r)
189 {
190  mpz_ptr erg = (mpz_ptr) omAllocBin(gmp_nrz_bin);
191  mpz_init_set_si(erg, i);
192  mpz_mod(erg, erg, r->modNumber);
193  return (number) erg;
194 }
195 
196 /*
197  * convert a number to int
198  */
199 static long nrnInt(number &n, const coeffs)
200 {
201  return mpz_get_si((mpz_ptr) n);
202 }
203 
204 #if SI_INTEGER_VARIANT==2
205 #define nrnDelete nrzDelete
206 #define nrnSize nrzSize
207 #else
208 static void nrnDelete(number *a, const coeffs)
209 {
210  if (*a != NULL)
211  {
212  mpz_clear((mpz_ptr) *a);
213  omFreeBin((void *) *a, gmp_nrz_bin);
214  *a = NULL;
215  }
216 }
217 static int nrnSize(number a, const coeffs)
218 {
219  mpz_ptr p=(mpz_ptr)a;
220  int s=p->_mp_alloc;
221  if (s==1) s=(mpz_cmp_ui(p,0)!=0);
222  return s;
223 }
224 #endif
225 /*
226  * Multiply two numbers
227  */
228 static number nrnMult(number a, number b, const coeffs r)
229 {
230  mpz_ptr erg = (mpz_ptr)omAllocBin(gmp_nrz_bin);
231  mpz_init(erg);
232  mpz_mul(erg, (mpz_ptr)a, (mpz_ptr) b);
233  mpz_mod(erg, erg, r->modNumber);
234  return (number) erg;
235 }
236 
237 static void nrnPower(number a, int i, number * result, const coeffs r)
238 {
239  mpz_ptr erg = (mpz_ptr)omAllocBin(gmp_nrz_bin);
240  mpz_init(erg);
241  mpz_powm_ui(erg, (mpz_ptr)a, i, r->modNumber);
242  *result = (number) erg;
243 }
244 
245 static number nrnAdd(number a, number b, const coeffs r)
246 {
247  mpz_ptr erg = (mpz_ptr)omAllocBin(gmp_nrz_bin);
248  mpz_init(erg);
249  mpz_add(erg, (mpz_ptr)a, (mpz_ptr) b);
250  mpz_mod(erg, erg, r->modNumber);
251  return (number) erg;
252 }
253 
254 static number nrnSub(number a, number b, const coeffs r)
255 {
256  mpz_ptr erg = (mpz_ptr)omAllocBin(gmp_nrz_bin);
257  mpz_init(erg);
258  mpz_sub(erg, (mpz_ptr)a, (mpz_ptr) b);
259  mpz_mod(erg, erg, r->modNumber);
260  return (number) erg;
261 }
262 
263 static BOOLEAN nrnIsZero(number a, const coeffs)
264 {
265  return 0 == mpz_cmpabs_ui((mpz_ptr)a, 0);
266 }
267 
268 static number nrnNeg(number c, const coeffs r)
269 {
270  if( !nrnIsZero(c, r) )
271  // Attention: This method operates in-place.
272  mpz_sub((mpz_ptr)c, r->modNumber, (mpz_ptr)c);
273  return c;
274 }
275 
276 static number nrnInvers(number c, const coeffs r)
277 {
278  mpz_ptr erg = (mpz_ptr)omAllocBin(gmp_nrz_bin);
279  mpz_init(erg);
280  mpz_invert(erg, (mpz_ptr)c, r->modNumber);
281  return (number) erg;
282 }
283 
284 /*
285  * Give the largest k, such that a = x * k, b = y * k has
286  * a solution.
287  * a may be NULL, b not
288  */
289 static number nrnGcd(number a, number b, const coeffs r)
290 {
291  mpz_ptr erg = (mpz_ptr)omAllocBin(gmp_nrz_bin);
292  mpz_init_set(erg, r->modNumber);
293  if (a != NULL) mpz_gcd(erg, erg, (mpz_ptr)a);
294  mpz_gcd(erg, erg, (mpz_ptr)b);
295  if(mpz_cmp(erg,r->modNumber)==0)
296  {
297  mpz_clear(erg);
299  return nrnInit(0,r);
300  }
301  return (number)erg;
302 }
303 
304 /*
305  * Give the smallest k, such that a * x = k = b * y has a solution
306  * TODO: lcm(gcd,gcd) better than gcd(lcm) ?
307  */
308 static number nrnLcm(number a, number b, const coeffs r)
309 {
310  number erg = nrnGcd(NULL, a, r);
311  number tmp = nrnGcd(NULL, b, r);
312  mpz_lcm((mpz_ptr)erg, (mpz_ptr)erg, (mpz_ptr)tmp);
313  nrnDelete(&tmp, r);
314  return (number)erg;
315 }
316 
317 /* Not needed any more, but may have room for improvement
318  number nrnGcd3(number a,number b, number c,ring r)
319 {
320  mpz_ptr erg = (mpz_ptr) omAllocBin(gmp_nrz_bin);
321  mpz_init(erg);
322  if (a == NULL) a = (number)r->modNumber;
323  if (b == NULL) b = (number)r->modNumber;
324  if (c == NULL) c = (number)r->modNumber;
325  mpz_gcd(erg, (mpz_ptr)a, (mpz_ptr)b);
326  mpz_gcd(erg, erg, (mpz_ptr)c);
327  mpz_gcd(erg, erg, r->modNumber);
328  return (number)erg;
329 }
330 */
331 
332 /*
333  * Give the largest k, such that a = x * k, b = y * k has
334  * a solution and r, s, s.t. k = s*a + t*b
335  * CF: careful: ExtGcd is wrong as implemented (or at least may not
336  * give you what you want:
337  * ExtGcd(5, 10 modulo 12):
338  * the gcdext will return 5 = 1*5 + 0*10
339  * however, mod 12, the gcd should be 1
340  */
341 static number nrnExtGcd(number a, number b, number *s, number *t, const coeffs r)
342 {
343  mpz_ptr erg = (mpz_ptr)omAllocBin(gmp_nrz_bin);
344  mpz_ptr bs = (mpz_ptr)omAllocBin(gmp_nrz_bin);
345  mpz_ptr bt = (mpz_ptr)omAllocBin(gmp_nrz_bin);
346  mpz_init(erg);
347  mpz_init(bs);
348  mpz_init(bt);
349  mpz_gcdext(erg, bs, bt, (mpz_ptr)a, (mpz_ptr)b);
350  mpz_mod(bs, bs, r->modNumber);
351  mpz_mod(bt, bt, r->modNumber);
352  *s = (number)bs;
353  *t = (number)bt;
354  return (number)erg;
355 }
356 
357 static BOOLEAN nrnIsOne(number a, const coeffs)
358 {
359  return 0 == mpz_cmp_si((mpz_ptr)a, 1);
360 }
361 
362 static BOOLEAN nrnEqual(number a, number b, const coeffs)
363 {
364  return 0 == mpz_cmp((mpz_ptr)a, (mpz_ptr)b);
365 }
366 
367 static number nrnGetUnit(number k, const coeffs r)
368 {
369  if (mpz_divisible_p(r->modNumber, (mpz_ptr)k)) return nrnInit(1,r);
370 
371  mpz_ptr unit = (mpz_ptr)nrnGcd(NULL, k, r);
372  mpz_tdiv_q(unit, (mpz_ptr)k, unit);
373  mpz_ptr gcd = (mpz_ptr)nrnGcd(NULL, (number)unit, r);
374  if (!nrnIsOne((number)gcd,r))
375  {
376  mpz_ptr ctmp;
377  // tmp := unit^2
378  mpz_ptr tmp = (mpz_ptr) nrnMult((number) unit,(number) unit,r);
379  // gcd_new := gcd(tmp, 0)
380  mpz_ptr gcd_new = (mpz_ptr) nrnGcd(NULL, (number) tmp, r);
381  while (!nrnEqual((number) gcd_new,(number) gcd,r))
382  {
383  // gcd := gcd_new
384  ctmp = gcd;
385  gcd = gcd_new;
386  gcd_new = ctmp;
387  // tmp := tmp * unit
388  mpz_mul(tmp, tmp, unit);
389  mpz_mod(tmp, tmp, r->modNumber);
390  // gcd_new := gcd(tmp, 0)
391  mpz_gcd(gcd_new, tmp, r->modNumber);
392  }
393  // unit := unit + modNumber / gcd_new
394  mpz_tdiv_q(tmp, r->modNumber, gcd_new);
395  mpz_add(unit, unit, tmp);
396  mpz_mod(unit, unit, r->modNumber);
397  nrnDelete((number*) &gcd_new, r);
398  nrnDelete((number*) &tmp, r);
399  }
400  nrnDelete((number*) &gcd, r);
401  return (number)unit;
402 }
403 
404 /* XExtGcd returns a unimodular matrix ((s,t)(u,v)) sth.
405  * (a,b)^t ((st)(uv)) = (g,0)^t
406  * Beware, the ExtGcd will not necessaairly do this.
407  * Problem: if g = as+bt then (in Z/nZ) it follows NOT that
408  * 1 = (a/g)s + (b/g) t
409  * due to the zero divisors.
410  */
411 
412 //#define CF_DEB;
413 static number nrnXExtGcd(number a, number b, number *s, number *t, number *u, number *v, const coeffs r)
414 {
415  number xx;
416 #ifdef CF_DEB
417  StringSetS("XExtGcd of ");
418  nrnWrite(a, r);
419  StringAppendS("\t");
420  nrnWrite(b, r);
421  StringAppendS(" modulo ");
422  nrnWrite(xx = (number)r->modNumber, r);
423  Print("%s\n", StringEndS());
424 #endif
425 
426  mpz_ptr one = (mpz_ptr)omAllocBin(gmp_nrz_bin);
427  mpz_ptr erg = (mpz_ptr)omAllocBin(gmp_nrz_bin);
428  mpz_ptr bs = (mpz_ptr)omAllocBin(gmp_nrz_bin);
429  mpz_ptr bt = (mpz_ptr)omAllocBin(gmp_nrz_bin);
430  mpz_ptr bu = (mpz_ptr)omAllocBin(gmp_nrz_bin);
431  mpz_ptr bv = (mpz_ptr)omAllocBin(gmp_nrz_bin);
432  mpz_init(erg);
433  mpz_init(one);
434  mpz_init_set(bs, (mpz_ptr) a);
435  mpz_init_set(bt, (mpz_ptr) b);
436  mpz_init(bu);
437  mpz_init(bv);
438  mpz_gcd(erg, bs, bt);
439 
440 #ifdef CF_DEB
441  StringSetS("1st gcd:");
442  nrnWrite(xx= (number)erg, r);
443 #endif
444 
445  mpz_gcd(erg, erg, r->modNumber);
446 
447  mpz_div(bs, bs, erg);
448  mpz_div(bt, bt, erg);
449 
450 #ifdef CF_DEB
451  Print("%s\n", StringEndS());
452  StringSetS("xgcd: ");
453 #endif
454 
455  mpz_gcdext(one, bu, bv, bs, bt);
456  number ui = nrnGetUnit(xx = (number) one, r);
457 #ifdef CF_DEB
458  n_Write(xx, r);
459  StringAppendS("\t");
460  n_Write(ui, r);
461  Print("%s\n", StringEndS());
462 #endif
463  nrnDelete(&xx, r);
464  if (!nrnIsOne(ui, r))
465  {
466 #ifdef CF_DEB
467  PrintS("Scaling\n");
468 #endif
469  number uii = nrnInvers(ui, r);
470  nrnDelete(&ui, r);
471  ui = uii;
472  mpz_ptr uu = (mpz_ptr)omAllocBin(gmp_nrz_bin);
473  mpz_init_set(uu, (mpz_ptr)ui);
474  mpz_mul(bu, bu, uu);
475  mpz_mul(bv, bv, uu);
476  mpz_clear(uu);
477  omFreeBin(uu, gmp_nrz_bin);
478  }
479  nrnDelete(&ui, r);
480 #ifdef CF_DEB
481  StringSetS("xgcd");
482  nrnWrite(xx= (number)bs, r);
483  StringAppendS("*");
484  nrnWrite(xx= (number)bu, r);
485  StringAppendS(" + ");
486  nrnWrite(xx= (number)bt, r);
487  StringAppendS("*");
488  nrnWrite(xx= (number)bv, r);
489  Print("%s\n", StringEndS());
490 #endif
491 
492  mpz_mod(bs, bs, r->modNumber);
493  mpz_mod(bt, bt, r->modNumber);
494  mpz_mod(bu, bu, r->modNumber);
495  mpz_mod(bv, bv, r->modNumber);
496  *s = (number)bu;
497  *t = (number)bv;
498  *u = (number)bt;
499  *u = nrnNeg(*u, r);
500  *v = (number)bs;
501  return (number)erg;
502 }
503 
504 static BOOLEAN nrnIsMOne(number a, const coeffs r)
505 {
506  if((r->ch==2) && (nrnIsOne(a,r))) return FALSE;
507  mpz_t t; mpz_init_set(t, (mpz_ptr)a);
508  mpz_add_ui(t, t, 1);
509  bool erg = (0 == mpz_cmp(t, r->modNumber));
510  mpz_clear(t);
511  return erg;
512 }
513 
514 static BOOLEAN nrnGreater(number a, number b, const coeffs)
515 {
516  return 0 < mpz_cmp((mpz_ptr)a, (mpz_ptr)b);
517 }
518 
519 static BOOLEAN nrnGreaterZero(number k, const coeffs cf)
520 {
521  if (cf->is_field)
522  {
523  if (mpz_cmp_ui(cf->modBase,2)==0)
524  {
525  return TRUE;
526  }
527  mpz_t ch2; mpz_init_set(ch2, cf->modBase);
528  mpz_sub_ui(ch2,ch2,1);
529  mpz_divexact_ui(ch2,ch2,2);
530  if (mpz_cmp(ch2,(mpz_ptr)k)<0)
531  return FALSE;
532  mpz_clear(ch2);
533  }
534  return 0 < mpz_sgn1((mpz_ptr)k);
535 }
536 
537 static BOOLEAN nrnIsUnit(number a, const coeffs r)
538 {
539  number tmp = nrnGcd(a, (number)r->modNumber, r);
540  bool res = nrnIsOne(tmp, r);
541  nrnDelete(&tmp, r);
542  return res;
543 }
544 
545 static number nrnAnn(number k, const coeffs r)
546 {
547  mpz_ptr tmp = (mpz_ptr) omAllocBin(gmp_nrz_bin);
548  mpz_init(tmp);
549  mpz_gcd(tmp, (mpz_ptr) k, r->modNumber);
550  if (mpz_cmp_si(tmp, 1)==0)
551  {
552  mpz_set_ui(tmp, 0);
553  return (number) tmp;
554  }
555  mpz_divexact(tmp, r->modNumber, tmp);
556  return (number) tmp;
557 }
558 
559 static BOOLEAN nrnDivBy(number a, number b, const coeffs r)
560 {
561  /* b divides a iff b/gcd(a, b) is a unit in the given ring: */
562  number n = nrnGcd(a, b, r);
563  mpz_tdiv_q((mpz_ptr)n, (mpz_ptr)b, (mpz_ptr)n);
564  bool result = nrnIsUnit(n, r);
565  nrnDelete(&n, NULL);
566  return result;
567 }
568 
569 static int nrnDivComp(number a, number b, const coeffs r)
570 {
571  if (nrnEqual(a, b,r)) return 2;
572  if (mpz_divisible_p((mpz_ptr) a, (mpz_ptr) b)) return -1;
573  if (mpz_divisible_p((mpz_ptr) b, (mpz_ptr) a)) return 1;
574  return 0;
575 }
576 
577 static number nrnDiv(number a, number b, const coeffs r)
578 {
579  if (r->is_field)
580  {
581  number inv=nrnInvers(b,r);
582  number erg=nrnMult(a,inv,r);
583  nrnDelete(&inv,r);
584  return erg;
585  }
586  mpz_ptr erg = (mpz_ptr)omAllocBin(gmp_nrz_bin);
587  mpz_init(erg);
588  if (mpz_divisible_p((mpz_ptr)a, (mpz_ptr)b))
589  {
590  mpz_divexact(erg, (mpz_ptr)a, (mpz_ptr)b);
591  return (number)erg;
592  }
593  else
594  {
595  mpz_ptr gcd = (mpz_ptr)nrnGcd(a, b, r);
596  mpz_divexact(erg, (mpz_ptr)b, gcd);
597  if (!nrnIsUnit((number)erg, r))
598  {
599  WerrorS("Division not possible, even by cancelling zero divisors.");
600  nrnDelete((number*) &gcd, r);
601  nrnDelete((number*) &erg, r);
602  return (number)NULL;
603  }
604  // a / gcd(a,b) * [b / gcd (a,b)]^(-1)
605  mpz_ptr tmp = (mpz_ptr)nrnInvers((number) erg,r);
606  mpz_divexact(erg, (mpz_ptr)a, gcd);
607  mpz_mul(erg, erg, tmp);
608  nrnDelete((number*) &gcd, r);
609  nrnDelete((number*) &tmp, r);
610  mpz_mod(erg, erg, r->modNumber);
611  return (number)erg;
612  }
613 }
614 
615 static number nrnMod(number a, number b, const coeffs r)
616 {
617  /*
618  We need to return the number rr which is uniquely determined by the
619  following two properties:
620  (1) 0 <= rr < |b| (with respect to '<' and '<=' performed in Z x Z)
621  (2) There exists some k in the integers Z such that a = k * b + rr.
622  Consider g := gcd(n, |b|). Note that then |b|/g is a unit in Z/n.
623  Now, there are three cases:
624  (a) g = 1
625  Then |b| is a unit in Z/n, i.e. |b| (and also b) divides a.
626  Thus rr = 0.
627  (b) g <> 1 and g divides a
628  Then a = (a/g) * (|b|/g)^(-1) * b (up to sign), i.e. again rr = 0.
629  (c) g <> 1 and g does not divide a
630  Then denote the division with remainder of a by g as this:
631  a = s * g + t. Then t = a - s * g = a - s * (|b|/g)^(-1) * |b|
632  fulfills (1) and (2), i.e. rr := t is the correct result. Hence
633  in this third case, rr is the remainder of division of a by g in Z.
634  Remark: according to mpz_mod: a,b are always non-negative
635  */
636  mpz_ptr g = (mpz_ptr)omAllocBin(gmp_nrz_bin);
637  mpz_ptr rr = (mpz_ptr)omAllocBin(gmp_nrz_bin);
638  mpz_init(g);
639  mpz_init_set_ui(rr, 0);
640  mpz_gcd(g, (mpz_ptr)r->modNumber, (mpz_ptr)b); // g is now as above
641  if (mpz_cmp_si(g, 1L) != 0) mpz_mod(rr, (mpz_ptr)a, g); // the case g <> 1
642  mpz_clear(g);
644  return (number)rr;
645 }
646 
647 static number nrnIntDiv(number a, number b, const coeffs r)
648 {
649  mpz_ptr erg = (mpz_ptr)omAllocBin(gmp_nrz_bin);
650  mpz_init(erg);
651  mpz_tdiv_q(erg, (mpz_ptr)a, (mpz_ptr)b);
652  return (number)erg;
653 }
654 
655 /* CF: note that Z/nZ has (at least) two distinct euclidean structures
656  * 1st phi(a) := (a mod n) which is just the structure directly
657  * inherited from Z
658  * 2nd phi(a) := gcd(a, n)
659  * The 1st version is probably faster as everything just comes from Z,
660  * but the 2nd version behaves nicely wrt. to quotient operations
661  * and HNF and such. In agreement with nrnMod we imlement the 2nd here
662  *
663  * For quotrem note that if b exactly divides a, then
664  * min(v_p(a), v_p(n)) >= min(v_p(b), v_p(n))
665  * so if we divide a and b by g:= gcd(a,b,n), then b becomes a
666  * unit mod n/g.
667  * Thus we 1st compute the remainder (similar to nrnMod) and then
668  * the exact quotient.
669  */
670 static number nrnQuotRem(number a, number b, number * rem, const coeffs r)
671 {
672  mpz_t g, aa, bb;
673  mpz_ptr qq = (mpz_ptr)omAllocBin(gmp_nrz_bin);
674  mpz_ptr rr = (mpz_ptr)omAllocBin(gmp_nrz_bin);
675  mpz_init(qq);
676  mpz_init(rr);
677  mpz_init(g);
678  mpz_init_set(aa, (mpz_ptr)a);
679  mpz_init_set(bb, (mpz_ptr)b);
680 
681  mpz_gcd(g, bb, r->modNumber);
682  mpz_mod(rr, aa, g);
683  mpz_sub(aa, aa, rr);
684  mpz_gcd(g, aa, g);
685  mpz_div(aa, aa, g);
686  mpz_div(bb, bb, g);
687  mpz_div(g, r->modNumber, g);
688  mpz_invert(g, bb, g);
689  mpz_mul(qq, aa, g);
690  if (rem)
691  *rem = (number)rr;
692  else {
693  mpz_clear(rr);
694  omFreeBin(rr, gmp_nrz_bin);
695  }
696  mpz_clear(g);
697  mpz_clear(aa);
698  mpz_clear(bb);
699  return (number) qq;
700 }
701 
702 /*
703  * Helper function for computing the module
704  */
705 
706 static mpz_ptr nrnMapCoef = NULL;
707 
708 static number nrnMapModN(number from, const coeffs /*src*/, const coeffs dst)
709 {
710  return nrnMult(from, (number) nrnMapCoef, dst);
711 }
712 
713 static number nrnMap2toM(number from, const coeffs /*src*/, const coeffs dst)
714 {
715  mpz_ptr erg = (mpz_ptr)omAllocBin(gmp_nrz_bin);
716  mpz_init(erg);
717  mpz_mul_ui(erg, nrnMapCoef, (unsigned long)from);
718  mpz_mod(erg, erg, dst->modNumber);
719  return (number)erg;
720 }
721 
722 static number nrnMapZp(number from, const coeffs /*src*/, const coeffs dst)
723 {
724  mpz_ptr erg = (mpz_ptr)omAllocBin(gmp_nrz_bin);
725  mpz_init(erg);
726  // TODO: use npInt(...)
727  mpz_mul_si(erg, nrnMapCoef, (unsigned long)from);
728  mpz_mod(erg, erg, dst->modNumber);
729  return (number)erg;
730 }
731 
732 number nrnMapGMP(number from, const coeffs /*src*/, const coeffs dst)
733 {
734  mpz_ptr erg = (mpz_ptr)omAllocBin(gmp_nrz_bin);
735  mpz_init(erg);
736  mpz_mod(erg, (mpz_ptr)from, dst->modNumber);
737  return (number)erg;
738 }
739 
740 static number nrnMapQ(number from, const coeffs src, const coeffs dst)
741 {
742  mpz_ptr erg = (mpz_ptr)omAllocBin(gmp_nrz_bin);
743  mpz_init(erg);
744  nlGMP(from, erg, src); // FIXME? TODO? // extern void nlGMP(number &i, number n, const coeffs r); // to be replaced with n_MPZ(erg, from, src); // ?
745  mpz_mod(erg, erg, dst->modNumber);
746  return (number)erg;
747 }
748 
749 #if SI_INTEGER_VARIANT==3
750 static number nrnMapZ(number from, const coeffs /*src*/, const coeffs dst)
751 {
752  mpz_ptr erg = (mpz_ptr)omAllocBin(gmp_nrz_bin);
753  if (n_Z_IS_SMALL(from))
754  mpz_init_set_si(erg, SR_TO_INT(from));
755  else
756  mpz_init_set(erg, (mpz_ptr) from);
757  mpz_mod(erg, erg, dst->modNumber);
758  return (number)erg;
759 }
760 #elif SI_INTEGER_VARIANT==2
761 
762 static number nrnMapZ(number from, const coeffs src, const coeffs dst)
763 {
764  if (SR_HDL(from) & SR_INT)
765  {
766  long f_i=SR_TO_INT(from);
767  return nrnInit(f_i,dst);
768  }
769  return nrnMapGMP(from,src,dst);
770 }
771 #elif SI_INTEGER_VARIANT==1
772 static number nrnMapZ(number from, const coeffs src, const coeffs dst)
773 {
774  return nrnMapQ(from,src,dst);
775 }
776 #endif
777 void nrnWrite (number a, const coeffs cf)
778 {
779  char *s,*z;
780  if (a==NULL)
781  {
782  StringAppendS("o");
783  }
784  else
785  {
786  int l=mpz_sizeinbase((mpz_ptr) a, 10) + 2;
787  s=(char*)omAlloc(l);
788  if (cf->is_field)
789  {
790  mpz_t ch2; mpz_init_set(ch2, cf->modBase);
791  mpz_sub_ui(ch2,ch2,1);
792  mpz_divexact_ui(ch2,ch2,2);
793  if ((mpz_cmp_ui(cf->modBase,2)!=0) && (mpz_cmp(ch2,(mpz_ptr)a)<0))
794  {
795  mpz_sub(ch2,(mpz_ptr)a,cf->modBase);
796  z=mpz_get_str(s,10,ch2);
797  StringAppendS(z);
798  }
799  else
800  {
801  z=mpz_get_str(s,10,(mpz_ptr) a);
802  StringAppendS(z);
803  }
804  mpz_clear(ch2);
805  }
806  else
807  {
808  z=mpz_get_str(s,10,(mpz_ptr) a);
809  StringAppendS(z);
810  }
811  omFreeSize((ADDRESS)s,l);
812  }
813 }
814 
815 nMapFunc nrnSetMap(const coeffs src, const coeffs dst)
816 {
817  /* dst = nrn */
818  if ((src->rep==n_rep_gmp) && nCoeff_is_Z(src))
819  {
820  return nrnMapZ;
821  }
822  if ((src->rep==n_rep_gap_gmp) /*&& nCoeff_is_Z(src)*/)
823  {
824  return nrnMapZ;
825  }
826  if (src->rep==n_rep_gap_rat) /*&& nCoeff_is_Q(src)) or Z*/
827  {
828  return nrnMapQ;
829  }
830  // Some type of Z/n ring / field
831  if (nCoeff_is_Zn(src) || nCoeff_is_Ring_PtoM(src) ||
832  nCoeff_is_Ring_2toM(src) || nCoeff_is_Zp(src))
833  {
834  if ( (!nCoeff_is_Zp(src))
835  && (mpz_cmp(src->modBase, dst->modBase) == 0)
836  && (src->modExponent == dst->modExponent)) return ndCopyMap;
837  else
838  {
839  mpz_ptr nrnMapModul = (mpz_ptr) omAllocBin(gmp_nrz_bin);
840  // Computing the n of Z/n
841  if (nCoeff_is_Zp(src))
842  {
843  mpz_init_set_si(nrnMapModul, src->ch);
844  }
845  else
846  {
847  mpz_init(nrnMapModul);
848  mpz_set(nrnMapModul, src->modNumber);
849  }
850  // nrnMapCoef = 1 in dst if dst is a subring of src
851  // nrnMapCoef = 0 in dst / src if src is a subring of dst
852  if (nrnMapCoef == NULL)
853  {
854  nrnMapCoef = (mpz_ptr) omAllocBin(gmp_nrz_bin);
855  mpz_init(nrnMapCoef);
856  }
857  if (mpz_divisible_p(nrnMapModul, dst->modNumber))
858  {
859  mpz_set_ui(nrnMapCoef, 1);
860  }
861  else
862  if (mpz_divisible_p(dst->modNumber,nrnMapModul))
863  {
864  mpz_divexact(nrnMapCoef, dst->modNumber, nrnMapModul);
865  mpz_ptr tmp = dst->modNumber;
866  dst->modNumber = nrnMapModul;
867  if (!nrnIsUnit((number) nrnMapCoef,dst))
868  {
869  dst->modNumber = tmp;
870  nrnDelete((number*) &nrnMapModul, dst);
871  return NULL;
872  }
873  mpz_ptr inv = (mpz_ptr) nrnInvers((number) nrnMapCoef,dst);
874  dst->modNumber = tmp;
875  mpz_mul(nrnMapCoef, nrnMapCoef, inv);
876  mpz_mod(nrnMapCoef, nrnMapCoef, dst->modNumber);
877  nrnDelete((number*) &inv, dst);
878  }
879  else
880  {
881  nrnDelete((number*) &nrnMapModul, dst);
882  return NULL;
883  }
884  nrnDelete((number*) &nrnMapModul, dst);
885  if (nCoeff_is_Ring_2toM(src))
886  return nrnMap2toM;
887  else if (nCoeff_is_Zp(src))
888  return nrnMapZp;
889  else
890  return nrnMapModN;
891  }
892  }
893  return NULL; // default
894 }
895 
896 /*
897  * set the exponent (allocate and init tables) (TODO)
898  */
899 
900 static void nrnSetExp(unsigned long m, coeffs r)
901 {
902  /* clean up former stuff */
903  if (r->modNumber != NULL) mpz_clear(r->modNumber);
904 
905  r->modExponent= m;
906  r->modNumber = (mpz_ptr)omAllocBin(gmp_nrz_bin);
907  mpz_init_set (r->modNumber, r->modBase);
908  mpz_pow_ui (r->modNumber, r->modNumber, m);
909 }
910 
911 /* We expect this ring to be Z/n^m for some m > 0 and for some n > 2 which is not a prime. */
912 static void nrnInitExp(unsigned long m, coeffs r)
913 {
914  nrnSetExp(m, r);
915  assume (r->modNumber != NULL);
916 //CF: in general, the modulus is computed somewhere. I don't want to
917 // check it's size before I construct the best ring.
918 // if (mpz_cmp_ui(r->modNumber,2) <= 0)
919 // WarnS("nrnInitExp failed (m in Z/m too small)");
920 }
921 
922 #ifdef LDEBUG
923 BOOLEAN nrnDBTest (number a, const char *f, const int l, const coeffs r)
924 {
925  if ( (mpz_sgn1((mpz_ptr) a) < 0) || (mpz_cmp((mpz_ptr) a, r->modNumber) > 0) )
926  {
927  Warn("mod-n: out of range at %s:%d\n",f,l);
928  return FALSE;
929  }
930  return TRUE;
931 }
932 #endif
933 
934 /*2
935 * extracts a long integer from s, returns the rest (COPY FROM longrat0.cc)
936 */
937 static const char * nlCPEatLongC(char *s, mpz_ptr i)
938 {
939  const char * start=s;
940  if (!(*s >= '0' && *s <= '9'))
941  {
942  mpz_init_set_ui(i, 1);
943  return s;
944  }
945  mpz_init(i);
946  while (*s >= '0' && *s <= '9') s++;
947  if (*s=='\0')
948  {
949  mpz_set_str(i,start,10);
950  }
951  else
952  {
953  char c=*s;
954  *s='\0';
955  mpz_set_str(i,start,10);
956  *s=c;
957  }
958  return s;
959 }
960 
961 static const char * nrnRead (const char *s, number *a, const coeffs r)
962 {
963  mpz_ptr z = (mpz_ptr) omAllocBin(gmp_nrz_bin);
964  {
965  s = nlCPEatLongC((char *)s, z);
966  }
967  mpz_mod(z, z, r->modNumber);
968  if ((*s)=='/')
969  {
970  mpz_ptr n = (mpz_ptr) omAllocBin(gmp_nrz_bin);
971  s++;
972  s=nlCPEatLongC((char*)s,n);
973  if (!nrnIsOne((number)n,r))
974  {
975  *a=nrnDiv((number)z,(number)n,r);
976  mpz_clear(z);
977  omFreeBin((void *)z, gmp_nrz_bin);
978  mpz_clear(n);
979  omFreeBin((void *)n, gmp_nrz_bin);
980  }
981  }
982  else
983  *a = (number) z;
984  return s;
985 }
986 
987 static number nrnConvFactoryNSingN( const CanonicalForm n, const coeffs r)
988 {
989  return nrnInit(n.intval(),r);
990 }
991 
992 static CanonicalForm nrnConvSingNFactoryN( number n, BOOLEAN setChar, const coeffs r )
993 {
994  if (setChar) setCharacteristic( r->ch );
995  return CanonicalForm(nrnInt( n,r ));
996 }
997 
998 /* for initializing function pointers */
1000 {
1001  assume( (getCoeffType(r) == n_Zn) || (getCoeffType (r) == n_Znm) );
1002  ZnmInfo * info= (ZnmInfo *) p;
1003  r->modBase= (mpz_ptr)nrnCopy((number)info->base, r); //this circumvents the problem
1004  //in bigintmat.cc where we cannot create a "legal" nrn that can be freed.
1005  //If we take a copy, we can do whatever we want.
1006 
1007  nrnInitExp (info->exp, r);
1008 
1009  /* next computation may yield wrong characteristic as r->modNumber
1010  is a GMP number */
1011  r->ch = mpz_get_ui(r->modNumber);
1012 
1013  r->is_field=FALSE;
1014  r->is_domain=FALSE;
1015  r->rep=n_rep_gmp;
1016 
1017 
1018  r->cfCoeffString = nrnCoeffString;
1019 
1020  r->cfInit = nrnInit;
1021  r->cfDelete = nrnDelete;
1022  r->cfCopy = nrnCopy;
1023  r->cfSize = nrnSize;
1024  r->cfInt = nrnInt;
1025  r->cfAdd = nrnAdd;
1026  r->cfSub = nrnSub;
1027  r->cfMult = nrnMult;
1028  r->cfDiv = nrnDiv;
1029  r->cfAnn = nrnAnn;
1030  r->cfIntMod = nrnMod;
1031  r->cfExactDiv = nrnDiv;
1032  r->cfInpNeg = nrnNeg;
1033  r->cfInvers = nrnInvers;
1034  r->cfDivBy = nrnDivBy;
1035  r->cfDivComp = nrnDivComp;
1036  r->cfGreater = nrnGreater;
1037  r->cfEqual = nrnEqual;
1038  r->cfIsZero = nrnIsZero;
1039  r->cfIsOne = nrnIsOne;
1040  r->cfIsMOne = nrnIsMOne;
1041  r->cfGreaterZero = nrnGreaterZero;
1042  r->cfWriteLong = nrnWrite;
1043  r->cfRead = nrnRead;
1044  r->cfPower = nrnPower;
1045  r->cfSetMap = nrnSetMap;
1046  //r->cfNormalize = ndNormalize;
1047  r->cfLcm = nrnLcm;
1048  r->cfGcd = nrnGcd;
1049  r->cfIsUnit = nrnIsUnit;
1050  r->cfGetUnit = nrnGetUnit;
1051  r->cfExtGcd = nrnExtGcd;
1052  r->cfXExtGcd = nrnXExtGcd;
1053  r->cfQuotRem = nrnQuotRem;
1054  r->cfCoeffName = nrnCoeffName;
1055  r->cfCoeffWrite = nrnCoeffWrite;
1056  r->nCoeffIsEqual = nrnCoeffIsEqual;
1057  r->cfKillChar = nrnKillChar;
1058  r->cfQuot1 = nrnQuot1;
1059 #if SI_INTEGER_VARIANT==2
1060  r->cfWriteFd = nrzWriteFd;
1061  r->cfReadFd = nrzReadFd;
1062 #endif
1063 
1064 #ifdef LDEBUG
1065  r->cfDBTest = nrnDBTest;
1066 #endif
1067  if ((r->modExponent==1)&&(mpz_size1(r->modBase)==1))
1068  {
1069  long p=mpz_get_si(r->modBase);
1070  if ((p<=FACTORY_MAX_PRIME)&&(p==IsPrime(p))) /*factory limit: <2^29*/
1071  {
1072  r->convFactoryNSingN=nrnConvFactoryNSingN;
1073  r->convSingNFactoryN=nrnConvSingNFactoryN;
1074  }
1075  }
1076  return FALSE;
1077 }
1078 
1079 #endif
1080 /* #ifdef HAVE_RINGS */
All the auxiliary stuff.
int BOOLEAN
Definition: auxiliary.h:85
#define TRUE
Definition: auxiliary.h:98
#define FALSE
Definition: auxiliary.h:94
void * ADDRESS
Definition: auxiliary.h:133
void setCharacteristic(int c)
Definition: cf_char.cc:23
int l
Definition: cfEzgcd.cc:93
int m
Definition: cfEzgcd.cc:121
int i
Definition: cfEzgcd.cc:125
int k
Definition: cfEzgcd.cc:92
int p
Definition: cfModGcd.cc:4019
g
Definition: cfModGcd.cc:4031
CanonicalForm cf
Definition: cfModGcd.cc:4024
CanonicalForm b
Definition: cfModGcd.cc:4044
FILE * f
Definition: checklibs.c:9
factory's main class
Definition: canonicalform.h:83
long intval() const
conversion functions
Coefficient rings, fields and other domains suitable for Singular polynomials.
static FORCE_INLINE BOOLEAN nCoeff_is_Z(const coeffs r)
Definition: coeffs.h:838
static FORCE_INLINE BOOLEAN nCoeff_is_Ring_PtoM(const coeffs r)
Definition: coeffs.h:749
n_coeffType
Definition: coeffs.h:28
@ n_Znm
only used if HAVE_RINGS is defined
Definition: coeffs.h:46
@ n_Zn
only used if HAVE_RINGS is defined
Definition: coeffs.h:45
coeffs nInitChar(n_coeffType t, void *parameter)
one-time initialisations for new coeffs in case of an error return NULL
Definition: numbers.cc:350
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_Zn(const coeffs r)
Definition: coeffs.h:848
static FORCE_INLINE void n_Write(number n, const coeffs r, const BOOLEAN bShortOut=TRUE)
Definition: coeffs.h:591
static FORCE_INLINE BOOLEAN nCoeff_is_Zp(const coeffs r)
Definition: coeffs.h:822
static FORCE_INLINE BOOLEAN nCoeff_is_Ring_2toM(const coeffs r)
Definition: coeffs.h:746
@ n_rep_gap_rat
(number), see longrat.h
Definition: coeffs.h:111
@ n_rep_gap_gmp
(), see rinteger.h, new impl.
Definition: coeffs.h:112
@ n_rep_gmp
(mpz_ptr), see rmodulon,h
Definition: coeffs.h:115
number(* nMapFunc)(number a, const coeffs src, const coeffs dst)
maps "a", which lives in src, into dst
Definition: coeffs.h:73
#define Print
Definition: emacs.cc:80
#define Warn
Definition: emacs.cc:77
return result
Definition: facAbsBiFact.cc:76
const CanonicalForm int s
Definition: facAbsFact.cc:55
CanonicalForm res
Definition: facAbsFact.cc:64
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
const ExtensionInfo & info
< [in] sqrfree poly
void WerrorS(const char *s)
Definition: feFopen.cc:24
void mpz_mul_si(mpz_ptr r, mpz_srcptr s, long int si)
Definition: longrat.cc:172
void nlGMP(number &i, mpz_t n, const coeffs r)
Definition: longrat.cc:1478
#define SR_INT
Definition: longrat.h:66
#define SR_TO_INT(SR)
Definition: longrat.h:68
void rem(unsigned long *a, unsigned long *q, unsigned long p, int &dega, int degq)
Definition: minpoly.cc:572
#define assume(x)
Definition: mod2.h:390
#define FACTORY_MAX_PRIME
Definition: modulop.h:30
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:252
char * nEatLong(char *s, mpz_ptr i)
extracts a long integer from s, returns the rest
Definition: numbers.cc:652
char * nEati(char *s, int *i, int m)
divide by the first (leading) number and return it, i.e. make monic
Definition: numbers.cc:631
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define omAllocBin(bin)
Definition: omAllocDecl.h:205
#define omFree(addr)
Definition: omAllocDecl.h:261
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:259
#define NULL
Definition: omList.c:10
omBin_t * omBin
Definition: omStructs.h: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
number nrzReadFd(const ssiInfo *d, const coeffs)
Definition: rintegers.cc:586
void nrzWriteFd(number n, const ssiInfo *d, const coeffs)
Definition: rintegers.cc:580
static const char * nrnRead(const char *s, number *a, const coeffs r)
Definition: rmodulon.cc:961
static number nrnMap2toM(number from, const coeffs, const coeffs dst)
Definition: rmodulon.cc:713
static coeffs nrnQuot1(number c, const coeffs r)
Definition: rmodulon.cc:133
omBin gmp_nrz_bin
Definition: rintegers.cc:31
static char * nrnCoeffName_buff
Definition: rmodulon.cc:86
static const char * nlCPEatLongC(char *s, mpz_ptr i)
Definition: rmodulon.cc:937
static number nrnInit(long i, const coeffs r)
Definition: rmodulon.cc:188
static void nrnKillChar(coeffs r)
Definition: rmodulon.cc:125
BOOLEAN nrnDBTest(number a, const char *f, const int l, const coeffs r)
Definition: rmodulon.cc:923
#define nrnSize
Definition: rmodulon.cc:206
static BOOLEAN nrnGreater(number a, number b, const coeffs)
Definition: rmodulon.cc:514
static mpz_ptr nrnMapCoef
Definition: rmodulon.cc:706
static BOOLEAN nrnIsZero(number a, const coeffs)
Definition: rmodulon.cc:263
static CanonicalForm nrnConvSingNFactoryN(number n, BOOLEAN setChar, const coeffs r)
Definition: rmodulon.cc:992
static number nrnExtGcd(number a, number b, number *s, number *t, const coeffs r)
Definition: rmodulon.cc:341
static BOOLEAN nrnCoeffIsEqual(const coeffs r, n_coeffType n, void *parameter)
Definition: rmodulon.cc:105
void nrnWrite(number a, const coeffs)
Definition: rmodulon.cc:777
static number nrnMod(number a, number b, const coeffs r)
Definition: rmodulon.cc:615
static number nrnMapZ(number from, const coeffs src, const coeffs dst)
Definition: rmodulon.cc:762
static void nrnInitExp(unsigned long m, coeffs r)
Definition: rmodulon.cc:912
static number nrnAnn(number k, const coeffs r)
Definition: rmodulon.cc:545
static char * nrnCoeffName(const coeffs r)
Definition: rmodulon.cc:87
static BOOLEAN nrnIsUnit(number a, const coeffs r)
Definition: rmodulon.cc:537
static void nrnCoeffWrite(const coeffs r, BOOLEAN)
Definition: rmodulon.cc:36
coeffs nrnInitCfByName(char *s, n_coeffType n)
Definition: rmodulon.cc:58
#define nrnDelete
Definition: rmodulon.cc:205
nMapFunc nrnSetMap(const coeffs src, const coeffs dst)
Definition: rmodulon.cc:815
static number nrnMapZp(number from, const coeffs, const coeffs dst)
Definition: rmodulon.cc:722
static number nrnInvers(number c, const coeffs r)
Definition: rmodulon.cc:276
static number nrnConvFactoryNSingN(const CanonicalForm n, const coeffs r)
Definition: rmodulon.cc:987
static void nrnSetExp(unsigned long m, coeffs r)
Definition: rmodulon.cc:900
static int nrnDivComp(number a, number b, const coeffs r)
Definition: rmodulon.cc:569
static number nrnIntDiv(number a, number b, const coeffs r)
Definition: rmodulon.cc:647
static number nrnXExtGcd(number a, number b, number *s, number *t, number *u, number *v, const coeffs r)
Definition: rmodulon.cc:413
static BOOLEAN nrnEqual(number a, number b, const coeffs)
Definition: rmodulon.cc:362
static number nrnQuotRem(number a, number b, number *rem, const coeffs r)
Definition: rmodulon.cc:670
static long nrnInt(number &n, const coeffs)
Definition: rmodulon.cc:199
static number nrnMapQ(number from, const coeffs src, const coeffs dst)
Definition: rmodulon.cc:740
static BOOLEAN nrnIsOne(number a, const coeffs)
Definition: rmodulon.cc:357
static number nrnCopy(number a, const coeffs)
Definition: rmodulon.cc:178
static number nrnSub(number a, number b, const coeffs r)
Definition: rmodulon.cc:254
static number nrnLcm(number a, number b, const coeffs r)
Definition: rmodulon.cc:308
static number nrnMapModN(number from, const coeffs, const coeffs dst)
Definition: rmodulon.cc:708
static void nrnPower(number a, int i, number *result, const coeffs r)
Definition: rmodulon.cc:237
static number nrnMult(number a, number b, const coeffs r)
Definition: rmodulon.cc:228
static number nrnNeg(number c, const coeffs r)
Definition: rmodulon.cc:268
static char * nrnCoeffString(const coeffs r)
Definition: rmodulon.cc:113
static number nrnGetUnit(number k, const coeffs r)
Definition: rmodulon.cc:367
number nrnMapGMP(number from, const coeffs, const coeffs dst)
Definition: rmodulon.cc:732
static number nrnDiv(number a, number b, const coeffs r)
Definition: rmodulon.cc:577
static BOOLEAN nrnIsMOne(number a, const coeffs r)
Definition: rmodulon.cc:504
static BOOLEAN nrnDivBy(number a, number b, const coeffs r)
Definition: rmodulon.cc:559
static BOOLEAN nrnGreaterZero(number k, const coeffs cf)
Definition: rmodulon.cc:519
BOOLEAN nrnInitChar(coeffs r, void *p)
Definition: rmodulon.cc:999
static number nrnAdd(number a, number b, const coeffs r)
Definition: rmodulon.cc:245
static number nrnGcd(number a, number b, const coeffs r)
Definition: rmodulon.cc:289
#define mpz_size1(A)
Definition: si_gmp.h:12
#define mpz_sgn1(A)
Definition: si_gmp.h:13
#define SR_HDL(A)
Definition: tgb.cc:35
int gcd(int a, int b)
Definition: walkSupport.cc:836