source: git/libpolys/polys/ext_fields/algext.cc @ 70305c5

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