Index: factory/int_poly.cc
===================================================================
--- factory/int_poly.cc	(revision 2dd068c3d0ef548417675269401bdc269475bf0b)
+++ factory/int_poly.cc	(revision 2dd068c3d0ef548417675269401bdc269475bf0b)
@@ -0,0 +1,1300 @@
+// emacs edit mode for this file is -*- C++ -*-
+// $Id: int_poly.cc,v 1.0 1996-05-17 10:59:46 stobbe Exp $
+
+/*
+$Log: not supported by cvs2svn $
+*/
+
+#include <string.h>
+#include <strstream.h>
+
+#include "assert.h"
+#include "cf_defs.h"
+#include "cf_factory.h"
+#include "int_cf.h"
+#include "int_poly.h"
+#include "canonicalform.h"
+#include "variable.h"
+#include "imm.h"
+
+
+InternalPoly::InternalPoly( termList first, termList last, const Variable & v )
+{
+    firstTerm = first;
+    lastTerm = last;
+    var = v;
+}
+
+InternalPoly::InternalPoly()
+{
+    ASSERT( 0, "ups, why do you initialize an empty poly" );
+}
+
+InternalPoly::InternalPoly( const Variable & v, const int e, const CanonicalForm& c )
+{
+    var = v;
+    firstTerm = new term( 0, c, e );
+    lastTerm = firstTerm;
+}
+
+InternalPoly::InternalPoly( const InternalPoly& )
+{
+    cerr << "ups there is something wrong in your code" << endl; 
+}; 
+
+InternalPoly::~InternalPoly()
+{
+    freeTermList( firstTerm );
+}
+
+InternalCF*
+InternalPoly::deepCopyObject() const
+{
+    termList first, last;
+    first = deepCopyTermList( firstTerm, last );
+    return new InternalPoly( first, last, var );
+}
+
+InternalCF*
+InternalPoly::genZero()
+{
+    return firstTerm->coeff.genZero().getval();
+}
+
+InternalCF*
+InternalPoly::genOne()
+{
+    return firstTerm->coeff.genOne().getval();
+}
+
+bool
+InternalPoly::isUnivariate() const
+{
+    termList cursor = firstTerm;
+    while ( cursor ) {
+	if ( ! cursor->coeff.inCoeffDomain() )
+	    return false;
+	cursor = cursor->next;
+    }
+    return true;
+}
+
+int
+InternalPoly::degree()
+{
+    return firstTerm->exp;
+}
+
+int
+InternalPoly::sign() const
+{
+    return firstTerm->coeff.sign();
+}
+
+CanonicalForm
+InternalPoly::lc()
+{
+    return firstTerm->coeff.lc();
+}
+
+CanonicalForm
+InternalPoly::LC()
+{
+    return firstTerm->coeff;
+}
+
+int
+InternalPoly::taildegree()
+{
+    return lastTerm->exp;
+}
+
+CanonicalForm
+InternalPoly::tailcoeff()
+{
+    return lastTerm->coeff;
+}
+
+CanonicalForm
+InternalPoly::coeff( int i )
+{
+    termList theCursor = firstTerm;
+    while ( theCursor ) {
+	if ( theCursor->exp == i )
+	    return theCursor->coeff;
+	else if ( theCursor->exp > i )
+	    theCursor = theCursor->next;
+	else
+	    theCursor = 0;
+    }
+    return 0;
+}
+
+void
+InternalPoly::print(ostream &aStream, char * aString )
+{
+    if ( ! firstTerm ) 
+	aStream << 0 << aString;
+    else {
+	char * theString;
+	termList theCursor = firstTerm;
+	while ( theCursor ) {
+	    ostrstream theStream;
+	    if ( theCursor->exp == 0 )
+		theCursor->coeff.print( aStream, aString );
+	    else  if ( theCursor->coeff.isOne() ) {
+		aStream << var;
+		if ( theCursor->exp != 1 )
+		    aStream << '^' << theCursor->exp << aString;
+		else
+		    aStream << aString;
+	    }
+	    else  if ( theCursor->coeff.sign() < 0 && (-theCursor->coeff).isOne() ) {
+		aStream << '-' << var;
+		if ( theCursor->exp != 1 )
+		    aStream << '^' << theCursor->exp << aString;
+		else
+		    aStream << aString;
+	    }
+	    else {
+		theStream << '*' << var;
+		if ( theCursor->exp != 1 )
+		    theStream << '^' << theCursor->exp << aString << ends;
+		else
+		    theStream << aString << ends; // results from error in GNU strstream
+		theString = theStream.str();
+		theCursor->coeff.print( aStream, theString );
+		delete [] theString;
+	    }
+	    theCursor = theCursor->next;
+	    if ( theCursor && ( theCursor->coeff.sign() >= 0 ) )
+		aStream << '+';
+	}
+    }
+}
+
+InternalCF*
+InternalPoly::neg()
+{
+    if ( getRefCount() == 1 ) {
+	negateTermList( firstTerm );
+	return this;
+    }
+    else {
+	decRefCount();
+	termList last, first = copyTermList( firstTerm, last, true );
+	return new InternalPoly( first, last, var );
+    }
+}
+
+InternalCF*
+InternalPoly::invert()
+{
+    if ( inExtension() && getReduce( var ) ) {
+	setReduce( var, false );
+	CanonicalForm a( this->copyObject() );
+	CanonicalForm b = getMipo( var );
+	CanonicalForm u, v;
+	CanonicalForm g = extgcd( a, b, u, v );
+	setReduce( var, true );
+	return u.getval();
+    }
+    else
+	return CFFactory::basic( 0 );
+}
+
+int
+InternalPoly::comparesame ( InternalCF* acoeff )
+{
+    InternalPoly* apoly = (InternalPoly*)acoeff;
+    if ( this == apoly )
+	return 0;
+    else {
+	termList cur1 = firstTerm;
+	termList cur2 = apoly->firstTerm;
+	for ( ; cur1 && cur2; cur1 = cur1->next, cur2 = cur2->next )
+	    if ( ( cur1->exp != cur2->exp ) || ( cur1->coeff != cur2->coeff ) )
+		if ( cur1->exp > cur2->exp )
+		    return 1;
+		else  if ( cur1->exp < cur2->exp )
+		    return -1;
+		else  if ( cur1->coeff > cur2->coeff )
+		    return 1;
+		else
+		    return -1;
+	return cur1 != cur2;
+    }
+}
+
+InternalCF*
+InternalPoly::addsame( InternalCF* aCoeff )
+{
+    InternalPoly * aPoly = (InternalPoly*)aCoeff;
+    if ( getRefCount() == 1 ) {
+	firstTerm = addTermList( firstTerm, aPoly->firstTerm, lastTerm, false );
+	if ( firstTerm && firstTerm->exp != 0 )
+	    return this;
+	else  if ( firstTerm ) {
+	    InternalCF * res = firstTerm->coeff.getval();
+	    delete this;
+	    return res;
+	}
+	else {
+	    delete this;
+	    return CFFactory::basic( 0 );
+	}
+    }
+    else {
+	decRefCount();
+	termList last, first = copyTermList( firstTerm, last );
+	first = addTermList( first, aPoly->firstTerm, last, false );
+	if ( first && first->exp != 0 )
+	    return new InternalPoly( first, last, var );
+	else  if ( first ) {
+	    InternalCF * res = first->coeff.getval();
+	    delete first;
+	    return res;
+	}
+	else
+	    return CFFactory::basic( 0 );
+
+    }
+}
+
+InternalCF*
+InternalPoly::subsame( InternalCF* aCoeff )
+{
+    InternalPoly * aPoly = (InternalPoly*)aCoeff;
+    if ( getRefCount() == 1 ) {
+	firstTerm = addTermList( firstTerm, aPoly->firstTerm, lastTerm, true );
+	if ( firstTerm && firstTerm->exp != 0 )
+	    return this;
+	else  if ( firstTerm ) {
+	    InternalCF * res = firstTerm->coeff.getval();
+	    delete this;
+	    return res;
+	}
+	else {
+	    delete this;
+	    return CFFactory::basic( 0 );
+	}
+    }
+    else {
+	decRefCount();
+	termList last, first = copyTermList( firstTerm, last );
+	first = addTermList( first, aPoly->firstTerm, last, true );
+	if ( first && first->exp != 0 )
+	    return new InternalPoly( first, last, var );
+	else  if ( first ) {
+	    InternalCF * res = first->coeff.getval();
+	    delete first;
+	    return res;
+	}
+	else
+	    return CFFactory::basic( 0 );
+
+    }
+}
+
+InternalCF*
+InternalPoly::mulsame( InternalCF* aCoeff )
+{
+    InternalPoly *aPoly = (InternalPoly*)aCoeff;
+    termList resultFirst = 0, resultLast = 0;
+    termList theCursor = firstTerm;
+
+    while ( theCursor ) {
+	resultFirst = mulAddTermList( resultFirst, aPoly->firstTerm, theCursor->coeff, theCursor->exp, resultLast, false );
+	theCursor = theCursor->next;
+    }
+    if ( inExtension() && getReduce( var ) ) {
+	resultFirst = reduceTermList( resultFirst, (getInternalMipo( var ))->firstTerm, resultLast );
+	if ( resultFirst == 0 )
+	    if ( getRefCount() == 1 ) {
+		delete this;
+		return CFFactory::basic(0);
+	    }
+	    else {
+		decRefCount();
+		return CFFactory::basic(0);
+	    }
+	else  if ( resultFirst->exp == 0 )
+	    if ( getRefCount() == 1 ) {
+		InternalCF * res = resultFirst->coeff.getval();
+		delete resultFirst;
+		delete this;
+		return res;
+	    }
+	    else {
+		decRefCount();
+		InternalCF * res = resultFirst->coeff.getval();
+		delete resultFirst;
+		return res;
+	    }
+    }
+    if ( getRefCount() == 1 ) {
+	freeTermList( firstTerm );
+	firstTerm = resultFirst;
+	lastTerm = resultLast;
+	return this;
+    }
+    else {
+	decRefCount();
+	return new InternalPoly( resultFirst, resultLast, var );
+    }
+}
+
+InternalCF*
+InternalPoly::dividesame( InternalCF* aCoeff )
+{
+    return divsame( aCoeff );
+}
+
+
+InternalCF*
+InternalPoly::divsame( InternalCF* aCoeff )
+{
+    if ( inExtension() && getReduce( var ) ) {
+	InternalCF * dummy = aCoeff->invert();
+	dummy = dummy->mulsame( this );
+	if ( getRefCount() == 1 ) {
+	     delete this;
+	     return dummy;
+	}
+	else {
+	    decRefCount();
+	    return dummy;
+	}
+    }
+    InternalPoly *aPoly = (InternalPoly*)aCoeff;
+    termList dummy, first, last, resultfirst = 0, resultlast = 0;
+    CanonicalForm coeff, newcoeff;
+    int exp, newexp;
+    bool singleObject;
+
+    if ( getRefCount() == 1 ) {
+	first = firstTerm; last = lastTerm; singleObject = true;
+    }
+    else {
+	first = copyTermList( firstTerm, last ); singleObject = false;
+	decRefCount();
+    }
+    coeff = aPoly->firstTerm->coeff;
+    exp = aPoly->firstTerm->exp;
+    while (first && ( first->exp >= exp ) ) {
+	newcoeff = first->coeff / coeff;
+	newexp = first->exp - exp;
+	dummy = first;
+	first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
+	delete dummy;
+	appendTermList( resultfirst, resultlast, newcoeff, newexp );
+    }
+    freeTermList( first );
+    if ( singleObject ) {
+	if ( resultfirst && resultfirst->exp != 0 ) {
+	    firstTerm = resultfirst;
+	    lastTerm = resultlast;
+	    return this;
+	}
+	else  if ( resultfirst ) {
+	    InternalCF * res = resultfirst->coeff.getval();
+	    delete resultfirst;
+	    firstTerm = 0;
+	    delete this;
+	    return res;
+	}
+	else {
+	    // this should not happen (evtl use assertion)
+	    ASSERT( 0, "FATAL ERROR, PLEASE INFORM THE AUTHOR" );
+	    firstTerm = 0;
+	    delete this;
+	    return CFFactory::basic( 0 );
+	}
+    }
+    else {
+	if ( resultfirst && resultfirst->exp != 0 )
+	    return new InternalPoly( resultfirst, resultlast, var );
+	else  if ( resultfirst ) {
+	    InternalCF * res = resultfirst->coeff.getval();
+	    delete resultfirst;
+	    return res;
+	}
+	else
+	    return CFFactory::basic( 0 );
+    }
+}
+
+InternalCF*
+InternalPoly::modulosame( InternalCF* aCoeff )
+{
+    return modsame( aCoeff );
+}
+
+InternalCF*
+InternalPoly::modsame( InternalCF* aCoeff )
+{
+    if ( inExtension() && getReduce( var ) ) {
+	if ( deleteObject() ) delete this;
+	return CFFactory::basic( 0 );
+    }
+    InternalPoly *aPoly = (InternalPoly*)aCoeff;
+    termList dummy, first, last;
+    CanonicalForm coeff, newcoeff;
+    int exp, newexp;
+    bool singleObject;
+
+    if ( getRefCount() == 1 ) {
+	first = firstTerm; last = lastTerm; singleObject = true;
+    }
+    else {
+	first = copyTermList( firstTerm, last ); singleObject = false;
+	decRefCount();
+    }
+    coeff = aPoly->firstTerm->coeff;
+    exp = aPoly->firstTerm->exp;
+    while (first && ( first->exp >= exp ) ) {
+	newcoeff = first->coeff / coeff;
+	newexp = first->exp - exp;
+	dummy = first;
+	first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
+	delete dummy;
+    }
+    if ( singleObject ) {
+	if ( first && first->exp != 0 ) {
+	    firstTerm = first;
+	    lastTerm = last;
+	    return this;
+	}
+	else  if ( first ) {
+	    InternalCF * res = first->coeff.getval();
+	    delete first;
+	    firstTerm = 0;
+	    delete this;
+	    return res;
+	}
+	else {
+	    firstTerm = 0;
+	    delete this;
+	    return CFFactory::basic( 0 );
+	}
+    }
+    else {
+	if ( first && first->exp != 0 )
+	    return new InternalPoly( first, last, var );
+	else  if ( first ) {
+	    InternalCF * res = first->coeff.getval();
+	    delete first;
+	    return res;
+	}
+	else
+	    return CFFactory::basic( 0 );
+    }
+}
+
+
+void
+InternalPoly::divremsame( InternalCF* acoeff, InternalCF*& quot, InternalCF*& rem )
+{
+    if ( inExtension() && getReduce( var ) ) {
+	InternalCF * dummy = acoeff->invert();
+	quot = dummy->mulsame( this );
+	rem = CFFactory::basic( 0 );
+    }
+    else {
+	InternalPoly *aPoly = (InternalPoly*)acoeff;
+	termList dummy, first, last, resultfirst = 0, resultlast = 0;
+	CanonicalForm coeff, newcoeff;
+	int exp, newexp;
+
+	first = copyTermList( firstTerm, last );
+
+	coeff = aPoly->firstTerm->coeff;
+	exp = aPoly->firstTerm->exp;
+	while (first && ( first->exp >= exp ) ) {
+	    newcoeff = first->coeff / coeff;
+	    newexp = first->exp - exp;
+	    dummy = first;
+	    first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
+	    delete dummy;
+	    appendTermList( resultfirst, resultlast, newcoeff, newexp );
+	}
+	if ( resultfirst )
+	    if ( resultfirst->exp == 0 ) {
+		quot = resultfirst->coeff.getval();
+		delete resultfirst;
+	    }
+	    else
+		quot = new InternalPoly( resultfirst, resultlast, var );
+	else
+	    quot = CFFactory::basic( 0 );
+	if ( first )
+	    if ( first->exp == 0 ) {
+		rem = first->coeff.getval();
+		delete first;
+	    }
+	    else
+		rem = new InternalPoly( first, last, var );
+	else
+	    rem = CFFactory::basic( 0 );
+    }
+}
+
+
+bool
+InternalPoly::divremsamet( InternalCF* acoeff, InternalCF*& quot, InternalCF*& rem )
+{
+    if ( inExtension() && getReduce( var ) ) {
+	divremsame( acoeff, quot, rem );
+	return true;
+    }
+    InternalPoly *aPoly = (InternalPoly*)acoeff;
+    termList dummy, first, last, resultfirst = 0, resultlast = 0;
+    CanonicalForm coeff, newcoeff, dummycoeff;
+    int exp, newexp;
+    bool divideok = true;
+
+//    if ( ! ::divremt( lastTerm->coeff, aPoly->lastTerm->coeff, newcoeff, dummycoeff ) )
+//	return false;
+
+    first = copyTermList( firstTerm, last );
+
+    coeff = aPoly->firstTerm->coeff;
+    exp = aPoly->firstTerm->exp;
+    while (first && ( first->exp >= exp ) && divideok ) {
+	divideok = ::divremt( first->coeff, coeff, newcoeff, dummycoeff );
+	if ( divideok && dummycoeff.isZero() ) {
+	    newexp = first->exp - exp;
+	    dummy = first;
+	    first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
+	    delete dummy;
+	    appendTermList( resultfirst, resultlast, newcoeff, newexp );
+	}
+	else
+	    divideok = false;
+    }
+    if ( divideok ) {
+	if ( resultfirst )
+	    if ( resultfirst->exp == 0 ) {
+		quot = resultfirst->coeff.getval();
+		delete resultfirst;
+	    }
+	    else
+		quot = new InternalPoly( resultfirst, resultlast, var );
+	else
+	    quot = CFFactory::basic( 0 );
+	if ( first )
+	    if ( first->exp == 0 ) {
+		rem = first->coeff.getval();
+		delete first;
+	    }
+	    else
+		rem = new InternalPoly( first, last, var );
+	else
+	    rem = CFFactory::basic( 0 );
+    }
+    else {
+	freeTermList( resultfirst );
+	freeTermList( first );
+    }
+    return divideok;
+}
+
+int
+InternalPoly::comparecoeff ( InternalCF* acoeff )
+{
+    return 1;
+}
+
+InternalCF*
+InternalPoly::addcoeff( InternalCF* cc )
+{
+    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
+    if ( c.isZero() )
+	return this;
+    else {
+	if ( getRefCount() == 1 ) {
+	    if ( lastTerm->exp == 0 ) {
+		lastTerm->coeff += c;
+		if ( lastTerm->coeff.isZero() ) {
+		    termList cursor = firstTerm;
+		    while ( cursor->next != lastTerm )
+			cursor = cursor->next;
+		    delete lastTerm;
+		    cursor->next = 0;
+		    lastTerm = cursor;
+		}
+	    }
+	    else {
+		lastTerm->next = new term( 0, c, 0 );
+		lastTerm = lastTerm->next;
+	    }
+	    return this;
+	}
+	else {
+	    decRefCount();
+	    termList last, first = copyTermList( firstTerm, last, false );
+	    if ( last->exp == 0 ) {
+		last->coeff += c;
+		if ( last->coeff.isZero() ) {
+		    termList cursor = first;
+		    while ( cursor->next != last )
+			cursor = cursor->next;
+		    delete last;
+		    cursor->next = 0;
+		    last = cursor;
+		}
+	    }
+	    else {
+		last->next = new term( 0, c, 0 );
+		last = last->next;
+	    }
+	    return new InternalPoly( first, last, var );
+	}
+    }
+}
+
+InternalCF*
+InternalPoly::subcoeff( InternalCF* cc, bool negate )
+{
+    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
+    if ( c.isZero() )
+	if ( getRefCount() > 1 ) {
+	    decRefCount();
+	    termList last, first = copyTermList( firstTerm, last, negate );
+	    return new InternalPoly( first, last, var );
+	}
+	else {
+	    if ( negate )
+		negateTermList( firstTerm );
+	    return this;
+	}
+    else {
+	if ( getRefCount() == 1 ) {
+	    if ( lastTerm->exp == 0 ) {
+		if ( negate ) {
+		    negateTermList( firstTerm );
+		    lastTerm->coeff += c;
+		}
+		else
+		    lastTerm->coeff -= c;
+		if ( lastTerm->coeff.isZero() ) {
+		    termList cursor = firstTerm;
+		    while ( cursor->next != lastTerm )
+			cursor = cursor->next;
+		    delete lastTerm;
+		    cursor->next = 0;
+		    lastTerm = cursor;
+		}
+	    }
+	    else {
+		if ( negate ) {
+		    negateTermList( firstTerm );
+		    lastTerm->next = new term( 0, c, 0 );
+		}
+		else
+		    lastTerm->next = new term( 0, -c, 0 );
+		lastTerm = lastTerm->next;
+	    }
+	    return this;
+	}
+	else {
+	    decRefCount();
+	    termList last, first = copyTermList( firstTerm, last, negate );
+	    if ( last->exp == 0 ) {
+		if ( negate )
+		    last->coeff += c;
+		else
+		    last->coeff -= c;
+		if ( last->coeff.isZero() ) {
+		    termList cursor = first;
+		    while ( cursor->next != last )
+			cursor = cursor->next;
+		    delete last;
+		    cursor->next = 0;
+		    last = cursor;
+		}
+	    }
+	    else {
+		if ( negate )
+		    last->next = new term( 0, c, 0 );
+		else
+		    last->next = new term( 0, -c, 0 );
+		last = last->next;
+	    }
+	    return new InternalPoly( first, last, var );
+	}
+    }
+}
+
+InternalCF*
+InternalPoly::mulcoeff( InternalCF* cc )
+{
+    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
+    if ( c.isZero() ) {
+	if ( getRefCount() == 1 ) {
+	    delete this;
+	    return CFFactory::basic( 0 );
+	}
+	else {
+	    decRefCount();
+	    return CFFactory::basic( 0 );
+	}
+    }
+    else  if ( c.isOne() )
+	return this;
+    else {
+	if ( getRefCount() == 1 ) {
+	    mulTermList( firstTerm, c, 0 );
+	    return this;
+	}
+	else {
+	    decRefCount();
+	    termList last, first = copyTermList( firstTerm, last );
+	    mulTermList( first, c, 0 );
+	    return new InternalPoly( first, last, var );
+	}
+    }
+}
+
+InternalCF*
+InternalPoly::dividecoeff( InternalCF* c, bool invert )
+{
+    return divcoeff( c, invert );
+}
+
+InternalCF*
+InternalPoly::divcoeff( InternalCF* cc, bool invert )
+{
+    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
+    if ( inExtension() && getReduce( var ) && invert ) {
+	InternalCF * dummy;
+	dummy = this->invert();
+	dummy = dummy->mulcoeff( cc );
+	if ( getRefCount() == 1 ) {
+	    delete this;
+	    return dummy;
+	}
+	else {
+	    decRefCount();
+	    return dummy;
+	}
+    }
+    if ( invert )
+	if ( getRefCount() == 1 ) {
+	    delete this;
+	    return CFFactory::basic( 0 );
+	}
+	else {
+	    decRefCount();
+	    return CFFactory::basic( 0 );
+	}
+    if ( c.isOne() )
+	return this;
+    else {
+	if ( getRefCount() == 1 ) {
+	    firstTerm = divTermList( firstTerm, c, lastTerm );
+	    if ( firstTerm && firstTerm->exp != 0 )
+		return this;
+	    else  if ( firstTerm ) {
+		InternalCF * res = firstTerm->coeff.getval();
+		delete this;
+		return res;
+	    }
+	    else {
+		delete this;
+		return CFFactory::basic( 0 );
+	    }
+	}
+	else {
+	    decRefCount();
+	    termList last, first = copyTermList( firstTerm, last );
+	    first = divTermList( first, c, last );
+	    if ( first && first->exp != 0 )
+		return new InternalPoly( first, last, var );
+	    else  if ( first ) {
+		InternalCF * res = first->coeff.getval();
+		delete first;
+		return res;
+	    }
+	    else {
+		delete first;
+		return CFFactory::basic( 0 );
+	    }
+	}
+    }
+}
+
+InternalCF*
+InternalPoly::modulocoeff( InternalCF* cc, bool invert )
+{
+    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
+    if ( ! invert ) {
+	if ( deleteObject() ) delete this;
+	return c.getval();
+    }
+    ASSERT( ! c.isZero(), "divide by zero!" );
+    if ( deleteObject() ) delete this;
+    return CFFactory::basic( 0 );
+}
+
+InternalCF*
+InternalPoly::modcoeff( InternalCF* cc, bool invert )
+{
+    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
+    if ( invert ) {
+	if ( deleteObject() ) delete this;
+	return c.getval();
+    }
+    ASSERT( ! c.isZero(), "divide by zero!" );
+    if ( c.isOne() ) {
+        if ( getRefCount() == 1 ) {
+            delete this;
+            return CFFactory::basic( 0 );
+        }
+        else {
+            decRefCount();
+            return CFFactory::basic( 0 );
+        }
+    }
+    else {
+        if ( getRefCount() == 1 ) {
+            firstTerm = modTermList( firstTerm, c, lastTerm );
+            if ( firstTerm && firstTerm->exp != 0 )
+                return this;
+            else  if ( firstTerm ) {
+                InternalCF * res = firstTerm->coeff.getval();
+                delete this;
+                return res;
+            }
+            else {
+                delete this;
+                return CFFactory::basic( 0 );
+            }
+        }
+        else {
+            decRefCount();
+            termList last, first = copyTermList( firstTerm, last );
+            first = modTermList( first, c, last );
+            if ( first && first->exp != 0 )
+                return new InternalPoly( first, last, var );
+            else  if ( first ) {
+                InternalCF * res = first->coeff.getval();
+                delete first;
+                return res;
+            }
+            else {
+                delete first;
+                return CFFactory::basic( 0 );
+            }
+        }
+    }
+}
+
+void
+InternalPoly::divremcoeff( InternalCF* cc, InternalCF*& quot, InternalCF*& rem, bool invert )
+{
+    if ( inExtension() && getReduce( var ) ) {
+	quot = copyObject();
+	quot = quot->dividecoeff( cc, invert );
+	rem = CFFactory::basic( 0 );
+    }
+    else  if ( invert ) {
+	if ( is_imm( cc ) )
+	    rem = cc;
+	else
+	    rem = cc->copyObject();
+	quot = CFFactory::basic( 0 );
+    }
+    else {
+	CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
+	ASSERT( ! c.isZero(), "divide by zero!" );
+	termList quotlast, quotfirst = copyTermList( firstTerm, quotlast );
+	quotfirst = divTermList( quotfirst, c, quotlast );
+	if ( quotfirst )
+	    if ( quotfirst->exp == 0 ) {
+		quot = quotfirst->coeff.getval();
+		delete quotfirst;
+	    }
+	    else
+		quot = new InternalPoly( quotfirst, quotlast, var );
+	else
+	    quot = CFFactory::basic( 0 );
+	rem = CFFactory::basic( 0 );
+    }
+}
+
+bool
+InternalPoly::divremcoefft( InternalCF* cc, InternalCF*& quot, InternalCF*& rem, bool invert )
+{
+    if ( inExtension() && getReduce( var ) ) {
+	quot = copyObject();
+	quot = quot->dividecoeff( cc, invert );
+	rem = CFFactory::basic( 0 );
+	return true;
+    }
+    else  if ( invert ) {
+	if ( is_imm( cc ) )
+	    rem = cc;
+	else
+	    rem = cc->copyObject();
+	quot = CFFactory::basic( 0 );
+	return true;
+    }
+    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
+    ASSERT( ! c.isZero(), "divide by zero!" );
+    termList quotfirst, quotcursor;
+    termList cursor;
+    CanonicalForm cquot, crem;
+    bool divideok = true;
+
+    cursor = firstTerm;
+    quotcursor = quotfirst = new term;
+
+    while ( cursor && divideok ) {
+	divideok = ::divremt( cursor->coeff, c, cquot, crem );
+	divideok = divideok && crem.isZero();
+	if ( divideok ) {
+	    if ( ! cquot.isZero() ) {
+		quotcursor->next = new term( 0, cquot, cursor->exp );
+		quotcursor = quotcursor->next;
+	    }
+	    cursor = cursor->next;
+	}
+    }
+    quotcursor->next = 0;
+    if ( divideok ) {
+	cursor = quotfirst; quotfirst = quotfirst->next; delete cursor;
+	if ( quotfirst )
+	    if ( quotfirst->exp == 0 ) {
+		quot = quotfirst->coeff.getval();
+		delete quotfirst;
+	    }
+	    else
+		quot = new InternalPoly( quotfirst, quotcursor, var );
+	else
+	    quot = CFFactory::basic( 0 );
+	rem = CFFactory::basic( 0 );
+    }
+    else {
+	freeTermList( quotfirst );
+    }
+    return divideok;
+}
+
+// static functions
+
+termList
+InternalPoly::copyTermList ( termList aTermList, termList& theLastTerm, bool negate )
+{
+    if ( aTermList == 0 ) 
+	return 0;
+    else  if ( negate ) {
+	termList sourceCursor = aTermList;
+	termList dummy = new term;
+	termList targetCursor = dummy;
+
+	while ( sourceCursor ) {
+	    targetCursor->next = new term( 0, -sourceCursor->coeff, sourceCursor->exp );
+	    targetCursor = targetCursor->next;
+	    sourceCursor = sourceCursor->next;
+	}
+	targetCursor->next = 0;
+	theLastTerm = targetCursor;
+	targetCursor = dummy->next;
+	delete dummy;
+	return targetCursor;
+    }
+    else {
+	termList sourceCursor = aTermList;
+	termList dummy = new term;
+	termList targetCursor = dummy;
+
+	while ( sourceCursor ) {
+	    targetCursor->next = new term( 0, sourceCursor->coeff, sourceCursor->exp );
+	    targetCursor = targetCursor->next;
+	    sourceCursor = sourceCursor->next;
+	}
+	targetCursor->next = 0;
+	theLastTerm = targetCursor;
+	targetCursor = dummy->next;
+	delete dummy;
+	return targetCursor;
+    }
+}
+
+termList
+InternalPoly::deepCopyTermList ( termList aTermList, termList& theLastTerm )
+{
+    if ( aTermList == 0 ) 
+	return 0;
+    else {
+	termList sourceCursor = aTermList;
+	termList dummy = new term;
+	termList targetCursor = dummy;
+
+	while ( sourceCursor ) {
+	    targetCursor->next = new term( 0, sourceCursor->coeff.deepCopy(), sourceCursor->exp );
+	    targetCursor = targetCursor->next;
+	    sourceCursor = sourceCursor->next;
+	}
+	targetCursor->next = 0;
+	theLastTerm = targetCursor;
+	targetCursor = dummy->next;
+	delete dummy;
+	return targetCursor;
+    }
+}
+
+void
+InternalPoly::freeTermList ( termList aTermList )
+{
+    termList cursor = aTermList;
+
+    while ( cursor ) {
+	cursor = cursor->next;
+	delete aTermList;
+	aTermList = cursor;
+    }
+}
+
+void
+InternalPoly::negateTermList ( termList terms )
+{
+    termList cursor = terms;
+    while ( cursor ) {
+	cursor->coeff = -cursor->coeff;
+	cursor = cursor->next;
+    }
+}
+
+termList
+InternalPoly::addTermList ( termList theList, termList aList, termList& lastTerm, bool negate )
+{
+    termList theCursor = theList;
+    termList aCursor = aList;
+    termList predCursor = 0;
+
+    while ( theCursor && aCursor ) {
+	if ( theCursor->exp == aCursor->exp ) {
+	    if ( negate )
+		theCursor->coeff -= aCursor->coeff;
+	    else
+		theCursor->coeff += aCursor->coeff;
+	    if ( theCursor->coeff.isZero() ) {
+		if ( predCursor ) {
+		    predCursor->next = theCursor->next;
+		    delete theCursor;
+		    theCursor = predCursor->next;
+		}
+		else {
+		    theList = theList->next;
+		    delete theCursor;
+		    theCursor = theList;
+		}
+	    }
+	    else {
+		predCursor = theCursor;
+		theCursor = theCursor->next;
+	    }
+	    aCursor = aCursor->next;
+	}
+	else if ( theCursor->exp < aCursor->exp ) {
+	    if ( negate )
+		if ( predCursor ) {
+		    predCursor->next = new term( theCursor, -aCursor->coeff, aCursor->exp );
+		    predCursor = predCursor->next;
+		}
+		else {
+		    theList = new term( theCursor, -aCursor->coeff, aCursor->exp );
+		    predCursor = theList;
+		}
+	    else 
+		if ( predCursor ) {
+		    predCursor->next = new term( theCursor, aCursor->coeff, aCursor->exp );
+		    predCursor = predCursor->next;
+		}
+		else {
+		    theList = new term( theCursor, aCursor->coeff, aCursor->exp );
+		    predCursor = theList;
+		}
+	    aCursor = aCursor->next;
+	}	
+	else {
+	    predCursor = theCursor;
+	    theCursor = theCursor->next;
+	}
+    }
+    if ( aCursor ) {
+	if ( predCursor )
+	    predCursor->next = copyTermList( aCursor, lastTerm, negate );
+	else
+	    theList = copyTermList( aCursor, lastTerm, negate );
+    }
+    else if ( ! theCursor )
+	lastTerm = predCursor;
+
+    return theList;
+}
+
+void
+InternalPoly::mulTermList ( termList theCursor, const CanonicalForm& coeff, const int exp )
+{
+    while ( theCursor ) {
+	theCursor->coeff *= coeff;
+	theCursor->exp += exp;
+	theCursor = theCursor->next;
+    }
+}
+
+termList
+InternalPoly::divTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm )
+{
+    termList theCursor = firstTerm;
+    lastTerm = 0;
+    termList dummy;
+
+    while ( theCursor ) {
+	theCursor->coeff /= coeff;
+	if ( theCursor->coeff.isZero() ) {
+	    if ( theCursor == firstTerm )
+		firstTerm = theCursor->next;
+	    else
+		lastTerm->next = theCursor->next;
+	    dummy = theCursor;
+	    theCursor = theCursor->next;
+	    delete dummy;
+	}
+	else {
+	    lastTerm = theCursor;
+	    theCursor = theCursor->next;
+	}
+    }
+    return firstTerm;
+}
+
+termList
+InternalPoly::modTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm )
+{
+    termList theCursor = firstTerm;
+    lastTerm = 0;
+    termList dummy;
+
+    while ( theCursor ) {
+	theCursor->coeff.mod( coeff );
+	if ( theCursor->coeff.isZero() ) {
+	    if ( theCursor == firstTerm )
+		firstTerm = theCursor->next;
+	    else
+		lastTerm->next = theCursor->next;
+	    dummy = theCursor;
+	    theCursor = theCursor-> next;
+	    delete dummy;
+	}
+	else {
+	    lastTerm = theCursor;
+	    theCursor = theCursor->next;
+	}
+    }
+    return firstTerm;
+}
+
+void
+InternalPoly::appendTermList ( termList& first, termList& last, const CanonicalForm& coeff, const int exp )
+{
+    if ( last ) {
+	last->next = new term( 0, coeff, exp );
+	last = last->next;
+    }
+    else {
+	first = new term( 0, coeff, exp );
+	last = first;
+    }
+}
+
+termList
+InternalPoly::mulAddTermList ( termList theList, termList aList, const CanonicalForm & c, const int exp, termList & lastTerm, bool negate )
+{
+    termList theCursor = theList;
+    termList aCursor = aList;
+    termList predCursor = 0;
+    CanonicalForm coeff;
+
+    if ( negate )
+	coeff = -c;
+    else
+	coeff = c;
+
+    while ( theCursor && aCursor ) {
+	if ( theCursor->exp == aCursor->exp + exp ) {
+	    theCursor->coeff += aCursor->coeff * coeff;
+	    if ( theCursor->coeff.isZero() ) {
+		if ( predCursor ) {
+		    predCursor->next = theCursor->next;
+		    delete theCursor;
+		    theCursor = predCursor->next;
+		}
+		else {
+		    theList = theList->next;
+		    delete theCursor;
+		    theCursor = theList;
+		}
+	    }
+	    else {
+		predCursor = theCursor;
+		theCursor = theCursor->next;
+	    }
+	    aCursor = aCursor->next;
+	}
+	else if ( theCursor->exp < aCursor->exp + exp ) {
+	    if ( predCursor ) {
+		predCursor->next = new term( theCursor, aCursor->coeff * coeff, aCursor->exp + exp );
+		predCursor = predCursor->next;
+	    }
+	    else {
+		theList = new term( theCursor, aCursor->coeff * coeff, aCursor->exp + exp );
+		predCursor = theList;
+	    }
+	    aCursor = aCursor->next;
+	}
+	else {
+	    predCursor = theCursor;
+	    theCursor = theCursor->next;
+	}
+    }
+    if ( aCursor ) {
+	if ( predCursor ) {
+	    predCursor->next = copyTermList( aCursor, lastTerm );
+	    predCursor = predCursor->next;
+	}
+	else {
+	    theList = copyTermList( aCursor, lastTerm );
+	    predCursor = theList;
+	}
+	while ( predCursor ) {
+	    predCursor->exp += exp;
+	    predCursor->coeff *= coeff;
+	    predCursor = predCursor->next;
+	}
+    }
+    else if ( ! theCursor )
+	lastTerm = predCursor;
+    return theList;
+}
+
+termList
+InternalPoly::reduceTermList ( termList first, termList redterms, termList & last )
+{
+    CanonicalForm coeff = redterms->coeff;
+    CanonicalForm newcoeff;
+    int newexp;
+    int exp = redterms->exp;
+    termList dummy;
+    while ( first && ( first->exp >= exp ) ) {
+	newcoeff = first->coeff / coeff;
+	newexp = first->exp - exp;
+	dummy = first;
+	first = mulAddTermList( first->next, redterms->next, newcoeff, newexp, last, true );
+	delete dummy;
+    }
+    return first;
+}
