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