source: git/libpolys/polys/ext_fields/algext.cc @ dc42daf

jengelh-datetimespielwiese
Last change on this file since dc42daf was dc42daf, checked in by Claus Fieker <fieker@…>, 10 years ago
an attempt to introduce better normalization for polynomials over number fields. Seems to work well in selected examples...
  • Property mode set to 100644
File size: 39.0 KB
Line 
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/**
5  * ABSTRACT: numbers in an algebraic extension field K[a] / < f(a) >
6  *           Assuming that we have a coeffs object cf, then these numbers
7  *           are polynomials in the polynomial ring K[a] represented by
8  *           cf->extRing.
9  *           IMPORTANT ASSUMPTIONS:
10  *           1.) So far we assume that cf->extRing is a valid polynomial
11  *               ring in exactly one variable, i.e., K[a], where K is allowed
12  *               to be any field (representable in SINGULAR and which may
13  *               itself be some extension field, thus allowing for extension
14  *               towers).
15  *           2.) Moreover, this implementation assumes that
16  *               cf->extRing->qideal is not NULL but an ideal with at
17  *               least one non-zero generator which may be accessed by
18  *               cf->extRing->qideal->m[0] and which represents the minimal
19  *               polynomial f(a) of the extension variable 'a' in K[a].
20  *           3.) As soon as an std method for polynomial rings becomes
21  *               availabe, all reduction steps modulo f(a) should be replaced
22  *               by a call to std. Moreover, in this situation one can finally
23  *               move from K[a] / < f(a) > to
24  *                  K[a_1, ..., a_s] / I, with I some zero-dimensional ideal
25  *                                        in K[a_1, ..., a_s] given by a lex
26  *                                        Gröbner basis.
27  *               The code in algext.h and algext.cc is then capable of
28  *               computing in K[a_1, ..., a_s] / I.
29  **/
30
31#include "config.h"
32#include <misc/auxiliary.h>
33
34#include <omalloc/omalloc.h>
35
36#include <reporter/reporter.h>
37
38#include <coeffs/coeffs.h>
39#include <coeffs/numbers.h>
40#include <coeffs/longrat.h>
41
42#include <polys/monomials/ring.h>
43#include <polys/monomials/p_polys.h>
44#include <polys/simpleideals.h>
45
46#include <polys/PolyEnumerator.h>
47
48#ifdef HAVE_FACTORY
49#include <factory/factory.h>
50#include <polys/clapconv.h>
51#include <polys/clapsing.h>
52#endif
53
54
55#include <polys/ext_fields/algext.h>
56#define TRANSEXT_PRIVATES 1
57#include <polys/ext_fields/transext.h>
58
59#ifdef LDEBUG
60#define naTest(a) naDBTest(a,__FILE__,__LINE__,cf)
61BOOLEAN  naDBTest(number a, const char *f, const int l, const coeffs r);
62#else
63#define naTest(a) do {} while (0)
64#endif
65
66/// Our own type!
67static const n_coeffType ID = n_algExt;
68
69/* polynomial ring in which our numbers live */
70#define naRing cf->extRing
71
72/* coeffs object in which the coefficients of our numbers live;
73 * methods attached to naCoeffs may be used to compute with the
74 * coefficients of our numbers, e.g., use naCoeffs->nAdd to add
75 * coefficients of our numbers */
76#define naCoeffs cf->extRing->cf
77
78/* minimal polynomial */
79#define naMinpoly naRing->qideal->m[0]
80
81/// forward declarations
82BOOLEAN  naGreaterZero(number a, const coeffs cf);
83BOOLEAN  naGreater(number a, number b, const coeffs cf);
84BOOLEAN  naEqual(number a, number b, const coeffs cf);
85BOOLEAN  naIsOne(number a, const coeffs cf);
86BOOLEAN  naIsMOne(number a, const coeffs cf);
87BOOLEAN  naIsZero(number a, const coeffs cf);
88number   naInit(long i, const coeffs cf);
89int      naInt(number &a, const coeffs cf);
90number   naNeg(number a, const coeffs cf);
91number   naInvers(number a, const coeffs cf);
92number   naAdd(number a, number b, const coeffs cf);
93number   naSub(number a, number b, const coeffs cf);
94number   naMult(number a, number b, const coeffs cf);
95number   naDiv(number a, number b, const coeffs cf);
96void     naPower(number a, int exp, number *b, const coeffs cf);
97number   naCopy(number a, const coeffs cf);
98void     naWriteLong(number &a, const coeffs cf);
99void     naWriteShort(number &a, const coeffs cf);
100number   naRePart(number a, const coeffs cf);
101number   naImPart(number a, const coeffs cf);
102number   naGetDenom(number &a, const coeffs cf);
103number   naGetNumerator(number &a, const coeffs cf);
104number   naGcd(number a, number b, const coeffs cf);
105//number   naLcm(number a, number b, const coeffs cf);
106int      naSize(number a, const coeffs cf);
107void     naDelete(number *a, const coeffs cf);
108void     naCoeffWrite(const coeffs cf, BOOLEAN details);
109//number   naIntDiv(number a, number b, const coeffs cf);
110const char * naRead(const char *s, number *a, const coeffs cf);
111
112static BOOLEAN naCoeffIsEqual(const coeffs cf, n_coeffType n, void * param);
113
114
115/// returns NULL if p == NULL, otherwise makes p monic by dividing
116///   by its leading coefficient (only done if this is not already 1);
117///   this assumes that we are over a ground field so that division
118///   is well-defined;
119///   modifies p
120// void      p_Monic(poly p, const ring r);
121
122///   assumes that p and q are univariate polynomials in r,
123///   mentioning the same variable;
124///   assumes a global monomial ordering in r;
125///   assumes that not both p and q are NULL;
126///   returns the gcd of p and q;
127///   leaves p and q unmodified
128// poly      p_Gcd(const poly p, const poly q, const ring r);
129
130/* returns NULL if p == NULL, otherwise makes p monic by dividing
131   by its leading coefficient (only done if this is not already 1);
132   this assumes that we are over a ground field so that division
133   is well-defined;
134   modifies p */
135static inline void p_Monic(poly p, const ring r)
136{
137  if (p == NULL) return;
138  number n = n_Init(1, r->cf);
139  if (p->next==NULL) { p_SetCoeff(p,n,r); return; }
140  poly pp = p;
141  number lc = p_GetCoeff(p, r);
142  if (n_IsOne(lc, r->cf)) return;
143  number lcInverse = n_Invers(lc, r->cf);
144  p_SetCoeff(p, n, r);   // destroys old leading coefficient!
145  pIter(p);
146  while (p != NULL)
147  {
148    number n = n_Mult(p_GetCoeff(p, r), lcInverse, r->cf);
149    n_Normalize(n,r->cf);
150    p_SetCoeff(p, n, r);   // destroys old leading coefficient!
151    pIter(p);
152  }
153  n_Delete(&lcInverse, r->cf);
154  p = pp;
155}
156
157/// see p_Gcd;
158///   additional assumption: deg(p) >= deg(q);
159///   must destroy p and q (unless one of them is returned)
160static inline poly p_GcdHelper(poly &p, poly &q, const ring r)
161{
162  while (q != NULL)
163  {
164    p_PolyDiv(p, q, FALSE, r);
165    // swap p and q:
166    poly& t = q;
167    q = p;
168    p = t;
169
170  }
171  return p;
172}
173
174/* assumes that p and q are univariate polynomials in r,
175   mentioning the same variable;
176   assumes a global monomial ordering in r;
177   assumes that not both p and q are NULL;
178   returns the gcd of p and q;
179   leaves p and q unmodified */
180static inline poly      p_Gcd(const poly p, const poly q, const ring r)
181{
182  assume((p != NULL) || (q != NULL));
183
184  poly a = p; poly b = q;
185  if (p_Deg(a, r) < p_Deg(b, r)) { a = q; b = p; }
186  a = p_Copy(a, r); b = p_Copy(b, r);
187
188  /* We have to make p monic before we return it, so that if the
189     gcd is a unit in the ground field, we will actually return 1. */
190  a = p_GcdHelper(a, b, r);
191  p_Monic(a, r);
192  return a;
193}
194
195/* see p_ExtGcd;
196   additional assumption: deg(p) >= deg(q);
197   must destroy p and q (unless one of them is returned) */
198static inline poly p_ExtGcdHelper(poly &p, poly &pFactor, poly &q, poly &qFactor,
199                                  ring r)
200{
201  if (q == NULL)
202  {
203    qFactor = NULL;
204    pFactor = p_ISet(1, r);
205    p_SetCoeff(pFactor, n_Invers(p_GetCoeff(p, r), r->cf), r);
206    p_Monic(p, r);
207    return p;
208  }
209  else
210  {
211    poly pDivQ = p_PolyDiv(p, q, TRUE, r);
212    poly ppFactor = NULL; poly qqFactor = NULL;
213    poly theGcd = p_ExtGcdHelper(q, qqFactor, p, ppFactor, r);
214    pFactor = ppFactor;
215    qFactor = p_Add_q(qqFactor,
216                      p_Neg(p_Mult_q(pDivQ, p_Copy(ppFactor, r), r), r),
217                      r);
218    return theGcd;
219  }
220}
221
222
223/* assumes that p and q are univariate polynomials in r,
224   mentioning the same variable;
225   assumes a global monomial ordering in r;
226   assumes that not both p and q are NULL;
227   returns the gcd of p and q;
228   moreover, afterwards pFactor and qFactor contain appropriate
229   factors such that gcd(p, q) = p * pFactor + q * qFactor;
230   leaves p and q unmodified */
231poly p_ExtGcd(poly p, poly &pFactor, poly q, poly &qFactor, ring r)
232{
233  assume((p != NULL) || (q != NULL));
234  poly a = p; poly b = q; BOOLEAN aCorrespondsToP = TRUE;
235  if (p_Deg(a, r) < p_Deg(b, r))
236    { a = q; b = p; aCorrespondsToP = FALSE; }
237  a = p_Copy(a, r); b = p_Copy(b, r);
238  poly aFactor = NULL; poly bFactor = NULL;
239  poly theGcd = p_ExtGcdHelper(a, aFactor, b, bFactor, r);
240  if (aCorrespondsToP) { pFactor = aFactor; qFactor = bFactor; }
241  else                 { pFactor = bFactor; qFactor = aFactor; }
242  return theGcd;
243}
244
245
246
247#ifdef LDEBUG
248BOOLEAN naDBTest(number a, const char *f, const int l, const coeffs cf)
249{
250  assume(getCoeffType(cf) == ID);
251  if (a == NULL) return TRUE;
252  p_Test((poly)a, naRing);
253  if((((poly)a)!=naMinpoly)
254  && p_Totaldegree((poly)a, naRing) >= p_Totaldegree(naMinpoly, naRing))
255  {
256    Print("deg >= deg(minpoly) in %s:%d\n",f,l);
257    return FALSE;
258  }
259  return TRUE;
260}
261#endif
262
263void heuristicReduce(poly &p, poly reducer, const coeffs cf);
264void definiteReduce(poly &p, poly reducer, const coeffs cf);
265
266/* returns the bottom field in this field extension tower; if the tower
267   is flat, i.e., if there is no extension, then r itself is returned;
268   as a side-effect, the counter 'height' is filled with the height of
269   the extension tower (in case the tower is flat, 'height' is zero) */
270static coeffs nCoeff_bottom(const coeffs r, int &height)
271{
272  assume(r != NULL);
273  coeffs cf = r;
274  height = 0;
275  while (nCoeff_is_Extension(cf))
276  {
277    assume(cf->extRing != NULL); assume(cf->extRing->cf != NULL);
278    cf = cf->extRing->cf;
279    height++;
280  }
281  return cf;
282}
283
284BOOLEAN naIsZero(number a, const coeffs cf)
285{
286  naTest(a);
287  return (a == NULL);
288}
289
290void naDelete(number * a, const coeffs cf)
291{
292  if (*a == NULL) return;
293  if (((poly)*a)==naMinpoly) { *a=NULL;return;}
294  poly aAsPoly = (poly)(*a);
295  p_Delete(&aAsPoly, naRing);
296  *a = NULL;
297}
298
299BOOLEAN naEqual(number a, number b, const coeffs cf)
300{
301  naTest(a); naTest(b);
302  /// simple tests
303  if (a == NULL) return (b == NULL);
304  if (b == NULL) return (a == NULL);
305  return p_EqualPolys((poly)a,(poly)b,naRing);
306}
307
308number naCopy(number a, const coeffs cf)
309{
310  naTest(a);
311  if (a == NULL) return NULL;
312  if (((poly)a)==naMinpoly) return a;
313  return (number)p_Copy((poly)a, naRing);
314}
315
316number naGetNumerator(number &a, const coeffs cf)
317{
318  return naCopy(a, cf);
319}
320
321number naGetDenom(number &a, const coeffs cf)
322{
323  naTest(a);
324  return naInit(1, cf);
325}
326
327BOOLEAN naIsOne(number a, const coeffs cf)
328{
329  naTest(a);
330  poly aAsPoly = (poly)a;
331  if ((a==NULL) || (!p_IsConstant(aAsPoly, naRing))) return FALSE;
332  return n_IsOne(p_GetCoeff(aAsPoly, naRing), naCoeffs);
333}
334
335BOOLEAN naIsMOne(number a, const coeffs cf)
336{
337  naTest(a);
338  poly aAsPoly = (poly)a;
339  if ((a==NULL) || (!p_IsConstant(aAsPoly, naRing))) return FALSE;
340  return n_IsMOne(p_GetCoeff(aAsPoly, naRing), naCoeffs);
341}
342
343/// this is in-place, modifies a
344number naNeg(number a, const coeffs cf)
345{
346  naTest(a);
347  if (a != NULL) a = (number)p_Neg((poly)a, naRing);
348  return a;
349}
350
351number naImPart(number a, const coeffs cf)
352{
353  naTest(a);
354  return NULL;
355}
356
357number naInit_bigint(number longratBigIntNumber, const coeffs src, const coeffs cf)
358{
359  assume( cf != NULL );
360
361  const ring A = cf->extRing;
362
363  assume( A != NULL );
364
365  const coeffs C = A->cf;
366
367  assume( C != NULL );
368
369  number n = n_Init_bigint(longratBigIntNumber, src, C);
370
371  if ( n_IsZero(n, C) )
372  {
373    n_Delete(&n, C);
374    return NULL;
375  }
376
377  return (number)p_NSet(n, A);
378}
379
380
381
382number naInit(long i, const coeffs cf)
383{
384  if (i == 0) return NULL;
385  else        return (number)p_ISet(i, naRing);
386}
387
388int naInt(number &a, const coeffs cf)
389{
390  naTest(a);
391  poly aAsPoly = (poly)a;
392  if(aAsPoly == NULL)
393    return 0;
394  if (!p_IsConstant(aAsPoly, naRing))
395    return 0;
396  assume( aAsPoly != NULL );
397  return n_Int(p_GetCoeff(aAsPoly, naRing), naCoeffs);
398}
399
400/* TRUE iff (a != 0 and (b == 0 or deg(a) > deg(b) or (deg(a)==deg(b) && lc(a)>lc(b))) */
401BOOLEAN naGreater(number a, number b, const coeffs cf)
402{
403  naTest(a); naTest(b);
404  if (naIsZero(a, cf))
405  {
406    if (naIsZero(b, cf)) return FALSE;
407    return !n_GreaterZero(pGetCoeff((poly)b),cf);
408  }
409  if (naIsZero(b, cf))
410  {
411    return n_GreaterZero(pGetCoeff((poly)a),cf);
412  }
413  int aDeg = p_Totaldegree((poly)a, naRing);
414  int bDeg = p_Totaldegree((poly)b, naRing);
415  if (aDeg>bDeg) return TRUE;
416  if (aDeg<bDeg) return FALSE;
417  return n_Greater(pGetCoeff((poly)a),pGetCoeff((poly)b),naCoeffs);
418}
419
420/* TRUE iff a != 0 and (LC(a) > 0 or deg(a) > 0) */
421BOOLEAN naGreaterZero(number a, const coeffs cf)
422{
423  naTest(a);
424  if (a == NULL)                                            return FALSE;
425  if (n_GreaterZero(p_GetCoeff((poly)a, naRing), naCoeffs)) return TRUE;
426  if (p_Totaldegree((poly)a, naRing) > 0)                   return TRUE;
427  return FALSE;
428}
429
430void naCoeffWrite(const coeffs cf, BOOLEAN details)
431{
432  assume( cf != NULL );
433
434  const ring A = cf->extRing;
435
436  assume( A != NULL );
437  assume( A->cf != NULL );
438
439  n_CoeffWrite(A->cf, details);
440
441//  rWrite(A);
442
443  const int P = rVar(A);
444  assume( P > 0 );
445
446  Print("//   %d parameter    : ", P);
447
448  for (int nop=0; nop < P; nop ++)
449    Print("%s ", rRingVar(nop, A));
450
451  PrintLn();
452
453  const ideal I = A->qideal;
454
455  assume( I != NULL );
456  assume( IDELEMS(I) == 1 );
457
458
459  if ( details )
460  {
461    PrintS("//   minpoly        : (");
462    p_Write0( I->m[0], A);
463    PrintS(")");
464  }
465  else
466    PrintS("//   minpoly        : ...");
467
468  PrintLn();
469
470/*
471  char *x = rRingVar(0, A);
472
473  Print("//   Coefficients live in the extension field K[%s]/<f(%s)>\n", x, x);
474  Print("//   with the minimal polynomial f(%s) = %s\n", x,
475        p_String(A->qideal->m[0], A));
476  PrintS("//   and K: ");
477*/
478}
479
480number naAdd(number a, number b, const coeffs cf)
481{
482  naTest(a); naTest(b);
483  if (a == NULL) return naCopy(b, cf);
484  if (b == NULL) return naCopy(a, cf);
485  poly aPlusB = p_Add_q(p_Copy((poly)a, naRing),
486                        p_Copy((poly)b, naRing), naRing);
487  definiteReduce(aPlusB, naMinpoly, cf);
488  return (number)aPlusB;
489}
490
491number naSub(number a, number b, const coeffs cf)
492{
493  naTest(a); naTest(b);
494  if (b == NULL) return naCopy(a, cf);
495  poly minusB = p_Neg(p_Copy((poly)b, naRing), naRing);
496  if (a == NULL) return (number)minusB;
497  poly aMinusB = p_Add_q(p_Copy((poly)a, naRing), minusB, naRing);
498  definiteReduce(aMinusB, naMinpoly, cf);
499  return (number)aMinusB;
500}
501
502number naMult(number a, number b, const coeffs cf)
503{
504  naTest(a); naTest(b);
505  if ((a == NULL)||(b == NULL)) return NULL;
506  poly aTimesB = p_Mult_q(p_Copy((poly)a, naRing),
507                          p_Copy((poly)b, naRing), naRing);
508  definiteReduce(aTimesB, naMinpoly, cf);
509  p_Normalize(aTimesB,naRing);
510  return (number)aTimesB;
511}
512
513number naDiv(number a, number b, const coeffs cf)
514{
515  naTest(a); naTest(b);
516  if (b == NULL) WerrorS(nDivBy0);
517  if (a == NULL) return NULL;
518  poly bInverse = (poly)naInvers(b, cf);
519  if(bInverse != NULL) // b is non-zero divisor!
520  {
521    poly aDivB = p_Mult_q(p_Copy((poly)a, naRing), bInverse, naRing);
522    definiteReduce(aDivB, naMinpoly, cf);
523    p_Normalize(aDivB,naRing);
524    return (number)aDivB;
525  }
526  return NULL;
527}
528
529/* 0^0 = 0;
530   for |exp| <= 7 compute power by a simple multiplication loop;
531   for |exp| >= 8 compute power along binary presentation of |exp|, e.g.
532      p^13 = p^1 * p^4 * p^8, where we utilise that
533      p^(2^(k+1)) = p^(2^k) * p^(2^k);
534   intermediate reduction modulo the minimal polynomial is controlled by
535   the in-place method heuristicReduce(poly, poly, coeffs); see there.
536*/
537void naPower(number a, int exp, number *b, const coeffs cf)
538{
539  naTest(a);
540
541  /* special cases first */
542  if (a == NULL)
543  {
544    if (exp >= 0) *b = NULL;
545    else          WerrorS(nDivBy0);
546    return;
547  }
548  else if (exp ==  0) { *b = naInit(1, cf); return; }
549  else if (exp ==  1) { *b = naCopy(a, cf); return; }
550  else if (exp == -1) { *b = naInvers(a, cf); return; }
551
552  int expAbs = exp; if (expAbs < 0) expAbs = -expAbs;
553
554  /* now compute a^expAbs */
555  poly pow; poly aAsPoly = (poly)a;
556  if (expAbs <= 7)
557  {
558    pow = p_Copy(aAsPoly, naRing);
559    for (int i = 2; i <= expAbs; i++)
560    {
561      pow = p_Mult_q(pow, p_Copy(aAsPoly, naRing), naRing);
562      heuristicReduce(pow, naMinpoly, cf);
563    }
564    definiteReduce(pow, naMinpoly, cf);
565  }
566  else
567  {
568    pow = p_ISet(1, naRing);
569    poly factor = p_Copy(aAsPoly, naRing);
570    while (expAbs != 0)
571    {
572      if (expAbs & 1)
573      {
574        pow = p_Mult_q(pow, p_Copy(factor, naRing), naRing);
575        heuristicReduce(pow, naMinpoly, cf);
576      }
577      expAbs = expAbs / 2;
578      if (expAbs != 0)
579      {
580        factor = p_Mult_q(factor, p_Copy(factor, naRing), naRing);
581        heuristicReduce(factor, naMinpoly, cf);
582      }
583    }
584    p_Delete(&factor, naRing);
585    definiteReduce(pow, naMinpoly, cf);
586  }
587
588  /* invert if original exponent was negative */
589  number n = (number)pow;
590  if (exp < 0)
591  {
592    number m = naInvers(n, cf);
593    naDelete(&n, cf);
594    n = m;
595  }
596  *b = n;
597}
598
599/* may reduce p modulo the reducer by calling definiteReduce;
600   the decision is made based on the following heuristic
601   (which should also only be changed here in this method):
602      if (deg(p) > 10*deg(reducer) then perform reduction;
603   modifies p */
604void heuristicReduce(poly &p, poly reducer, const coeffs cf)
605{
606  #ifdef LDEBUG
607  p_Test((poly)p, naRing);
608  p_Test((poly)reducer, naRing);
609  #endif
610  if (p_Totaldegree(p, naRing) > 10 * p_Totaldegree(reducer, naRing))
611    definiteReduce(p, reducer, cf);
612}
613
614void naWriteLong(number &a, const coeffs cf)
615{
616  naTest(a);
617  if (a == NULL)
618    StringAppendS("0");
619  else
620  {
621    poly aAsPoly = (poly)a;
622    /* basically, just write aAsPoly using p_Write,
623       but use brackets around the output, if a is not
624       a constant living in naCoeffs = cf->extRing->cf */
625    BOOLEAN useBrackets = !(p_IsConstant(aAsPoly, naRing));
626    if (useBrackets) StringAppendS("(");
627    p_String0Long(aAsPoly, naRing, naRing);
628    if (useBrackets) StringAppendS(")");
629  }
630}
631
632void naWriteShort(number &a, const coeffs cf)
633{
634  naTest(a);
635  if (a == NULL)
636    StringAppendS("0");
637  else
638  {
639    poly aAsPoly = (poly)a;
640    /* basically, just write aAsPoly using p_Write,
641       but use brackets around the output, if a is not
642       a constant living in naCoeffs = cf->extRing->cf */
643    BOOLEAN useBrackets = !(p_IsConstant(aAsPoly, naRing));
644    if (useBrackets) StringAppendS("(");
645    p_String0Short(aAsPoly, naRing, naRing);
646    if (useBrackets) StringAppendS(")");
647  }
648}
649
650const char * naRead(const char *s, number *a, const coeffs cf)
651{
652  poly aAsPoly;
653  const char * result = p_Read(s, aAsPoly, naRing);
654  definiteReduce(aAsPoly, naMinpoly, cf);
655  *a = (number)aAsPoly;
656  return result;
657}
658
659#if 0
660/* implemented by the rule lcm(a, b) = a * b / gcd(a, b) */
661number naLcm(number a, number b, const coeffs cf)
662{
663  naTest(a); naTest(b);
664  if (a == NULL) return NULL;
665  if (b == NULL) return NULL;
666  number theProduct = (number)p_Mult_q(p_Copy((poly)a, naRing),
667                                       p_Copy((poly)b, naRing), naRing);
668  /* note that theProduct needs not be reduced w.r.t. naMinpoly;
669     but the final division will take care of the necessary reduction */
670  number theGcd = naGcd(a, b, cf);
671  return naDiv(theProduct, theGcd, cf);
672}
673#endif
674number napLcm(number b, const coeffs cf)
675{
676  number h=n_Init(1,naRing->cf);
677  poly bb=(poly)b;
678  number d;
679  while(bb!=NULL)
680  {
681    d=n_Lcm(h,pGetCoeff(bb), naRing->cf);
682    n_Delete(&h,naRing->cf);
683    h=d;
684    pIter(bb);
685  }
686  return h;
687}
688number naLcmContent(number a, number b, const coeffs cf)
689{
690  if (nCoeff_is_Zp(naRing->cf)) return naCopy(a,cf);
691#if 0
692  else {
693    number g = ndGcd(a, b, cf);
694    return g;
695  }
696#else
697  {
698    a=(number)p_Copy((poly)a,naRing);
699    number t=napLcm(b,cf);
700    if(!n_IsOne(t,naRing->cf))
701    {
702      number bt, rr;
703      poly xx=(poly)a;
704      while (xx!=NULL)
705      {
706        bt = n_Gcd(t, pGetCoeff(xx), naRing->cf);
707        rr = n_Mult(t, pGetCoeff(xx), naRing->cf);
708        n_Delete(&pGetCoeff(xx),naRing->cf);
709        pGetCoeff(xx) = n_Div(rr, bt, naRing->cf);
710        n_Normalize(pGetCoeff(xx),naRing->cf);
711        n_Delete(&bt,naRing->cf);
712        n_Delete(&rr,naRing->cf);
713        pIter(xx);
714      }
715    }
716    n_Delete(&t,naRing->cf);
717    return (number) a;
718  }
719#endif
720}
721
722/* expects *param to be castable to AlgExtInfo */
723static BOOLEAN naCoeffIsEqual(const coeffs cf, n_coeffType n, void * param)
724{
725  if (ID != n) return FALSE;
726  AlgExtInfo *e = (AlgExtInfo *)param;
727  /* for extension coefficient fields we expect the underlying
728     polynomial rings to be IDENTICAL, i.e. the SAME OBJECT;
729     this expectation is based on the assumption that we have properly
730     registered cf and perform reference counting rather than creating
731     multiple copies of the same coefficient field/domain/ring */
732  if (naRing == e->r)
733    return TRUE;
734  /* (Note that then also the minimal ideals will necessarily be
735     the same, as they are attached to the ring.) */
736
737  // NOTE: Q(a)[x] && Q(a)[y] should better share the _same_ Q(a)...
738  if( rEqual(naRing, e->r, TRUE) ) // also checks the equality of qideals
739  {
740    const ideal mi = naRing->qideal;
741    assume( IDELEMS(mi) == 1 );
742    const ideal ii = e->r->qideal;
743    assume( IDELEMS(ii) == 1 );
744
745    // TODO: the following should be extended for 2 *equal* rings...
746    assume( p_EqualPolys(mi->m[0], ii->m[0], naRing, e->r) );
747
748    rDelete(e->r);
749
750    return TRUE;
751  }
752
753  return FALSE;
754
755}
756
757int naSize(number a, const coeffs cf)
758{
759  if (a == NULL) return -1;
760  /* this has been taken from the old implementation of field extensions,
761     where we computed the sum of the degree and the number of terms in
762     (poly)a; so we leave it at that, for the time being;
763     maybe, the number of terms alone is a better measure? */
764  poly aAsPoly = (poly)a;
765  int theDegree = 0; int noOfTerms = 0;
766  while (aAsPoly != NULL)
767  {
768    noOfTerms++;
769    int d = p_GetExp(aAsPoly, 1, naRing);
770    if (d > theDegree) theDegree = d;
771    pIter(aAsPoly);
772  }
773  return theDegree + noOfTerms;
774}
775
776/* performs polynomial division and overrides p by the remainder
777   of division of p by the reducer;
778   modifies p */
779void definiteReduce(poly &p, poly reducer, const coeffs cf)
780{
781  #ifdef LDEBUG
782  p_Test((poly)p, naRing);
783  p_Test((poly)reducer, naRing);
784  #endif
785  if ((p!=NULL) && (p_GetExp(p,1,naRing)>=p_GetExp(reducer,1,naRing)))
786  {
787    p_PolyDiv(p, reducer, FALSE, naRing);
788  }
789}
790
791void  naNormalize(number &a, const coeffs cf)
792{
793  poly aa=(poly)a;
794  if (aa!=naMinpoly)
795    definiteReduce(aa,naMinpoly,cf);
796  a=(number)aa;
797}
798
799#ifdef HAVE_FACTORY
800number naConvFactoryNSingN( const CanonicalForm n, const coeffs cf)
801{
802  if (n.isZero()) return NULL;
803  poly p=convFactoryPSingP(n,naRing);
804  return (number)p;
805}
806CanonicalForm naConvSingNFactoryN( number n, BOOLEAN /*setChar*/, const coeffs cf )
807{
808  naTest(n);
809  if (n==NULL) return CanonicalForm(0);
810
811  return convSingPFactoryP((poly)n,naRing);
812}
813#endif
814
815
816/* IMPORTANT NOTE: Since an algebraic field extension is again a field,
817                   the gcd of two elements is not very interesting. (It
818                   is actually any unit in the field, i.e., any non-
819                   zero element.) Note that the below method does not operate
820                   in this strong sense but rather computes the gcd of
821                   two given elements in the underlying polynomial ring. */
822number naGcd(number a, number b, const coeffs cf)
823{
824  if (a==NULL)  return naCopy(b,cf);
825  if (b==NULL)  return naCopy(a,cf);
826
827  poly ax=(poly)a;
828  poly bx=(poly)b;
829  if (pNext(ax)!=NULL)
830    return (number)p_Copy(ax, naRing);
831  else
832  {
833    if(nCoeff_is_Zp(naRing->cf))
834      return naInit(1,cf);
835    else
836    {
837      number x = n_Copy(pGetCoeff((poly)a),naRing->cf);
838      if (n_IsOne(x,naRing->cf))
839        return (number)p_NSet(x,naRing);
840      while (pNext(ax)!=NULL)
841      {
842        pIter(ax);
843        number y = n_Gcd(x, pGetCoeff(ax), naRing->cf);
844        n_Delete(&x,naRing->cf);
845        x = y;
846        if (n_IsOne(x,naRing->cf))
847          return (number)p_NSet(x,naRing);
848      }
849      do
850      {
851        number y = n_Gcd(x, pGetCoeff(bx), naRing->cf);
852        n_Delete(&x,naRing->cf);
853        x = y;
854        if (n_IsOne(x,naRing->cf))
855          return (number)p_NSet(x,naRing);
856        pIter(bx);
857      }
858      while (bx!=NULL);
859      return (number)p_NSet(x,naRing);
860    }
861  }
862#if 0
863  naTest(a); naTest(b);
864  const ring R = naRing;
865  return (number) singclap_gcd(p_Copy((poly)a, R), p_Copy((poly)b, R), R);
866#endif
867//  return (number)p_Gcd((poly)a, (poly)b, naRing);
868}
869
870number naInvers(number a, const coeffs cf)
871{
872  naTest(a);
873  if (a == NULL) WerrorS(nDivBy0);
874
875  poly aFactor = NULL; poly mFactor = NULL; poly theGcd = NULL;
876// singclap_extgcd!
877  const BOOLEAN ret = singclap_extgcd ((poly)a, naMinpoly, theGcd, aFactor, mFactor, naRing);
878
879  assume( !ret );
880
881//  if( ret ) theGcd = p_ExtGcd((poly)a, aFactor, naMinpoly, mFactor, naRing);
882
883  naTest((number)theGcd); naTest((number)aFactor); naTest((number)mFactor);
884  p_Delete(&mFactor, naRing);
885
886  //  /* the gcd must be 1 since naMinpoly is irreducible and a != NULL: */
887  //  assume(naIsOne((number)theGcd, cf));
888
889  if( !naIsOne((number)theGcd, cf) )
890  {
891    WerrorS("zero divisor found - your minpoly is not irreducible");
892    p_Delete(&aFactor, naRing); aFactor = NULL;
893  }
894  p_Delete(&theGcd, naRing);
895
896  return (number)(aFactor);
897}
898
899/* assumes that src = Q, dst = Q(a) */
900number naMap00(number a, const coeffs src, const coeffs dst)
901{
902  if (n_IsZero(a, src)) return NULL;
903  assume(src == dst->extRing->cf);
904  poly result = p_One(dst->extRing);
905  p_SetCoeff(result, n_Copy(a, src), dst->extRing);
906  return (number)result;
907}
908
909/* assumes that src = Z/p, dst = Q(a) */
910number naMapP0(number a, const coeffs src, const coeffs dst)
911{
912  if (n_IsZero(a, src)) return NULL;
913  /* mapping via intermediate int: */
914  int n = n_Int(a, src);
915  number q = n_Init(n, dst->extRing->cf);
916  poly result = p_One(dst->extRing);
917  p_SetCoeff(result, q, dst->extRing);
918  return (number)result;
919}
920
921#if 0
922/* assumes that either src = Q(a), dst = Q(a), or
923                       src = Z/p(a), dst = Z/p(a)     */
924number naCopyMap(number a, const coeffs src, const coeffs dst)
925{
926  return naCopy(a, dst);
927}
928#endif
929
930number naCopyTrans2AlgExt(number a, const coeffs src, const coeffs dst)
931{
932  assume (nCoeff_is_transExt (src));
933  assume (nCoeff_is_algExt (dst));
934  fraction fa=(fraction)a;
935  poly p, q;
936  if (rSamePolyRep(src->extRing, dst->extRing))
937  {
938    p = p_Copy(NUM(fa),src->extRing);
939    if (!DENIS1(fa))
940    {
941      q = p_Copy(DEN(fa),src->extRing);
942      assume (q != NULL);
943    }
944  }
945  else
946  {
947    assume ((strcmp(rRingVar(0,src->extRing),rRingVar(0,dst->extRing))==0) && (rVar (src->extRing) == rVar (dst->extRing)));
948
949    nMapFunc nMap= n_SetMap (src->extRing->cf, dst->extRing->cf);
950
951    assume (nMap != NULL);
952    p= p_PermPoly (NUM (fa), NULL, src->extRing, dst->extRing,nMap, NULL,rVar (src->extRing));
953    if (!DENIS1(fa))
954    {
955      q= p_PermPoly (DEN (fa), NULL, src->extRing, dst->extRing,nMap, NULL,rVar (src->extRing));
956      assume (q != NULL);
957    }
958  }
959  definiteReduce(p, dst->extRing->qideal->m[0], dst);
960  assume (p_Test (p, dst->extRing));
961  if (!DENIS1(fa))
962  {
963    definiteReduce(q, dst->extRing->qideal->m[0], dst);
964    assume (p_Test (q, dst->extRing));
965    if (q != NULL)
966    {
967      number t= naDiv ((number)p,(number)q, dst);
968      p_Delete (&p, dst->extRing);
969      p_Delete (&q, dst->extRing);
970      return t;
971    }
972    WerrorS ("mapping denominator to zero");
973  }
974  return (number) p;
975}
976
977/* assumes that src = Q, dst = Z/p(a) */
978number naMap0P(number a, const coeffs src, const coeffs dst)
979{
980  if (n_IsZero(a, src)) return NULL;
981  // int p = rChar(dst->extRing);
982
983  number q = nlModP(a, src, dst->extRing->cf);
984
985  poly result = p_NSet(q, dst->extRing);
986
987  return (number)result;
988}
989
990/* assumes that src = Z/p, dst = Z/p(a) */
991number naMapPP(number a, const coeffs src, const coeffs dst)
992{
993  if (n_IsZero(a, src)) return NULL;
994  assume(src == dst->extRing->cf);
995  poly result = p_One(dst->extRing);
996  p_SetCoeff(result, n_Copy(a, src), dst->extRing);
997  return (number)result;
998}
999
1000/* assumes that src = Z/u, dst = Z/p(a), where u != p */
1001number naMapUP(number a, const coeffs src, const coeffs dst)
1002{
1003  if (n_IsZero(a, src)) return NULL;
1004  /* mapping via intermediate int: */
1005  int n = n_Int(a, src);
1006  number q = n_Init(n, dst->extRing->cf);
1007  poly result = p_One(dst->extRing);
1008  p_SetCoeff(result, q, dst->extRing);
1009  return (number)result;
1010}
1011
1012nMapFunc naSetMap(const coeffs src, const coeffs dst)
1013{
1014  /* dst is expected to be an algebraic field extension */
1015  assume(getCoeffType(dst) == ID);
1016
1017  if( src == dst ) return ndCopyMap;
1018
1019  int h = 0; /* the height of the extension tower given by dst */
1020  coeffs bDst = nCoeff_bottom(dst, h); /* the bottom field in the tower dst */
1021  coeffs bSrc = nCoeff_bottom(src, h); /* the bottom field in the tower src */
1022
1023  /* for the time being, we only provide maps if h = 1 and if b is Q or
1024     some field Z/pZ: */
1025  if (h==0)
1026  {
1027    if (nCoeff_is_Q(src) && nCoeff_is_Q(bDst))
1028      return naMap00;                            /// Q     -->  Q(a)
1029    if (nCoeff_is_Zp(src) && nCoeff_is_Q(bDst))
1030      return naMapP0;                            /// Z/p   -->  Q(a)
1031    if (nCoeff_is_Q(src) && nCoeff_is_Zp(bDst))
1032      return naMap0P;                            /// Q      --> Z/p(a)
1033    if (nCoeff_is_Zp(src) && nCoeff_is_Zp(bDst))
1034    {
1035      if (src->ch == dst->ch) return naMapPP;    /// Z/p    --> Z/p(a)
1036      else return naMapUP;                       /// Z/u    --> Z/p(a)
1037    }
1038  }
1039  if (h != 1) return NULL;
1040  if ((!nCoeff_is_Zp(bDst)) && (!nCoeff_is_Q(bDst))) return NULL;
1041  if ((!nCoeff_is_Zp(bSrc)) && (!nCoeff_is_Q(bSrc))) return NULL;
1042
1043  if (nCoeff_is_Q(bSrc) && nCoeff_is_Q(bDst))
1044  {
1045    if (rSamePolyRep(src->extRing, dst->extRing) && (strcmp(rRingVar(0, src->extRing), rRingVar(0, dst->extRing)) == 0))
1046    {
1047      if (src->type==n_algExt)
1048         return ndCopyMap; // naCopyMap;         /// Q(a)   --> Q(a)
1049      else
1050         return naCopyTrans2AlgExt;
1051    }
1052    else
1053      return NULL;                               /// Q(b)   --> Q(a)
1054  }
1055
1056  if (nCoeff_is_Zp(bSrc) && nCoeff_is_Zp(bDst))
1057  {
1058    if (rSamePolyRep(src->extRing, dst->extRing) && (strcmp(rRingVar(0,src->extRing),rRingVar(0,dst->extRing))==0))
1059    {
1060      if (src->type==n_algExt)
1061        return ndCopyMap; // naCopyMap;          /// Z/p(a) --> Z/p(a)
1062      else
1063         return naCopyTrans2AlgExt;
1064    }
1065    else if ((strcmp(rRingVar(0,src->extRing),rRingVar(0,dst->extRing))==0) && (rVar (src->extRing) == rVar (dst->extRing)))
1066    {
1067      if (src->type==n_transExt)
1068        return naCopyTrans2AlgExt;
1069    }
1070  }
1071
1072  return NULL;                                           /// default
1073}
1074
1075static int naParDeg(number a, const coeffs cf)
1076{
1077  if (a == NULL) return -1;
1078  poly aa=(poly)a;
1079  return cf->extRing->pFDeg(aa,cf->extRing);
1080}
1081
1082/// return the specified parameter as a number in the given alg. field
1083static number naParameter(const int iParameter, const coeffs cf)
1084{
1085  assume(getCoeffType(cf) == ID);
1086
1087  const ring R = cf->extRing;
1088  assume( R != NULL );
1089  assume( 0 < iParameter && iParameter <= rVar(R) );
1090
1091  poly p = p_One(R); p_SetExp(p, iParameter, 1, R); p_Setm(p, R);
1092
1093  return (number) p;
1094}
1095
1096
1097/// if m == var(i)/1 => return i,
1098int naIsParam(number m, const coeffs cf)
1099{
1100  assume(getCoeffType(cf) == ID);
1101
1102  const ring R = cf->extRing;
1103  assume( R != NULL );
1104
1105  return p_Var( (poly)m, R );
1106}
1107
1108
1109static void naClearContent(ICoeffsEnumerator& numberCollectionEnumerator, number& c, const coeffs cf)
1110{
1111  assume(cf != NULL);
1112  assume(getCoeffType(cf) == ID);
1113  assume(nCoeff_is_Q_algext(cf)); // only over (Q[a]/m(a)), while the default impl. is used over Zp[a]/m(a) !
1114
1115  const ring   R = cf->extRing;
1116  assume(R != NULL);
1117  const coeffs Q = R->cf;
1118  assume(Q != NULL);
1119  assume(nCoeff_is_Q(Q));
1120
1121  numberCollectionEnumerator.Reset();
1122
1123  if( !numberCollectionEnumerator.MoveNext() ) // empty zero polynomial?
1124  {
1125    c = n_Init(1, cf);
1126    return;
1127  }
1128
1129  naTest(numberCollectionEnumerator.Current());
1130
1131  // part 1, find a small candidate for gcd
1132  int s1; int s=2147483647; // max. int
1133
1134  const BOOLEAN lc_is_pos=naGreaterZero(numberCollectionEnumerator.Current(),cf);
1135
1136  int normalcount = 0;
1137
1138  poly cand1, cand;
1139
1140  do
1141  {
1142    number& n = numberCollectionEnumerator.Current();
1143    naNormalize(n, cf); ++normalcount;
1144
1145    naTest(n);
1146
1147    cand1 = (poly)n;
1148
1149    s1 = p_Deg(cand1, R); // naSize?
1150    if (s>s1)
1151    {
1152      cand = cand1;
1153      s = s1;
1154    }
1155  } while (numberCollectionEnumerator.MoveNext() );
1156
1157//  assume( nlGreaterZero(cand,cf) ); // cand may be a negative integer!
1158
1159  cand = p_Copy(cand, R);
1160  // part 2: compute gcd(cand,all coeffs)
1161
1162  numberCollectionEnumerator.Reset();
1163
1164  int length = 0;
1165  while (numberCollectionEnumerator.MoveNext() )
1166  {
1167    number& n = numberCollectionEnumerator.Current();
1168    ++length;
1169
1170    if( (--normalcount) <= 0)
1171      naNormalize(n, cf);
1172
1173    naTest(n);
1174
1175//    p_InpGcd(cand, (poly)n, R);
1176
1177    cand = singclap_gcd(cand, p_Copy((poly)n, R), R);
1178
1179//    cand1 = p_Gcd(cand,(poly)n, R); p_Delete(&cand, R); cand = cand1;
1180
1181    assume( naGreaterZero((number)cand, cf) ); // ???
1182/*
1183    if(p_IsConstant(cand,R))
1184    {
1185      c = cand;
1186
1187      if(!lc_is_pos)
1188      {
1189        // make the leading coeff positive
1190        c = nlNeg(c, cf);
1191        numberCollectionEnumerator.Reset();
1192
1193        while (numberCollectionEnumerator.MoveNext() )
1194        {
1195          number& nn = numberCollectionEnumerator.Current();
1196          nn = nlNeg(nn, cf);
1197        }
1198      }
1199      return;
1200    }
1201*/
1202
1203  }
1204
1205
1206  // part3: all coeffs = all coeffs / cand
1207  if (!lc_is_pos)
1208    cand = p_Neg(cand, R);
1209
1210  c = (number)cand; naTest(c);
1211
1212  poly cInverse = (poly)naInvers(c, cf);
1213  assume(cInverse != NULL); // c is non-zero divisor!?
1214
1215
1216  numberCollectionEnumerator.Reset();
1217
1218
1219  while (numberCollectionEnumerator.MoveNext() )
1220  {
1221    number& n = numberCollectionEnumerator.Current();
1222
1223    assume( length > 0 );
1224
1225    if( --length > 0 )
1226    {
1227      assume( cInverse != NULL );
1228      n = (number) p_Mult_q(p_Copy(cInverse, R), (poly)n, R);
1229    }
1230    else
1231    {
1232      n = (number) p_Mult_q(cInverse, (poly)n, R);
1233      cInverse = NULL;
1234      assume(length == 0);
1235    }
1236
1237    definiteReduce((poly &)n, naMinpoly, cf);
1238  }
1239
1240  assume(length == 0);
1241  assume(cInverse == NULL); //   p_Delete(&cInverse, R);
1242
1243  // Quick and dirty fix for constant content clearing... !?
1244  CRecursivePolyCoeffsEnumerator<NAConverter> itr(numberCollectionEnumerator); // recursively treat the numbers as polys!
1245
1246  number cc;
1247
1248  n_ClearContent(itr, cc, Q); // TODO: get rid of (-LC) normalization!?
1249
1250  // over alg. ext. of Q // takes over the input number
1251  c = (number) p_Mult_nn( (poly)c, cc, R);
1252//      p_Mult_q(p_NSet(cc, R), , R);
1253
1254  n_Delete(&cc, Q);
1255
1256  // TODO: the above is not enough! need GCD's of polynomial coeffs...!
1257/*
1258  // old and wrong part of p_Content
1259    if (rField_is_Q_a(r) && !CLEARENUMERATORS) // should not be used anymore if CLEARENUMERATORS is 1
1260    {
1261      // we only need special handling for alg. ext.
1262      if (getCoeffType(r->cf)==n_algExt)
1263      {
1264        number hzz = n_Init(1, r->cf->extRing->cf);
1265        p=ph;
1266        while (p!=NULL)
1267        { // each monom: coeff in Q_a
1268          poly c_n_n=(poly)pGetCoeff(p);
1269          poly c_n=c_n_n;
1270          while (c_n!=NULL)
1271          { // each monom: coeff in Q
1272            d=n_Lcm(hzz,pGetCoeff(c_n),r->cf->extRing->cf);
1273            n_Delete(&hzz,r->cf->extRing->cf);
1274            hzz=d;
1275            pIter(c_n);
1276          }
1277          pIter(p);
1278        }
1279        // hzz contains the 1/lcm of all denominators in c_n_n
1280        h=n_Invers(hzz,r->cf->extRing->cf);
1281        n_Delete(&hzz,r->cf->extRing->cf);
1282        n_Normalize(h,r->cf->extRing->cf);
1283        if(!n_IsOne(h,r->cf->extRing->cf))
1284        {
1285          p=ph;
1286          while (p!=NULL)
1287          { // each monom: coeff in Q_a
1288            poly c_n=(poly)pGetCoeff(p);
1289            while (c_n!=NULL)
1290            { // each monom: coeff in Q
1291              d=n_Mult(h,pGetCoeff(c_n),r->cf->extRing->cf);
1292              n_Normalize(d,r->cf->extRing->cf);
1293              n_Delete(&pGetCoeff(c_n),r->cf->extRing->cf);
1294              pGetCoeff(c_n)=d;
1295              pIter(c_n);
1296            }
1297            pIter(p);
1298          }
1299        }
1300        n_Delete(&h,r->cf->extRing->cf);
1301      }
1302    }
1303*/
1304
1305
1306//  c = n_Init(1, cf); assume(FALSE); // TODO: NOT YET IMPLEMENTED!!!
1307}
1308
1309
1310static void naClearDenominators(ICoeffsEnumerator& numberCollectionEnumerator, number& c, const coeffs cf)
1311{
1312  assume(cf != NULL);
1313  assume(getCoeffType(cf) == ID);
1314  assume(nCoeff_is_Q_algext(cf)); // only over (Q[a]/m(a)), while the default impl. is used over Zp[a]/m(a) !
1315
1316  assume(cf->extRing != NULL);
1317  const coeffs Q = cf->extRing->cf;
1318  assume(Q != NULL);
1319  assume(nCoeff_is_Q(Q));
1320  number n;
1321  CRecursivePolyCoeffsEnumerator<NAConverter> itr(numberCollectionEnumerator); // recursively treat the numbers as polys!
1322  n_ClearDenominators(itr, n, Q); // this should probably be fine...
1323  c = (number)p_NSet(n, cf->extRing); // over alg. ext. of Q // takes over the input number
1324}
1325
1326void naKillChar(coeffs cf)
1327{
1328   if ((--cf->extRing->ref) == 0)
1329     rDelete(cf->extRing);
1330}
1331
1332
1333
1334BOOLEAN naInitChar(coeffs cf, void * infoStruct)
1335{
1336  assume( infoStruct != NULL );
1337
1338  AlgExtInfo *e = (AlgExtInfo *)infoStruct;
1339  /// first check whether cf->extRing != NULL and delete old ring???
1340
1341  assume(e->r                     != NULL);      // extRing;
1342  assume(e->r->cf                 != NULL);      // extRing->cf;
1343
1344  assume((e->r->qideal            != NULL) &&    // minideal has one
1345         (IDELEMS(e->r->qideal)   == 1)    &&    // non-zero generator
1346         (e->r->qideal->m[0]      != NULL)    ); // at m[0];
1347
1348  assume( cf != NULL );
1349  assume(getCoeffType(cf) == ID);                     // coeff type;
1350
1351  e->r->ref ++; // increase the ref.counter for the ground poly. ring!
1352  const ring R = e->r; // no copy!
1353  assume( R->qideal == e->r->qideal );
1354  cf->extRing  = R;
1355
1356  /* propagate characteristic up so that it becomes
1357     directly accessible in cf: */
1358  cf->ch = R->cf->ch;
1359
1360  #ifdef LDEBUG
1361  p_Test((poly)naMinpoly, naRing);
1362  #endif
1363
1364  cf->cfGreaterZero  = naGreaterZero;
1365  cf->cfGreater      = naGreater;
1366  cf->cfEqual        = naEqual;
1367  cf->cfIsZero       = naIsZero;
1368  cf->cfIsOne        = naIsOne;
1369  cf->cfIsMOne       = naIsMOne;
1370  cf->cfInit         = naInit;
1371  cf->cfInit_bigint  = naInit_bigint;
1372  cf->cfInt          = naInt;
1373  cf->cfNeg          = naNeg;
1374  cf->cfAdd          = naAdd;
1375  cf->cfSub          = naSub;
1376  cf->cfMult         = naMult;
1377  cf->cfDiv          = naDiv;
1378  cf->cfExactDiv     = naDiv;
1379  cf->cfPower        = naPower;
1380  cf->cfCopy         = naCopy;
1381
1382  cf->cfWriteLong        = naWriteLong;
1383
1384  if( rCanShortOut(naRing) )
1385    cf->cfWriteShort = naWriteShort;
1386  else
1387    cf->cfWriteShort = naWriteLong;
1388
1389  cf->cfRead         = naRead;
1390  cf->cfDelete       = naDelete;
1391  cf->cfSetMap       = naSetMap;
1392  cf->cfGetDenom     = naGetDenom;
1393  cf->cfGetNumerator = naGetNumerator;
1394  cf->cfRePart       = naCopy;
1395  cf->cfImPart       = naImPart;
1396  cf->cfCoeffWrite   = naCoeffWrite;
1397  cf->cfNormalize    = naNormalize;
1398  cf->cfKillChar     = naKillChar;
1399#ifdef LDEBUG
1400  cf->cfDBTest       = naDBTest;
1401#endif
1402  cf->cfGcd          = naGcd;
1403  cf->cfLcm          = naLcmContent;
1404  cf->cfSize         = naSize;
1405  cf->nCoeffIsEqual  = naCoeffIsEqual;
1406  cf->cfInvers       = naInvers;
1407  cf->cfIntDiv       = naDiv; // ???
1408#ifdef HAVE_FACTORY
1409  cf->convFactoryNSingN=naConvFactoryNSingN;
1410  cf->convSingNFactoryN=naConvSingNFactoryN;
1411#endif
1412  cf->cfParDeg = naParDeg;
1413
1414  cf->iNumberOfParameters = rVar(R);
1415  cf->pParameterNames = R->names;
1416  cf->cfParameter = naParameter;
1417
1418  if( nCoeff_is_Q(R->cf) )
1419  {
1420    cf->cfClearContent = naClearContent;
1421    cf->cfClearDenominators = naClearDenominators;
1422  }
1423
1424  return FALSE;
1425}
Note: See TracBrowser for help on using the repository browser.