/* SYMMETRICA ff.c */
#include "def.h"
#include "macro.h"

#ifdef FFTRUE
/*
#define SYM_free(a) SYM_free_debug(a)
#define SYM_malloc(a) SYM_malloc_debug(a)
#define SYM_calloc(a,b) SYM_calloc_debug(a,b)
#define SYM_free(a)
*/

#define ALLOCOFFSET 0
/*
#define UE_malloc(a) SYM_malloc(a+ALLOCOFFSET)
*/
#define UE_malloc(a) SYM_malloc(a)

static INT init_ff();
static INT Charakteristik=(INT)0;
static INT UE_Erw_Grad=(INT)0;
static INT *UE_Platz_Mult=NULL;

#define Mult_Tafel_Speicher XYZ_ABC
static INT ***Mult_Tafel_Speicher = NULL;
static INT *Mult_Tafel_Grad = NULL;
static INT *Mult_Tafel_Charakteristik = NULL;
static INT **UE_Platz_Mult_Speicher = NULL;
static INT Mult_Tafel_Counter = (INT)0;


static INT **Mult_Tafel=NULL;
static FILE *Datei =NULL;     /* UWH */


static INT getString();
static INT UE_add();
static INT UE_fZeige();
static INT UE_invers();
static INT UE_ist_gleich();
static INT UE_ist_eins();
static INT UE_ist_null();
static INT UE_kgv();
static INT UE_mult();
static INT UE_negativ();
/* static INT UE_sqrt(); */
static INT UE_scan();
static INT UE_hoch();
/* static INT UE_prim(); */
static INT liestracepol();
static INT UE_Random();
static INT UE_order();
static INT UE_Int_Aequivalent();
static INT UE_Platz();
static INT UE_Free();
static INT minimalErw();
static int spezHoch();
static INT spezMult();
static INT spezEinsGGT();
static INT testirrPolynom();
static INT reduzierpoly();

#define UE_ADDG(a,b) (((a)+(b)) >= Charakteristik ?\
	((a)+(b))-Charakteristik: (a)+(b))
#define UE_MULTG(a,b) ((a) && (b) ? ((a)*(b)) % Charakteristik : (INT)0 )

/******************************************************************************/
/*      Endliche Koerper   :   Grundkoerperarithmetik                 */
/*                             */
/*                  Verfasser : Ulrich Eidt      */
/*                  Stand    : 04.11.91        */
/******************************************************************************/
static INT * s_ff_ip(a) OP a;
/* AK 180194 */ /* select .. int pointer */
{
	return s_o_s(s_v_i(a,(INT)1)).ob_INTpointer;
}

INT c_ff_ip(a,b) OP a; INT *b;
{
	OBJECTSELF c;
	c.ob_INTpointer = b;
	c_o_s(s_v_i(a,(INT)1) , c);
	return OK;
}

INT s_ff_ii(a,i) OP a; INT i;
{
	if (i > s_ff_di(a))
		error("s_ff_ii: index too big");
	return * (s_ff_ip(a)+i);
}


static INT UE_addg(a,b) INT a,b;
/* Summation : a,b sind die Summanden (Integerzahlen) */
{
	if (!b)
		return(a);
	if (!a)
		return(b);
	if (a+b>=Charakteristik)
		return(a+b-Charakteristik);
	return(a+b);
}

static INT UE_subg (a,b) INT a,b;/* Subtraktion : a,b sind Integerzahlen */
{
	if (!b)
		return(a);
	if (!a)
		return(Charakteristik-b);
	if (a>=b)
		return(a-b);
	return(Charakteristik+a-b);
}

static INT UE_multg(a,b) INT a,b;
/* Multiplikation : a,b sind Faktoren (Integerzahlen) */
{
	if (a && b)
		return((a*b) % Charakteristik);
	return((INT)0);
}


static INT UE_divg(a,b) INT a,b;/* Division : a,b sind Integerzahlen */
/* UE */
{
	INT j,i,s;
	if (!b)
	{
		error("UE_divg:zero-division ");
		return(ERROR);
	}
	if (!a || b==(INT)1)
		return(a);
	s = a;
	j = b;
	i = Charakteristik-2L;
	while(i>(INT)0)
	{
		while(!i % 2L)
		{
			i /= 2L;
			j =(j*j) % Charakteristik;
			if (j==(INT)1)
				return(s);
		}
		i--;
		s = (s*j) % Charakteristik;
	}
	return(s);
}


/******************************************************************************/
/* Gaussalgorithmen : Algorithmen fuer Gleichungssystemloesung            */
/*                                                         */
/*                                   Verfasser : Ulrich Eidt      */
/*                                   Stand    : 07.11.91        */
/******************************************************************************/

/******************************************************************************/
/* Funktion gausszerlegu fuehrt die Dreieckszerlegung PA = LR durch         */
/* Uebergabeparameter : Mat  : ist die Matrix                         */
/*                 n   : Dimension der Matrix                     */
/*                 P   : Platz fuer Permutationsvektor              */
/*                                                         */
/* Rueckgabeparameter : 0 falls Matrix singulaer                       */
/*                 1 falls Zerlegung erfolgreich durchgefuehrt         */
/*                                                         */
/* Bemerkungen : - Die Eintraege der Matrix Mat sind Zeile fuer Zeile von oben*/
/*              nach unten in Mat eingetragen.                     */
/*            - Die Funktionen add,sub,mult,div3 werden verwendet.        */
/*              Diese stehen in EndlArithmet.c                     */
/******************************************************************************/
static INT gausszerlegu(Mat,n,P) INT **Mat; INT n; INT *P;
{ 
	INT i,j,k=(INT)0,StellePermutation,Zwischenspeicher;

	for (k=(INT)0;k<n;k++)
	{

		/* Sollte ein Eintrag = 1 sein, dann sind wir optimal */
		/*  ansonsten nehmen wir den ersten Eintrag <> 0     */
		StellePermutation = -(INT)1;
		for (i=k;i<n;i++)
			if (Mat[i][k] == (INT)1)
			{
				StellePermutation = i;
				i = n+(INT)1;
			}
		if (StellePermutation < (INT)0)
			for (i=k;i<n;i++)
				if (Mat[i][k] > (INT)(INT)0)
				{
					StellePermutation = i;
					i = n+(INT)1;
				}

		/* Falls kein Eintrag <> 0 : Abbruch da Matrix singulaer */
		if (StellePermutation < (INT)0)
		{
			
			SYM_free((char *) Mat);
			error("ff.c: internal error FF45");
			return((INT)0);
		}

		/* Permutation speichern */
		P[k] = StellePermutation;

		/* Vertauschung falls notwendig */
		if (StellePermutation > k)
			for (j=(INT)0;j<n;j++)
			{
				Zwischenspeicher = Mat[k][j];
				Mat[k][j] = Mat[StellePermutation][j];
				Mat[StellePermutation][j] = Zwischenspeicher;
			}

		/* Berechnung von L */
		Zwischenspeicher = Mat[k][k];
		if (Zwischenspeicher != (INT)1)
		{
			Zwischenspeicher = UE_divg((INT)1,Zwischenspeicher);
			for (i=k+(INT)1;i<n;i++)
				Mat[i][k] = UE_MULTG(Mat[i][k],Zwischenspeicher);
		}

		/* Spaltenweise Berechnung der Untermatrix */
		for (j=k+(INT)1;j<n;j++)
		{
			Zwischenspeicher = Mat[k][j];
			for (i=k+(INT)1;i<n;i++)
				Mat[i][j] = UE_subg(Mat[i][j],UE_MULTG(Mat[i][k],                              Mat[k][j]));
		}
	}
	if (!Mat[n-1][n-1])
		{
		error("ff.c: internal error FF46");
		return((INT)0);
		}

	return((INT)1);
}



/******************************************************************************/
/* Funktion gaussaufloes berechnet die Loesung des Gleichungssystems :    */
/*                  LRx = Pb                                 */
/* Uebergabeparameter : Mat  : ist die Matrix mit den Informationen zu L und R*/
/*                 n   : Dimension der Matrix                  */
/*                 b   : rechte Seite des Permutationsvektors       */
/*                 P   : Permutationsvektor                     */
/*                                                         */
/* Bemerkungen : - Die Funktion ist ohne Rueckgabeparameter.            */
/*            - Der Vektor b enthaelt nach der Aktion das Ergebnis      */
/*         - Die Funktionen UE_addg,UE_subg,UE_multg,UE_divg werden verwendet. */
/******************************************************************************/
static INT gaussaufloes(Mat,n,b,P) INT **Mat, n, *b, *P;
{
	INT i,k=0,Zwischenspeicher;

	/* b := Pb */
	for (k=(INT)0;k<n-(INT)1;k++)
		if (k<P[k])
		{
			Zwischenspeicher = b[k];
			b[k] = b[P[k]];
			b[P[k]] = Zwischenspeicher;
		}

	/* b := L^-1b */
	for (k=(INT)0;k<n-(INT)1;k++)
		for (i=k+(INT)1;i<n;i++)
			b[i] = UE_subg(b[i],UE_MULTG(Mat[i][k],b[k]));

	/* b := R^-1b */
	for (k=n-(INT)1;k>=(INT)0;k--)
	{
		b[k] = UE_divg(b[k],Mat[k][k]);
		for (i=(INT)0;i<=k-(INT)1;i++)
			b[i] = UE_subg(b[i],UE_MULTG(Mat[i][k],b[k]));
	}
	return OK;
}


/******************************************************************************/
/* Funktion reduzierpoly fuehrt die Reduktion eines Polynoms modulo eines    */
/* anderen durch. Funktion nur fuer endliche Koerper verwendbar.           */
/*                                */
/* Bemerkungen : - Funktion ohne Rueckgabeparameter.              */
/*            - Polynome werden in Potenzaufsteigender Reihenfolge       */
/*              sortiert, beginnend bei 0. ZB. Pol = x^2 + x + 3  wird   */
/*              uebergeben als : Pol[0] = 3, Pol[1] = 1, Pol[3] = 1.     */
/*            - ReduzierPolynom wird als normiert vorrausgesetzt, dh. in   */
/*              der Funktion wird der Koeffizient der hoechsten Potenz   */
/*              automatisch als 1 angenommen.                      */
/*            - Polynom wird in der Funktion geaendert und enthaelt      */
/*              beim Abschluss der Funktion das reduzierte Polynom.      */
/*            - die Funktionen UE_multg,UE_addg,UE_subg werden verwendet.    */
/*                                */
/*               Autor : Ulrich Eidt           */
/*               Stand : 04.11.91           */
/******************************************************************************/
static INT reduzierpoly(Polynom,Grad,ReduzierPolynom,GradReduzierPol)

	INT *Polynom;       /* enthaelt das Polynom vor Reduktion       */
	INT Grad;          /* Grad des Polynoms vorher               */
	INT *ReduzierPolynom; /* Polynom nach dem reduziert wird         */
	INT GradReduzierPol;  /* Grad des Polynoms nach dem reduziert wird  */

{
	INT Polynomzeiger, i, Stelle, Faktor;

	/* falls Grad < GradReduzierPol ohne Aenderung zurueck   */
	if (Grad < GradReduzierPol)
	{
		return OK;
	}
	Polynomzeiger = Grad;

	/* Reduzieren, solange der Grad reduzierten Polynoms < Grad ReduzierPolynoms */
	while (Polynomzeiger >= GradReduzierPol)
	{
		Faktor = Polynom[Polynomzeiger];

		/* Reduzierung nur noetig, falls der Koeffizient <> 0         */
		if (Faktor)
		{
			Polynom[Polynomzeiger] = (INT)0;
			for (i=(INT)0;i<GradReduzierPol;i++)
			{
				Stelle = Polynomzeiger+i-GradReduzierPol;

				/* Hier findet die Reduktion statt   */
				Polynom[Stelle] = UE_subg(Polynom[Stelle],                                 UE_MULTG(Faktor,
				    ReduzierPolynom[i]));
			}
		}
		Polynomzeiger--;
	}
	return OK;
}


INT ff_ende()
/* AK 170393 */
{
	INT i;
	if (Mult_Tafel_Grad != NULL)
	{ 
	SYM_free((char *) Mult_Tafel_Grad); 
	Mult_Tafel_Grad=NULL; 
	}

	if (Mult_Tafel_Charakteristik != NULL)
	{ 
	SYM_free((char *) Mult_Tafel_Charakteristik); 
	Mult_Tafel_Charakteristik=NULL; 
	}

	if (Mult_Tafel_Speicher != NULL)
	{ 
	for (i=0;i<Mult_Tafel_Counter; i++)
		SYM_free((char*) Mult_Tafel_Speicher[i]);
	SYM_free((char *) Mult_Tafel_Speicher); 
	Mult_Tafel_Speicher=NULL; 
	}

	if (UE_Platz_Mult_Speicher != NULL)
	{ 
	for (i=0;i<Mult_Tafel_Counter; i++)
		SYM_free((char*) UE_Platz_Mult_Speicher[i]);
	SYM_free((char *) UE_Platz_Mult_Speicher); 
	UE_Platz_Mult_Speicher=NULL; 
	}

	Mult_Tafel=NULL;
	UE_Platz_Mult=NULL;
	return OK;
}

static INT insert_mt() /* AK 070294 */
/* fuegt in globalen speicher ein */
{
	Mult_Tafel_Counter++;
	if (Mult_Tafel_Counter > 1) {
	Mult_Tafel_Speicher = (INT ***) SYM_realloc(Mult_Tafel_Speicher, 
		sizeof(INT**)* Mult_Tafel_Counter);
	Mult_Tafel_Grad = (INT *) SYM_realloc(Mult_Tafel_Grad, 
		sizeof(INT)* Mult_Tafel_Counter);
	Mult_Tafel_Charakteristik = (INT *) SYM_realloc(Mult_Tafel_Charakteristik, 
		sizeof(INT)* Mult_Tafel_Counter);
	UE_Platz_Mult_Speicher = (INT **) SYM_realloc(UE_Platz_Mult_Speicher, 
		sizeof(INT*)* Mult_Tafel_Counter);
	}
	else {
	Mult_Tafel_Speicher = (INT ***) SYM_malloc( 
		sizeof(INT**)* Mult_Tafel_Counter);
	Mult_Tafel_Grad = (INT *) SYM_malloc( 
		sizeof(INT)* Mult_Tafel_Counter);
	Mult_Tafel_Charakteristik = (INT *) SYM_malloc( 
		sizeof(INT)* Mult_Tafel_Counter);
	UE_Platz_Mult_Speicher = (INT **) SYM_malloc( 
		sizeof(INT*)* Mult_Tafel_Counter);
	}
	Mult_Tafel_Speicher[Mult_Tafel_Counter-1] = Mult_Tafel;
	Mult_Tafel_Grad[Mult_Tafel_Counter-1] = UE_Erw_Grad;
	Mult_Tafel_Charakteristik[Mult_Tafel_Counter-1] = Charakteristik;
	UE_Platz_Mult_Speicher[Mult_Tafel_Counter-1] = UE_Platz_Mult;
	return OK;
}
 
/******************************************************************************/
/* Funktion erzmulttafel berechnet die Multiplikationstafel fuer die        */
/* Normalbasis.                                                */
/*                                                         */
/* Uebergabeparameter :                                          */
/*  - Erweiterungsgrad :  Gibt den gewuenschten Erweiterungsgrad an         */
/*  - zweitAufruf       :  1=Aufruf aus erzeugePol, 0 normaler Aufruf       */
/*                        -1=Aufruf aus erzeugePol mit Tracepolynombergabe */
/*  - Tracepolynom      :  Tracepolynom, falls bueergeben                    */
/*                                                         */
/* Rueckgabeparameter : 0 falls Tafel nicht erzeugt werden konnte.         */
/*                 1 sonst.                                   */
/*                                                         */
/* Bemerkungen:                                                */
/*            - Funktionen, die benutzt werden (also eingebunden sein     */
/*              muessen) :                                    */
/*               liestracepol    : aufgerufen von erzmulttafel()      */
/*                              zu finden in LiesTracePol.c        */
/*               reduzierpoly    : aufgerufen von erzmulttafel()      */
/*                              zu finden in ReduzierPoly.c        */
/*               gausszerlegu    : aufgerufen in erzmulttafel()       */
/*                              zu finden in GaussAlgorit.c        */
/*               gaussaufloes    : aufgerufen in erzmulttafel()       */
/*                              zu finden in GaussAlgorit.c        */
/*        UE_addg,UE_subg,UE_multg,UE_divg : aufgerufen von reduzierpoly(),      */
/*                              gausszerlegu()                 */
/*                              zu finden in EndlArithmet.c        */
/*                                                         */
/* Zur Implementierung:                                          */
/*  Zunaechst wird das Tracecompatible Polynom eingelesen, und falls dies    */
/*   erfolgreich war die noetigen Speicherbelegungen durchgefuehrt.         */
/*                                                         */
/*  Dann wird die Normalbasis in der Polynomialen Basis ermittelt und sowohl  */
/*   in Tafel als auch in Gaussmatrix abgespeichert. Dafuer wird immer in    */
/*   Grosspolynom das letzte Basiselement^Erweiterungsgrad (= Frobeniushomom.)*/
/*   eingelesen und nach Tracepolynom reduziert.                       */
/*                                                         */
/*  Mit Gausszerlegu() wird die Basistransformation (Gleichungssystem)      */
/*   Polynomialbasis -> Normalbasis ermoeglicht.                       */
/*                                                         */
/*  Diese Transformation wird auf die gewuenschten x - Potenzen in Polynomial-*/
/*   basis angewendet, die man erhaelt, indem die in Tafel abgespeicherten   */
/*   Polynome mit x multipliziert, und dann reduziert.                  */
/*                                                         */
/*                                 Autoer : Ulrich Eidt         */
/*                                 Stand  : 05.11.91            */
/******************************************************************************/
static INT erzmulttafel(Erweiterungsgrad,zweitAufruf,para_Tracepolynom)
	INT Erweiterungsgrad;
	INT zweitAufruf;   /* UWH */
/* 1 heisst ja, 0 heisst nein, -1 heisst
					ja mit bergabe von Tracepolynom */
	INT *para_Tracepolynom; /* UWH */
/* Tracecompatibles Polynom        */
{
	INT *Gaussmatrix;  /* Matrix fuer Basistransformation             */
	INT **Gau;       /* Zeigersystem fuer Gaussmatrix               */
	INT *Grosspolynom; /* Platz fuer Polynome mit Grad > Erweiterungsgrad */
	INT Grosspolzeiger;/* Hilfszeiger fuer Grosspolynom               */
	INT Gradgrosspol;  /* Gibt den Grad von Grosspolynom an            */
	INT *Tracepolynom; /* Tracecompatibles Polynom                  */
	INT *Permutation;  /* Permutationsvektor bei Gleichungssystemloesung  */
	INT i,j;         /* Laufvariable                          */
	INT *ax;
	int k;

	/* schaue ob schon von frueher da AK 070294 */
	for (i=0;i<Mult_Tafel_Counter; i++)
		{
		if ((Erweiterungsgrad == Mult_Tafel_Grad[i]) &&
		    (Charakteristik == Mult_Tafel_Charakteristik[i]))
			{
			Mult_Tafel = Mult_Tafel_Speicher [i];
			UE_Erw_Grad = Erweiterungsgrad;
			return OK;
			}
		}

	Mult_Tafel = NULL;
	
	/* also noch nicht frueher berechnet */

	if (UE_Erw_Grad && !zweitAufruf)  /* UWH */
		/* ->(f weg)  if (UE_kgv(UE_Erw_Grad,Erweiterungsgrad)<=100L) */ /* UWH */
		Erweiterungsgrad = UE_kgv(UE_Erw_Grad,Erweiterungsgrad);

	/* Tracecompatibles Polynom wird eingelesen, falls nicht moeglich Zurueck */
	/* falls moeglich Speicher freimachen                            */

	if (zweitAufruf>=0)    /* UWH */
	{                   /* UWH */
		Tracepolynom = (INT *) SYM_calloc(Erweiterungsgrad,sizeof(INT));
		if (liestracepol(Erweiterungsgrad,Tracepolynom,zweitAufruf) != OK) /* UWH */
		{
			SYM_free((char *) Tracepolynom);
			return error("ff.c: internal error FF-41");
			/* printf("Tracecompatibles Polynom nicht beschaffbar!\n"); */
		}                /* UWH */
	}
	else 
		Tracepolynom = para_Tracepolynom; /* AK 040294 */

	/* Bestehende Tafeln freimachen, falls nicht Aufruf aus erzeugePol */
#ifdef UNDEF
	if ( UE_Erw_Grad &&  !zweitAufruf) /* UWH */
	{
		if (Mult_Tafel != NULL)
			SYM_free((char *) Mult_Tafel);
		if (UE_Platz_Mult != NULL)
			SYM_free((char *) UE_Platz_Mult);
		Mult_Tafel=NULL;
		UE_Platz_Mult=NULL;
	}
#endif
	for (i=0;i<Mult_Tafel_Counter; i++)
		{
		if (Erweiterungsgrad == Mult_Tafel_Grad[i] &&
		    Charakteristik == Mult_Tafel_Charakteristik[i])
			{
			Mult_Tafel = Mult_Tafel_Speicher [i];
			UE_Erw_Grad = Erweiterungsgrad;
			if (zweitAufruf>=0)    /* UWH */
				SYM_free((char *) Tracepolynom);
			return OK;
			}
		}
	UE_Platz_Mult = (INT *) UE_malloc(Erweiterungsgrad*Erweiterungsgrad*
	    sizeof(INT));

	/* Abspeichern der jeweiligen Zeilenanfaenge der Matrix, um Multiplikationen */
	/*  bei der Addressierung zu vermeiden */
	Mult_Tafel = (INT **) UE_malloc(Erweiterungsgrad*sizeof(INT*));

	k=(INT)0;
	for (i=(INT)0;i<Erweiterungsgrad;i++)
	{
		Mult_Tafel[i] = & UE_Platz_Mult[k];
		k += Erweiterungsgrad;
	}
	

	if (Erweiterungsgrad == (INT)1)
	{
		if (zweitAufruf>=0)    /* UWH */
			SYM_free((char *) Tracepolynom);
		Mult_Tafel[0][0] = (INT)1;
		UE_Erw_Grad = (INT)1;
		insert_mt();
		return(OK);
	}

	Grosspolynom = (INT *) SYM_calloc(Erweiterungsgrad*Charakteristik,                          sizeof(INT));
	Gaussmatrix = (INT *) UE_malloc(Erweiterungsgrad*Erweiterungsgrad*                        sizeof(INT));
	Permutation = (INT *) UE_malloc(Erweiterungsgrad*sizeof(INT));

	/* Abspeichern der jeweiligen Zeilenanfaenge der Matrix, um Multiplikationen */
	/*  bei der Addressierung zu vermeiden */
	Gau = (INT **) UE_malloc(Erweiterungsgrad*sizeof(INT*));
	k=(INT)0; 
	ax = Gaussmatrix;
	for (i=(INT)0;i<Erweiterungsgrad;i++)
	{
		Gau[i] = ((INT *)Gaussmatrix) + (int)k;
		ax = Gaussmatrix;
		for (j=0;j<k;j++)
			ax = ax++;
		k += (int)Erweiterungsgrad;
	}

	/* Initialisierung der Gaussmatrix und Zwischenspeichern der Potenzen */
	for (i=(INT)0;i<Erweiterungsgrad;i++)
	{
		(Gau[i])[0] = (INT)0;
		Mult_Tafel[0][i] = (INT)0;
	}
	Gau[1][0] = (INT)1;
	Mult_Tafel[0][1] = (INT)1;
	for (i=(INT)1;i<Erweiterungsgrad;i++)
	{
		for (j=(INT)0;j<Erweiterungsgrad;j++)
			Grosspolynom[j] = (INT)0;
		Grosspolzeiger = (INT)0;
		for (j=(INT)0;j<Erweiterungsgrad;j++)
		{

			/* Grosspolynom = letztes Polynom ^ Charakteristik (Frobenius)*/
			if (Gau[j][i-1])
			{
				Grosspolynom[Grosspolzeiger] = Gau[j][i-1];
				Gradgrosspol = Grosspolzeiger;
			}
			Grosspolzeiger += Charakteristik;
		}

		/* Grosspolynom wird nach Tracepolynom reduziert und abgespeichert */
		reduzierpoly(Grosspolynom,Gradgrosspol,Tracepolynom,                      Erweiterungsgrad);
		for (j=(INT)0;j<Erweiterungsgrad;j++)
		{
			Gau[j][i] = Grosspolynom[j];
			Mult_Tafel[i][j] = Grosspolynom[j];
		}
	}

	/* Gaussdreieckszerlegung */
	if(!gausszerlegu(Gau,Erweiterungsgrad,Permutation))
	{
		error("ff.c: internal error FF6");
		SYM_free((char *) Gaussmatrix);
		SYM_free((char *) Grosspolynom);
		if (zweitAufruf>=0)    /* UWH */
			SYM_free((char *) Tracepolynom);
		SYM_free((char *) Permutation);
		SYM_free((char *) Gau);
		error("internal error FF200");
		return ERROR;
	}

	/* Berechnung der Tafeleintraege von x*x^(p^i) in der Normalbasis */
	for (i=(INT)0;i<Erweiterungsgrad;i++)
	{

		/* Grosspolynom wird belegt mit x*x^(p^i) in Polynomialbasis */
		Grosspolynom[0] = (INT)0;
		for (j=(INT)0;j<Erweiterungsgrad;j++)
			Grosspolynom[j+1] = Mult_Tafel[i][j];

		/* Grosspolynom wird reduziert und der Basiswechsel durchgefuehrt */
		reduzierpoly(Grosspolynom,Erweiterungsgrad,Tracepolynom,                   Erweiterungsgrad);
		gaussaufloes(Gau,Erweiterungsgrad,Grosspolynom,                     Permutation);

		/* Abschliessend wird das Ergebnis gespeichert */
		for (j=(INT)0;j<Erweiterungsgrad;j++)
			Mult_Tafel[i][j] = Grosspolynom[j];
	}

	/* Speicher wieder freigeben */
	SYM_free((char *) Gaussmatrix);
	SYM_free((char *) Grosspolynom);
	if (zweitAufruf>=0)    /* UWH */
		SYM_free((char *) Tracepolynom);
	SYM_free((char *) Permutation);
	SYM_free((char *) Gau);
	UE_Erw_Grad = Erweiterungsgrad;

	insert_mt();
	return OK;
}



/******************************************************************************/
/* Funktion UE_kgv berechnet das kleinste gemeinsame Vielfache von zwei       */
/*           Integerzahlen.                                    */
/******************************************************************************/
static INT UE_kgv(a,b) INT a,b;
{
	INT c,d;
	c = a;
	d = b;
	while(c && d)
	{
		c = c % d;
		if(c)
			d = d % c;
	}
	if(c)
		return(a*b/c);
	else
		return(a*b/d);
}



#ifdef UNDEF
/******************************************************************************/
/* Funktion UE_sqrt berechnet die abgerundete integer-Wurzel einer Integerzahl*/
/******************************************************************************/
static INT UE_sqrt(x) INT x;
{
	INT i;
	if (x==(INT)0)
		return((INT)0);
	for (i=(INT)1;i<x;i++)
		if (i*i > x)
			return(i-(INT)1);
	return((INT)1);
}

#endif

/******************************************************************************/
/* Funktion UE_power berechnet die y-te Potenz von x                      */
/******************************************************************************/
static INT UE_power(x,y) INT x,y;
{
	INT i, s = (INT)1;
	for (i=(INT)0;i<y;i++)
		s *= x;
	return(s);
}



#ifdef UNDEF
/******************************************************************************/
/* Funktion UE_prim prueft, ob p eine Primzahl ist.                       */
/* Rueckgabewert: 1, falls p Primzahl, 0 sonst.                        */
/******************************************************************************/
static INT UE_prim(p)
INT p;
{
	INT i, s;

	s = UE_sqrt(p);
	if (p < 2L)
		return((INT)0);
	if (p > 2 && ((p % 2L) == (INT)0))
		return((INT)0);
	else
	{
		for (i=3L;i<=s;i+=2L)
		{
			if ((p % i) == (INT)0)
				return((INT)0);
		}
	}
	return((INT)1);
}

#endif

/******************************************************************************/
/*                  FUNKTIONEN FUER ENDLICHE KOERPER                */
/* Die folgenden Funktionen stellen eine Arithmetik fuer endliche Koerper in  */
/* Normalbasenrepraesentation dar. Ein Koerperelement wird wie folgt        */
/* abgespeichert:                                              */
/*   e[0] enthaelt den Erweiterungsgrad, die weiteren <e[0]>     */
/*   Stellen die Eintraege des es bezueglich der entsprechenden       */
/*   Normalbasis.  e[0] = 0 ist gleichbedeutend mit 'nicht definiert'.  */
/*                                                         */
/*                  Verfasser : Ulrich Eidt      */
/*                  Stand    : 04.11.91        */
/******************************************************************************/

/******************************************************************************/
/* Funktion minimalErw stellt den Koerper mit dem kleinsten Erweiterungsgrad  */
/* fest, in dem ein e enthalten ist. Ist dieser kleiner als e[0]  */
/* so wird die Speicherung des ees auf den kleinsten moeglichen Erwei-  */
/* terungsgrad angepasst.                                        */
/* Ein e ist genau dann aus einem Unterkoerper, wenn fuer einen Teiler  */
/* m des Erweiterungsgrades sich die Eintraege immer nach m Eintraegen wieder-*/
/* holen.                                                    */
/******************************************************************************/
static INT minimalErw(e) INT **e;
{
	INT i,j,maximum=(*e)[0]/2L,Grad=(*e)[0],minGrad=(INT)0;
	INT erfolgreich;
	/* falls nicht definiert keine Aenderungen */
	if ((*e)[0] == (INT)0)
		return OK;
	/* Teiler suchen nur bis zum maximalen Teiler  */
	while(minGrad<=maximum)
	{
		minGrad++;
		/* Nur Teiler muessen ueberprueft werden */
		if (!(Grad % minGrad))
		{
			erfolgreich = (INT)1;
			for (i=minGrad;i<Grad;i+=minGrad)
				for (j=(INT)1;j<=minGrad;j++)
					if ((*e)[j] != (*e)[i+j])
					{
	/* Keine Wiederholung -> minGrad nicht der minimale Erweiterungsgrad */
						erfolgreich = (INT)0;
						j = minGrad+(INT)1;
						i = Grad;
					}
			if (erfolgreich)
			{
				**e = minGrad;
				return OK;
			}
		}
	}
	return OK;
}

INT s_ff_ci(a) OP a;
/* selct finite field characteristik */
{
	return S_V_II(a,(INT)0);
}

OP s_ff_c(a) OP a;
/* selct finite field characteristik */
{
	return S_V_I(a,(INT)0);
}

INT s_ff_di(a) OP a;
{
	return S_FF_II(a,(INT)0);
}


INT freeself_ff(a) OP a;
/* AK 100393 */
{
	OBJECTSELF d;
	INT erg = OK;
	UE_Free( & S_FF_IP(a));
	SYM_free(S_V_S(a));
	erg += SYMfreeall(S_V_L(a));
	d = S_O_S(a);
	SYM_free(d.ob_vector);
	C_O_K(a,EMPTY);
	ENDR("freeself_ff");
}

INT copy_ff(a,b) OP a,b;
/* AK 100393 */
{
	OBJECTSELF ma,mb;
	INT al,i;
	INT erg = OK;
	erg += m_il_v(2L,b);
	C_O_K(b,FF);
	erg += copy(S_FF_C(a),S_FF_C(b));
	ma = S_O_S(S_V_I(a,(INT)1));
	al =  *(S_O_S(S_V_I(a,(INT)1)).ob_INTpointer); 
	UE_Erw_Grad=al;
	mb.ob_INTpointer = (INT *) UE_malloc((al+1) * sizeof(INT)); 
	for (i=(INT)0;i<=al;i++)
		*(mb.ob_INTpointer+i) = *(ma.ob_INTpointer+i);
	C_O_S(S_V_I(b,(INT)1),mb); 
	ENDR("copy_ff");
}

INT scan_ff(a) OP a;
{
	OP b;
	INT erg = OK;
	b = callocobject();
	printeingabe("Enter the Characteristik of the finite field");
	erg += scan(INTEGER,b);
	Charakteristik = S_I_I(b);
	erg += init_ff(a); /* AK 160594 */
	erg += copy(b,S_FF_C(a));
	erg += UE_scan(& S_FF_IP(a));
	erg += SYMfreeall(b);
	ENDR("scan_ff");
}

/******************************************************************************/
/* Funktion UE_scan uebernimmt das Einlesen der Koerperelemente            */
/*                                                         */
/* Struktur : 0-te Stelle enthaelt den Grad der Koerpererweiterung         */
/*         Die darauffolgenden <Grad> Stellen enthalten das e      */
/******************************************************************************/
static INT UE_scan(Koerperzeiger) INT **Koerperzeiger;
{
	INT i,j=(INT)0,ZeichenZeiger = (INT)1,*Koerperelement;
	char *Zeichen;
	Koerperelement = *Koerperzeiger;
	Zeichen = (char *) SYM_calloc(500,sizeof(char));
	printeingabe("input of a finite field element");
	printeingabe("degree of extension");
	scanf("%ld",&i);
#ifdef UNDEF
	if (i<=(INT)0)
	{
		Koerperelement[0] = UE_Erw_Grad;
		for (i=(INT)1;i<=UE_Erw_Grad;i++)
			Koerperelement[i] = (INT)0;
		SYM_free(Zeichen); /* AK 051093 */
		return OK;
	}
	if (i>UE_Erw_Grad)
	{
		if (UE_Erw_Grad > 0)
#endif
			SYM_free((char *) Koerperelement);
		Koerperelement = (INT *) UE_malloc((i+1)*sizeof(INT));
		*Koerperzeiger = Koerperelement;
#ifdef UNDEF
	}
#endif
	for (j=(INT)0;j<=i;j++)
		Koerperelement[j] = (INT)0;
	fprintf(stderr,"input   of %ld entries, seperated by comma",i);
	fprintf(stderr,"\nmissing entries are 0\n");
	scanf("%s",Zeichen);
	j = (INT)1;
	ZeichenZeiger = (INT)0;
	while (j<=i)
	{
		/* 44 = 'Komma' */
		while (Zeichen[ZeichenZeiger]!=44 && Zeichen[ZeichenZeiger]!=0)
		{
			Koerperelement[j] = Koerperelement[j] * 10 +
			    Zeichen[ZeichenZeiger] - 48;
			ZeichenZeiger++;
		}
		ZeichenZeiger++;
		j++;
	}
	for (j=(INT)1;j<=i;j++)
		Koerperelement[j] %= Charakteristik;
	Koerperelement[0] = i;
	UE_Erw_Grad  = 0;
	minimalErw(Koerperzeiger);
	SYM_free(Zeichen); /* AK 051093 */
	return OK;
}



/******************************************************************************/
/* Funktion UE_Platz stellt ein undefiniertes Koerperelement bereit.         */
/******************************************************************************/
static INT UE_Platz(Koerperzeiger) INT **Koerperzeiger;
{
	if (UE_Erw_Grad < 0)
		{
		error("ff.c: internal error FF331");
		}
	*Koerperzeiger = (INT *) UE_malloc((UE_Erw_Grad+1)*sizeof(INT));
	(*Koerperzeiger)[0] = (INT)0;
	return OK;
}

static INT UE_Free(a) INT **a; /* AK 060294 */
{
	SYM_free(*a);
	*a = NULL;	
	return OK;
}



/******************************************************************************/
/* Funktion UE_Zeige gibt ein Koerperelement auf dem Bildschirm aus.        */
/******************************************************************************/
static INT UE_Zeige(Koerperzeiger) INT **Koerperzeiger;
{
	return UE_fZeige(stdout,Koerperzeiger);
}

/******************************************************************************/
/* Funktion UE_fZeige gibt ein Koerperelement auf f aus.                 */
/******************************************************************************/
static INT UE_fZeige(f,Koerperzeiger) INT **Koerperzeiger; FILE *f;
{
	INT i,*Koerperelement;
	if ((*Koerperzeiger)[0] == (INT)0)
	{
		return error("ff.c: internal error FF1");
	}
	/* minimalErw(Koerperzeiger); */
	Koerperelement = *Koerperzeiger;
	for (i=(INT)1;i<Koerperelement[0];i++)
		fprintf(f,"%ld,",Koerperelement[i]);
	fprintf(f,"%ld",Koerperelement[Koerperelement[0]]);
	return OK;
}


INT comp_ff(a,b) OP a,b;
{
	INT erg = OK;
	if ((S_O_K(a) != FF) || (S_O_K(b) != FF))
		{
		erg +=  WTT("comp_ff",a,b);
		goto endr_ende;
		}

	if (S_FF_CI(a) != S_FF_CI(b))
		{
		error("comp_ff:different characteristic");
		goto endr_ende;
		}
	return UE_ist_gleich(& S_FF_IP(a), & S_FF_IP(b));
	ENDR("comp_ff");
}

INT addinvers_apply_ff(a) OP a;
/* AK 160393 */
{
	OP b = callocobject();
	INT erg = OK;
	erg += copy(a,b);
	erg += addinvers(b,a);
	erg += SYMfreeall(b);
	ENDR("addinvers_apply_ff");
}

INT random_ff(b) OP b;
/* AK 170393 */
{
	INT erg = OK;
	if (Charakteristik == (INT)0) /* not yet set */
		Charakteristik = (INT)5;
	if( UE_Erw_Grad==(INT)0)
		UE_Erw_Grad=(INT)9;
	erg += init_ff(b);
	erg += UE_Random( & S_FF_IP(b));
	M_I_I(Charakteristik,S_FF_C(b));
	erg += erzmulttafel(UE_Erw_Grad,(INT)0,NULL); /* UWH */
	ENDR("random_ff");
}

INT random_char_ff(a,b) OP a,b;
/* AK 220294 */
{
	if (not primep(a))
		{
		return error("random_char_ff: no prime");
		}
	Charakteristik = S_I_I(a);
	return random_ff(b);
}


INT addinvers_ff(a,b) OP a,b;
{
	INT erg = OK;
	Charakteristik = S_FF_CI(a);
	erg += init_ff(b);
	erg += UE_negativ(& S_FF_IP(a), & S_FF_IP(b));
	erg += m_i_i(Charakteristik,S_FF_C(b));
	ENDR("addinvers_ff");
}

INT invers_ff(a,b) OP a,b;
{
	INT erg = OK;
	Charakteristik = S_FF_CI(a);
	erg += init_ff(b);
	erg += UE_invers(& S_FF_IP(a), & S_FF_IP(b));
	erg += m_i_i(Charakteristik,S_FF_C(b));
	ENDR("invers_ff");
}

INT mult_ff(a,b,c) OP a,b,c;
{
	INT erg = OK;
	if (S_FF_CI(a) != S_FF_CI(b))
		error("mult_ff:different characteristic");
	Charakteristik = S_FF_CI(a);
	erg += init_ff(c);
	UE_mult(& S_FF_IP(a), & S_FF_IP(b), & S_FF_IP(c) );
	M_I_I(Charakteristik,S_FF_C(c));
	ENDR("mult_ff");
}

INT nullp_ff(a) OP a;
{
	return UE_ist_null(& S_FF_IP(a));
}

INT einsp_ff(a) OP a;
{
	return UE_ist_eins(& S_FF_IP(a));
}

INT mult_apply_ff(a,b) OP a,b;
/* AK 170393 */
{
	OP c = callocobject();
	INT erg = OK;
	if (S_O_K(b) != FF) /* AK 230596 */
		cast_apply_ff(b);
	erg += copy(b,c);
	erg += mult(a,c,b);
	erg += SYMfreeall(c);
	return erg;
}

INT add_apply_ff(a,b) OP a,b;
/* AK 170393 */
{
	OP c = callocobject();
	INT erg = OK;
	erg += copy(b,c);
	erg += add(a,c,b);
	erg += SYMfreeall(c);
	ENDR("add_apply_ff");
}

INT add_ff(a,b,c) OP a,b,c;
{
	INT erg = OK;
	if (nullp(b))
		return copy(a,c);
	if (S_O_K(b) != FF) /* AK 230294 */
		cast_apply_ff(b);
	if ((S_O_K(a) != FF)   || (S_O_K(b) != FF))
		return WTT("add_ff",a,b);

	if (S_FF_CI(a) != S_FF_CI(b))
		error("add_ff:different characteristic");
	Charakteristik = S_FF_CI(a);
	erg += init_ff(c);
	erg += UE_add(& S_FF_IP(a), &S_FF_IP(b), &S_FF_IP(c));
	erg += m_i_i(Charakteristik,S_FF_C(c));

	if (s_ff_ii(c,(INT)1) > Charakteristik)
		error("add_ff:internal error 070295");
	ENDR("add_ff");
}

INT t_INTEGER_FF(a,b,c) OP a,b,c;
/* AK 070394 */
/* a is INTEGER b is INTEGER = Charakteristik c becomes FF */
{
	INT i,erg = OK;
	if ((S_O_K(b) != INTEGER) || (S_O_K(a) != INTEGER))
		{
		erg += WTT("t_INTEGER_FF",a,b);
		goto t_ende;
		}
	if (check_equal_3(a,b,c,t_INTEGER_FF,&erg) == EQUAL)
                goto t_ende;

	Charakteristik = S_I_I(b);
	i = S_I_I(a); 	
	while (i<(INT)0) i += Charakteristik; /* AK 070295 */
	erg += init_ff(c);
	erg += UE_Int_Aequivalent(i, &S_FF_IP(c));
	erg += m_i_i(Charakteristik,S_FF_C(c));
	
t_ende:
	ENDR("t_INTEGER_FF");
	
}

INT cast_apply_ff(a) OP a;
/* AK 230294 */
{
	INT erg = OK,i;
	switch (S_O_K(a)) {
		case INTEGER:
			i = S_I_I(a); 	
			erg += init_ff(a);
			erg += UE_Int_Aequivalent(i, &S_FF_IP(a));
			erg += m_i_i(Charakteristik,S_FF_C(a));
			break;
		default:
			printobjectkind(a);
			erg += error("cast_apply_ff: transfer not possible");
			break;
		}
	ENDR("cast_apply_ff");
}



/******************************************************************************/
/* Funktion UE_add belegt Ergebzeig mit seins+szwei               */
/******************************************************************************/
static INT UE_add(seins,szwei,Ergebzeig) INT **seins; INT **szwei, **Ergebzeig;
{
	INT i,j,k,*Summ1hilf,*Summ2hilf,*Summand_eins,*Summand_zwei,*Ergebnis;
	INT h1=(INT)0,h2=(INT)0;
	Summand_eins = *seins;
	Summand_zwei = *szwei;
	Ergebnis = *Ergebzeig;


	/* Falls der Grad einer der Summanden nicht Den Erweiterungsgrad teilt, */
	/* Wird eine Koerpererweiterung noetig */
	if (!UE_Erw_Grad ||
	    (UE_Erw_Grad % Summand_eins[0]+UE_Erw_Grad%Summand_zwei[0]))
	{
		minimalErw(seins);
		minimalErw(szwei);
	}
	if (!UE_Erw_Grad ||
	    (UE_Erw_Grad % Summand_eins[0]+UE_Erw_Grad%Summand_zwei[0]))
		{
		k = UE_kgv(Summand_eins[0],Summand_zwei[0]);
		if ( erzmulttafel(k,(INT)0,NULL) != OK)  /* UWH */
			{
			return error("ff.c:internal error FF70");
			}
		}

	/* ist der Grad einer der Summanden m nicht gleich dem aktuellen Grad, so */
	/* muss eine Einbettung vorgenommen werden, indem man die Koeffizienten   */
	/* (<aktueller Grad> / m)-mal wiederholt.                         */
	if (Summand_eins[0] != UE_Erw_Grad)
	{
		k=(INT)1;
		Summ1hilf = (INT *) UE_malloc((UE_Erw_Grad+1)*sizeof(INT));
		h1=(INT)1;
		for (i=(INT)0;i<UE_Erw_Grad/Summand_eins[0];i++)
			for (j=(INT)1;j<=Summand_eins[0];j++)
				{
				Summ1hilf[k++] = Summand_eins[j];
				}
	}
	else
		Summ1hilf = Summand_eins;

	if (Summand_zwei[0] != UE_Erw_Grad)
	{
		k=(INT)1;
		h2=(INT)1;
		Summ2hilf = (INT *) UE_malloc((UE_Erw_Grad+1)*sizeof(INT));
		for (i=(INT)0;i<UE_Erw_Grad/Summand_zwei[0];i++)
			for (j=(INT)1;j<=Summand_zwei[0];j++)
				Summ2hilf[k++] = Summand_zwei[j];
	}
	else
		Summ2hilf = Summand_zwei;

	/* Der Grad des Ergebniselementes muss korrekt sein */
	if (Ergebnis[0]!=UE_Erw_Grad)
	{
		SYM_free((char *) Ergebnis);

		Ergebnis = (INT *) UE_malloc((UE_Erw_Grad+1)*sizeof(INT));
		Ergebnis[0] = UE_Erw_Grad;
		*Ergebzeig = Ergebnis;
	}

	/* Addition */
	for (i=(INT)1;i<=UE_Erw_Grad;i++)
		Ergebnis[i] = UE_addg(Summ1hilf[i],Summ2hilf[i]);
	if (h1==(INT)1) /* AK 160393 */
		SYM_free(Summ1hilf);
	if (h2==(INT)1) /* AK 160393 */
		SYM_free(Summ2hilf);
	return OK;
}




/******************************************************************************/
/* Funktion UE_mult belegt Ergebzeig mit feins+Fakt2zeig              */
/******************************************************************************/
static INT UE_mult(feins,Fakt2zeig,Ergebzeig) INT **feins, **Fakt2zeig, **Ergebzeig;
{
	INT i,j,k,l,m,*Fakt1hilf,*Fakt2hilf,*Faktor_eins,*Faktor_zwei,*Ergebnis,zwisch;
	Faktor_eins = (INT *) UE_malloc(((*feins)[0]+1)*sizeof(INT));
	Faktor_eins[0] = (*feins)[0];
	for (i=(INT)1;i<=Faktor_eins[0];i++)
		Faktor_eins[i] = (*feins)[i];
	Faktor_zwei = (INT *) UE_malloc(((*Fakt2zeig)[0]+1)*sizeof(INT));
	Faktor_zwei[0] = (*Fakt2zeig)[0];
	for (i=(INT)1;i<=Faktor_zwei[0];i++)
		Faktor_zwei[i] = (*Fakt2zeig)[i];
	Ergebnis = *Ergebzeig;


	/* Falls der Grad einer der Faktoren nicht Den Erweiterungsgrad teilt, */
	/* Wird eine Koerpererweiterung noetig */
	if (Mult_Tafel == NULL)
		{
		erzmulttafel(UE_Erw_Grad,(INT)0,NULL); /* UWH */
		}
	if (!UE_Erw_Grad || (UE_Erw_Grad%Faktor_eins[0] + UE_Erw_Grad%Faktor_zwei[0]))
	{
		minimalErw(feins);
		minimalErw(Fakt2zeig);
	}
	if (!UE_Erw_Grad || (UE_Erw_Grad%Faktor_eins[0] + UE_Erw_Grad%Faktor_zwei[0]))
		if (erzmulttafel(UE_kgv(Faktor_eins[0],Faktor_zwei[0]),(INT)0,NULL) != OK) /* UWH */
		{
			return error("ff.c: internal error (FF3)");
		}

	/* ist der Grad einer der Faktoren m nicht gleich dem aktuellen Grad, so  */
	/* muss eine Einbettung vorgenommen werden, indem man die Koeffizienten   */
	/* (<aktueller Grad> / m)-mal wiederholt.                         */
	if (Faktor_eins[0] != UE_Erw_Grad)
	{
		k=(INT)1;
		Fakt1hilf = (INT *) UE_malloc((UE_Erw_Grad+1)*sizeof(INT));
		for (i=(INT)0;i<UE_Erw_Grad/Faktor_eins[0];i++)
			for (j=(INT)1;j<=Faktor_eins[0];j++)
				Fakt1hilf[k++] = Faktor_eins[j];
	}
	else
		Fakt1hilf = Faktor_eins;

	if (Faktor_zwei[0] != UE_Erw_Grad)
	{
		k=(INT)1;
		Fakt2hilf = (INT *) UE_malloc((UE_Erw_Grad+1)*sizeof(INT));
		for (i=(INT)0;i<UE_Erw_Grad/Faktor_zwei[0];i++)
			for (j=(INT)1;j<=Faktor_zwei[0];j++)
				Fakt2hilf[k++] = Faktor_zwei[j];
	}
	else
		Fakt2hilf = Faktor_zwei;

	/* der Grad des Ergebnisselementes muss korrekt sein */
	if (Ergebnis[0]!=UE_Erw_Grad)
	{
#ifdef UNDEF
		if (Ergebnis[0] != 0)
		{
#endif
			SYM_free((char *) Ergebnis);
#ifdef UNDEF
		}
#endif
		Ergebnis = (INT *) UE_malloc((UE_Erw_Grad+1)*sizeof(INT));
		Ergebnis[0] = UE_Erw_Grad;
		*Ergebzeig = Ergebnis;
	}

	/* Ergebniselement mit 0 vobelegen */
	for (i=(INT)1;i<=UE_Erw_Grad;i++)
		Ergebnis[i] = (INT)0;
	/* Multiplikation mittels Multiplikationstafel */
	for (i=(INT)1;i<=UE_Erw_Grad;i++)
	{
		if(Fakt1hilf[i])
		{
			l=(INT)0;
			for (j=UE_Erw_Grad-i+(INT)1;j<=UE_Erw_Grad-(INT)1;j++)
			{
				l++;
				if (Fakt2hilf[l])
				{
					zwisch=UE_MULTG(Fakt1hilf[i],Fakt2hilf[l]);
					m=(INT)0;
					for (k=UE_Erw_Grad-i+(INT)1;k<=UE_Erw_Grad-(INT)1;k++)
					{
	m++;
	if (Mult_Tafel[j][k])
		Ergebnis[m]=UE_ADDG(Ergebnis[m],UE_MULTG(zwisch,Mult_Tafel[j][k]));
					}
					for (k=(INT)0;k<=UE_Erw_Grad-i;k++)
					{
	m++;
	if (Mult_Tafel[j][k])
		Ergebnis[m] = UE_ADDG(Ergebnis[m],UE_MULTG(zwisch,Mult_Tafel[j][k]));
					}
				}
			}
			for (j=(INT)0;j<=UE_Erw_Grad-i;j++)
			{
				l++;
				if (Fakt2hilf[l])
				{
					zwisch = UE_MULTG(Fakt1hilf[i],Fakt2hilf[l]);
					m=(INT)0;
					for (k=UE_Erw_Grad-i+(INT)1;k<=UE_Erw_Grad-(INT)1;k++)
					{
	m++;
	if (Mult_Tafel[j][k])
		Ergebnis[m] = UE_ADDG(Ergebnis[m],UE_MULTG(zwisch,Mult_Tafel[j][k]));
					}
					for (k=(INT)0;k<=UE_Erw_Grad-i;k++)
					{
	m++;
	if (Mult_Tafel[j][k])
		Ergebnis[m] = UE_ADDG(Ergebnis[m],UE_MULTG(zwisch,Mult_Tafel[j][k]));
					}
				}
			}
		}
	}
	SYM_free ((char *) Faktor_eins);
	SYM_free ((char *) Faktor_zwei);
	if (Faktor_eins!=Fakt1hilf)
		SYM_free ((char *) Fakt1hilf);
	if (Faktor_zwei!=Fakt2hilf)
		SYM_free ((char *) Fakt2hilf);
	return OK;
}



/******************************************************************************/
/* Funktion UE_negativ belegt Ergebnis mit -e                  */
/******************************************************************************/
static INT UE_negativ(e,Ergebnis) INT **e,**Ergebnis;
{
	INT i;
	/* minimalErw(e); */
	/* 0 e */
	if ((*e)[0] == (INT)1 && (*e)[1] == (INT)0)
	{
		(*Ergebnis)[0] = (INT)1;
		(*Ergebnis)[1] = (INT)0;
		return OK;
	}
	/* Ergebniselement muss korrekte Erweiterung haben */
	if ((*Ergebnis)[0] < (*e)[0])
	{
		SYM_free((char*) (*Ergebnis));
		*Ergebnis = (INT *) UE_malloc(((*e)[0] +1)*sizeof(INT));
	}

	(*Ergebnis)[0] = (*e)[0];
	for (i=(INT)1;i<=(*e)[0];i++)
		if ((*e)[i])
			/* Negativbildung modulo Charakteristik */
			(*Ergebnis)[i] = Charakteristik-(*e)[i];
		else
			(*Ergebnis)[i] = (INT)0;
	return OK;
}


/******************************************************************************/
/* Funktion UE_hoch berechnet e^m und gibt das Ergebnis in Ergebzeig aus*/
/******************************************************************************/
static INT UE_hoch(e,m,Ergebnis) INT **e, m, **Ergebnis;
{
	INT *Elemhelp,i;
	/* minimalErw(e); AK 231296 */
	if ((*e)[0] == 1 && (*e)[1] == 0)
	{
		(*Ergebnis)[0] = (INT)1;
		(*Ergebnis)[1] = (INT)0;
		return OK;
	}

	/* falls Einselement */
	if ((*e)[0] == 1 && (*e)[1] == 1)
	{
		(*Ergebnis)[0] = (INT)1;
		(*Ergebnis)[1] = (INT)1;
		return OK;
	}

	/* Erzeugung eines Hilfselementes  */
	Elemhelp = (INT *) UE_malloc(((*e)[0] +(INT)1)*sizeof(INT));
	for (i=(INT)0;i<=(*e)[0];i++)
		Elemhelp[i] = (*e)[i];

	/* falls Ergebniselement nicht den benoetigten Erweiterungsgrad hat */
	if ((*Ergebnis)[0] < Elemhelp[0])
	{
		SYM_free((char*) (*Ergebnis));
		*Ergebnis = (INT *) UE_malloc(((*e)[0] +(INT)1)*sizeof(INT));
	}

	for (i=(INT)0;i<=(*e)[0];i++)
		(*Ergebnis)[i] = (*e)[i];
	i = m-(INT)1;
	while(i>(INT)0)
	{
		while(!(i % 2L))
		{
			i /= 2L;
			UE_mult(&Elemhelp,&Elemhelp,&Elemhelp);
		}
		i--;
		UE_mult(Ergebnis,&Elemhelp,Ergebnis);
	}
	SYM_free((char *) Elemhelp);
	return OK;
}



/******************************************************************************/
/* Funktion invers berechnet 1/e und gibt das Ergebnis in Ergebzeig aus.*/
/******************************************************************************/
static INT UE_invers(e,Ergebnis) INT **e,**Ergebnis;
{
	INT i;
	if ((*e)[0] == 1 && (*e)[1] == (INT)0)
	{
		printf("Division durch 0\n");
		(*Ergebnis)[0] = (INT)0;
		return OK;
	}

	/* 1/e = e^(Charakteristik^(Erweiterungsgrad des ees)-2L) */
	i = UE_power(Charakteristik,(*e)[0])-2L;
	UE_hoch(e,i,Ergebnis);
	return OK;
}



/******************************************************************************/
/* Funktion UE_ist_null testet, ob e = 0                        */
/* Rueckgabewert : 1 falls e = 0, 0 sonst                        */
/******************************************************************************/
static INT UE_ist_null(e) INT **e;
{
	if((*e)[0] == 1 && (*e)[1] == (INT)0) /* AK 270396 */
		return((INT)1);
	minimalErw(e);
	if((*e)[0] == 1 && (*e)[1] == (INT)0)
		return((INT)1);
	return((INT)0);
}

/******************************************************************************/
/* Funktion UE_ist_eins testet, ob e = 1                        */
/* Rueckgabewert : 1 falls e = 1, 0 sonst                        */
/******************************************************************************/
static INT UE_ist_eins(e) INT **e;
{
	minimalErw(e);
	if((*e)[0] == 1 && (*e)[1] == (INT)1)
		return((INT)1);
	return((INT)0);
}



/******************************************************************************/
/* Funktion Int_Aequivalent berechnet zu einer Integerzahl a das zugehoerige  */
/* Grundkoerperelement und belegt Ergebnis damit.                      */
/******************************************************************************/
static INT UE_Int_Aequivalent(a,Ergebnis) INT a; INT **Ergebnis;
{
	/* falls Ergebniselement nicht den benoetigten Erweiterungsgrad hat */
	if ((*Ergebnis)[0] < (INT)1)
	{
		SYM_free((char*) (*Ergebnis));
		*Ergebnis = (INT *) UE_malloc(2*sizeof(INT));
	}
	(*Ergebnis)[0] = (INT)1;
	(*Ergebnis)[1] = a % Charakteristik;
	return OK;
}




/******************************************************************************/
/* Funktion UE_ist_gleich vergleicht e_eins mit e_zwei               */
/* Rueckgabewert :  1  falls e_eins > e_zwei,                      */
/*             -1  falls e_eins < e_zwei,                      */
/*              0  falls e_eins = e_zwei.                      */
/******************************************************************************/
static INT UE_ist_gleich(e_eins,e_zwei) INT **e_eins, **e_zwei;
{
	INT i,j,k,*Elem1hilf,*Elem2hilf;
	INT gemein_grad;

	/* falls die ee verschiedene Erweiterungsgrade ueber dem Grundkoerper */
	/* haben, muessen sie in den gemeinsammen Erweiterungskoerper eingebettet   */
	/* werden.                                                  */
	if ((*e_eins)[0] != (*e_zwei)[0])
	{
		gemein_grad = UE_kgv((*e_eins)[0],(*e_zwei)[0]);
		if ((*e_eins)[0] != gemein_grad)
		{
			k=(INT)1;
			Elem1hilf = (INT *) UE_malloc((gemein_grad+1)*sizeof(INT));
			for (i=(INT)0;i<gemein_grad/(*e_eins)[0];i++)
				for (j=(INT)1;j<=(*e_eins)[0];j++)
					Elem1hilf[k++] = (*e_eins)[j];
		}
		else
			Elem1hilf = *e_eins;

		if ((*e_zwei)[0] != gemein_grad)
		{
			k=(INT)1;
			Elem2hilf = (INT *) UE_malloc((gemein_grad+1)*sizeof(INT));
			for (i=(INT)0;i<gemein_grad/(*e_zwei)[0];i++)
				for (j=(INT)1;j<=(*e_zwei)[0];j++)
					Elem2hilf[k++] = (*e_zwei)[j];
		}
		else
			Elem2hilf = *e_zwei;
	}
	else
	{
		Elem1hilf = *e_eins;
		Elem2hilf = *e_zwei;
		gemein_grad = (*e_eins)[0] ; /* AK 230395 */
	}

	/* Vergleich */
	k = (INT)0;
	for (i=(INT)1;i<=gemein_grad;i++)
		if (Elem1hilf[i] != Elem2hilf[i])
		{
			k = i;
			i = gemein_grad+(INT)1;
		}

	if (k > 0 && Elem1hilf[k] < Elem2hilf[k])
		k = (INT)-1;

	if (k > 0 && Elem1hilf[k] > Elem2hilf[k])
		k = (INT)1;

	/* Speicher, fallsbenoetigt freigeben */
	if (*e_eins!=Elem1hilf)
		SYM_free ((char *) Elem1hilf);
	if (*e_zwei!=Elem2hilf)
		SYM_free ((char *) Elem2hilf);

	return(k);
}



INT order_ff(a,b) OP a,b;
/* AK 170194 */
{
	INT erg = OK;
	if (a == b)
		return ERROR;
	CTO(FF,"order_ff",a);
	erg += erzmulttafel(UE_Erw_Grad,0,NULL); /* UWH */
	erg += m_i_i(UE_order(  & S_FF_IP(a) ), b);
	ENDR("order_ff");
}

/******************************************************************************/
/* Funktion UE_order berechnet das kleinste m mit e^m = 1              */
/* Rueckgabewert : die berechnete Ordnung.                           */
/******************************************************************************/
static INT UE_order(e) INT **e;
{
	INT maxord = UE_power(Charakteristik,(*e)[0])-(INT)1;
	INT maxteiler = maxord/2L;

	INT i,*Ergebnis;
	UE_Platz(&Ergebnis);
	for (i=(INT)1;i<=maxteiler;i++)
		if (!(maxord % i))
		{
			UE_hoch(e,i,&Ergebnis);
			if (UE_ist_eins(&Ergebnis))
				{
				SYM_free(Ergebnis);
				return i;
				}
		}
	UE_Free(&Ergebnis);
	return(maxord);
}



/******************************************************************************/
/* Funktion UE_Random erzeugt ein zufaelliges e im Koerper des aktuellen*/
/* Grades.                                                   */
/******************************************************************************/
static INT UE_Random(e) INT **e;
{
	INT i;
	/* Der Erweiterungsgrad des ees muss mit dem aktuellen uebereinstimmen */
#ifdef UNDEF
	if ((*e)[0] != UE_Erw_Grad)
	{
#endif
		SYM_free(*e); /* AK 170393 */
		*e = (INT *) UE_malloc((UE_Erw_Grad+1)*sizeof(INT));
		(*e)[0] = UE_Erw_Grad;
#ifdef UNDEF
	}
#endif
	/* Zufallserzeugung */
	for (i=(INT)1;i<=UE_Erw_Grad;i++)
		(*e)[i] = rand() % Charakteristik;
	minimalErw(e);
	return OK;
}


#ifdef UNDEF
UE_main()
{
	INT u=1,i,j=0,*test,*test_eins,*test_zwei;
	UE_Erw_Grad = (INT)0;
	do {
		printf("Geben sie die gewuenschte Charakteristik ein ");
		scanf("%d",&Charakteristik); 
		fflush(stdout);
		j = UE_prim(Charakteristik);
		if (!j)
			printf("\n   Dies ist keine Primzahl!\n");
	} while (!j);
	while(u)
	{
		UE_Platz(&test);
		UE_scan(&test);
		printf("\n");
		UE_Platz(&test_eins);
		UE_scan(&test_eins);
		printf("\n");
		UE_Platz(&test_zwei);
		UE_add(&test,&test_eins,&test_zwei);
		UE_Zeige(&test);
		printf(" + \n");
		UE_Zeige(&test_eins);
		printf(" = \n");
		UE_Zeige(&test_zwei);
		if (UE_ist_null(&test_zwei))
			printf("ist Null\n");
		if (UE_ist_eins(&test_zwei))
			printf("ist Eins\n");
		printf("\n\n");
		UE_mult(&test,&test_eins,&test_zwei);
		UE_Zeige(&test);
		printf(" * \n");
		UE_Zeige(&test_eins);
		printf(" = \n");
		UE_Zeige(&test_zwei);
		if (UE_ist_null(&test_zwei))
			printf("ist Null\n");
		if (UE_ist_eins(&test_zwei))
			printf("ist Eins\n");
		printf("\n\n");
		UE_invers(&test_zwei,&test_eins);
		printf("1/ ");
		UE_Zeige(&test_zwei);
		printf(" = ");
		UE_Zeige(&test_eins);
		if (UE_ist_null(&test_eins))
			printf("ist Null\n");
		if (UE_ist_eins(&test_eins))
			printf("ist Eins\n");
		printf("\n\n");
		UE_negativ(&test_zwei,&test_eins);
		printf("0- ");
		UE_Zeige(&test_zwei);
		printf(" = ");
		UE_Zeige(&test_eins);
		if (UE_ist_null(&test_eins))
			printf("ist Null\n");
		if (UE_ist_eins(&test_eins))
			printf("ist Eins\n");
		UE_Free(&test);
		UE_Free(&test_eins);
		UE_Free(&test_zwei);
		printf("Momentane Koerpererweiterung: %d\n",UE_Erw_Grad);
		printf("Ende = 1   Weiter = 2   neuer Grad und weiter = 3 ");
		scanf("%d",&i);
		if (i==1)
			u=(INT)0;
		if (i==3)
		{
			printf("Grad :");
			scanf("%ld",&UE_Erw_Grad);
			erzmulttafel(UE_Erw_Grad,0,NULL); /* UWH */
		}
	}
}
#endif /* UNDEF */

static INT init_ff(a) OP a;
{
	INT erg = OK;
	erg += m_il_v(2L,a);
	C_O_K(a,FINITEFIELD);
	erg += UE_Platz(&S_FF_IP(a));
	return erg;
}


INT debugprint_ff(a) OP a;
/* AK 160393 */
{
	INT i;
	INT *iv;
	for (i=(INT)0;i<doffset;i++) fputc(' ',stderr);
	fprintf(stderr,"ff:Charakteristik =\n");
	doffset += 2L;
	debugprint(s_v_i(a,(INT)0));
	doffset -= 2L;
	iv = S_O_S(S_V_I(a,(INT)1)).ob_INTpointer;
	for (i=(INT)0;i<doffset;i++) fputc(' ',stderr);
	fprintf(stderr,"ff:INT vektor =\n");
	for (i=(INT)0;i<doffset;i++) fputc(' ',stderr);
	for (i=(INT)0;i<= *iv;i++)
		fprintf(stderr,"%ld ",*(iv+i));
	fprintf(stderr,"\n");
	return OK;
}



INT fprint_ff(f,a) OP a; FILE *f;
/* AK 180194 *//* AK 260594 */
{
	INT erg = OK;
	fprintf(f,"[");
	erg += UE_fZeige(f,& S_FF_IP(a));
	fprintf(f,"]");
	if (f == stdout)
	if (zeilenposition > (INT)70)
		{
		fprintf(stdout,"\n"); 
		zeilenposition = (INT)0;
		}
	return erg;
}

INT m_vector_ff(a,b,c) OP a,b,c;
/* AK 170194 */ /* a Charakteristik, b INTEGERVECTOR */
{
	INT erg = OK;
	INT i;
	INT *bi;

        if (check_equal_3(a,b,c,m_vector_ff,&erg) == EQUAL)
                goto mve;

	if (S_O_K(a) != INTEGER)
		return WTT("m_vector_ff",a,b);
	if (not VECTORP(b))
		return WTT("m_vector_ff",a,b);

	Charakteristik = S_I_I(a);
	UE_Erw_Grad = S_V_LI(b);
	erg += m_il_v(2L,c);
	C_O_K(c,FINITEFIELD);
	erg += UE_Platz(&S_FF_IP(c));
	bi = S_FF_IP(c);
	*bi = S_V_LI(b);
	for (i=(INT)0;i<S_V_LI(b);i++)
		*(bi+i+1) = S_V_II(b,i);

	erg += m_i_i(Charakteristik,S_V_I(c,(INT)0));
	erg += erzmulttafel(UE_Erw_Grad,0,NULL); /* UWH */
mve:
	ENDR("m_vector_ff");
}

INT m_ff_vector(a,b) OP a,b;
/* AK 230395 */
{
	INT erg = OK;
	INT i;

        if (check_equal_2(a,b,m_ff_vector,&erg) == EQUAL)
                return erg;

	CTO(FINITEFIELD,"m_ff_vector",a);
	erg += m_il_v(S_FF_DI(a),b);
	for (i=0;i<S_V_LI(b);i++)
		M_I_I(S_FF_II(a,i+1),S_V_I(b,i));
	C_O_K(b,INTEGERVECTOR);
	ENDR("m_ff_vector");
}

INT first_ff(a,b,c) OP a,b,c;
/* AK 170194 a Charakteristik, b Grad der Erweiterung */
{
	OP d;
	INT erg = OK;
	d = callocobject();
	if (S_O_K(a) != INTEGER)
		return WTT("first_ff",a,b);
	erg += m_il_nv(S_I_I(b),d);
	erg += m_vector_ff(a,d,c);
	erg += SYMfreeall(d);
	ENDR("first_ff");
}

INT next_ff(a,b) OP a,b;
{
	INT i,*ai,l;
	INT erg = OK;
	if (a == b)
		return ERROR;
	CTO(FF,"next_ff",a);
	Charakteristik = S_V_II(a,(INT)0);
	copy(a,b);
	ai = S_O_S(S_V_I(b,(INT)1)).ob_INTpointer;
	UE_Erw_Grad = *ai;
	l = *ai;
	for (i=l;i>0;i--)
		if ( *(ai+i) < (Charakteristik-1) )
		{
			*(ai+i) = *(ai+i) + (INT)1;
			for (i++;i<=l;i++)
			{
				*(ai+i) = (INT)0;
			}
			return OK;
		}
	if (i == 0)
		return LAST_FF;
	erg = ERROR;
	ENDR("next_ff");
}

/****************************************************************************/
/* Funktion einfuegTrace fuegt ein neu berechnetes Polynom in die           */
/*          entsprechende Datei ein.                                        */
/* bergabeparameter   Grad           Erweiterungsgrad der Datei            */
/*                     tracePolynom   einzutragendes Polynom                */
/****************************************************************************/
void einfuegTrace(Grad,tracePolynom) INT Grad; INT *tracePolynom;
{
	INT j;
	INT i;
	INT Laenge;
	char Zeichenkette[50];
	/* "G<GRAD>:" */
	Laenge = getString(Grad,Zeichenkette);
	fseek(Datei,0,2);
	putc('G',Datei);
	for (i=0;i<Laenge;i++)
		putc(Zeichenkette[i],Datei);
	putc(':',Datei);

	/* Polynomkoeffizienten  */
	for (j=0;j<Grad;j++)
	{
		Laenge = getString(tracePolynom[j],Zeichenkette);
		for (i=0;i<Laenge;i++)
			putc(Zeichenkette[i],Datei);
		putc(' ',Datei);
	}
	putc('\n',Datei);
	return;
}




/****************************************************************************/
/* Funktion spezGrad ermittelt den Grad von Polynom                         */
/*                                                                          */
/* Uebergabeparameter : Polynom,Grad                                         */
/*                                                                          */
/* Rueckgabeparameter Grad des Polynoms                                      */
/****************************************************************************/
static INT spezGrad(Polynom,Grad) INT *Polynom; INT Grad;
{
	INT i;
	for (i=Grad;i>=0;i--)
		{
		if (Polynom[i])
			{
			return(i);
			}
		}
	return(-1);
}




/****************************************************************************/
/* Funktion spezNormiert normiert Polynom                                   */
/* bergabeparameter : Polynom, NormalPolynom,Grad                          */
/****************************************************************************/
static INT *spezNormiert(Polynom,Grad) INT *Polynom; INT Grad;
{
	INT i;
	INT maxGrad = spezGrad(Polynom,Grad);
	INT Faktor = Polynom[maxGrad];
	if (Faktor==1)
		return(Polynom);
	Faktor = UE_divg(1,Faktor);
	for (i=maxGrad;i>=0;i--)
		Polynom[i] = UE_multg(Polynom[i],Faktor);
	return(Polynom);
}



/***************************************************************************/
/* Funktion spezEinsGGT berprft, ob GGT(Pol1,Pol2) = 1                   */
/* bergabeparameter Pol1, Pol2, Grad = Grad der Polynome                  */
/* Rckgabewert : 1, falls GGT = 1, 0 sonst                                */
/***************************************************************************/
static INT spezEinsGGT(Pol1,Pol2,Grad) INT *Pol1; INT *Pol2; INT Grad;
{
	INT i;
	INT *hilf1pol;
	INT *hilf2pol;
	if (!(hilf1pol = (INT *) UE_malloc((Grad+1)*sizeof(INT))))
		return no_memory();

	if (!(hilf2pol = (INT *) UE_malloc((Grad+1)*sizeof(INT))))
	{
		SYM_free((char *) hilf1pol);
		return no_memory();
	}
	for (i=0;i<=Grad;i++)
	{
		hilf1pol[i] = Pol1[i];
		hilf2pol[i] = Pol2[i];
	}
	while (spezGrad(hilf1pol,Grad)>=0 && spezGrad(hilf2pol,Grad)>=0)
	{
		reduzierpoly(hilf1pol,spezGrad(hilf1pol,Grad),spezNormiert(hilf2pol,Grad),spezGrad(hilf2pol,Grad));
		if(spezGrad(hilf1pol,Grad)>=0)
			reduzierpoly(hilf2pol,spezGrad(hilf2pol,Grad),spezNormiert(hilf1pol,Grad),spezGrad(hilf1pol,Grad));
	}

	/* Grad = 0 bedeutet von 0 verschiedenes Grundkoerperelement */
	if (spezGrad(hilf1pol,Grad)==0)
	{
		SYM_free((char *) hilf1pol);
		SYM_free((char *) hilf2pol);
		return (INT)1;
	}

	/* hilf1pol = 0  und hilf2pol von 0 verschiedenes Grundkorperelement */
	if (spezGrad(hilf1pol,Grad)<0)
		if (spezGrad(hilf2pol,Grad)==0)
		{
			SYM_free((char *) hilf1pol);
			SYM_free((char *) hilf2pol);
			return (INT) 1;
		}

	SYM_free((char *) hilf1pol);
	SYM_free((char *) hilf2pol);
	return(INT)0;
}



/****************************************************************************/
/* Funktion spezMult Multiplikation zweier Koerperelemente Modulo           */
/*                   NormalPolynom                                          */
/* bergabeparameter : Faktor1, Faktor2, Ergebnis, NormalPolynom, Grad      */
/*                                                                          */
/* Rckgabeparameter 1, falls ohne Probleme durchgefuehrt, 0 sonst.         */
/****************************************************************************/
static INT spezMult(Faktor1,Faktor2,Ergebnis,NormalPolynom,Grad)
	INT *Faktor1;
	INT *Faktor2;
	INT *Ergebnis;
	INT *NormalPolynom;
	INT Grad;
{
	INT i;
	INT j;
	INT ergebnisGrad=0;
	INT *zwischenErgebnis;
	zwischenErgebnis = (INT *) SYM_calloc(Grad+Grad,sizeof(INT));

	for (i=0;i<Grad;i++)
		for(j=0;j<Grad;j++)
			if(Faktor1[i] && Faktor2[j])
			{
				if (ergebnisGrad < i+j)
					ergebnisGrad = i+j;
				zwischenErgebnis[i+j] = UE_addg(zwischenErgebnis[i+j],
							UE_multg(Faktor1[i],Faktor2[j]));
			}

	reduzierpoly(zwischenErgebnis,ergebnisGrad,NormalPolynom,Grad);

	for (i=0;i<Grad;i++)
		Ergebnis[i] = zwischenErgebnis[i];

	SYM_free((char *) zwischenErgebnis);
	return(1);
}

/*******************************************************************************/ 
/* Funktion spezHoch berechnet Element^m und gibt das Ergebnis in Ergebzeig aus*/ 
/*******************************************************************************/ 
static int spezHoch(Element,m,Ergebnis,NormalPolynom,Grad) INT *Element;
	INT m;
	INT *Ergebnis;
	INT *NormalPolynom;
	INT Grad;
{
	INT *Elemhelp,i;

	/* Erzeugung eines Hilfselementes  */
	if(!(Elemhelp = (INT *) UE_malloc(Grad*sizeof(INT))))
	{
		return(0);
	}
	for (i=0;i<Grad;i++)
		Elemhelp[i] = Element[i];

	for (i=0;i<Grad;i++)
		Ergebnis[i] = Element[i];

	i = m-1;
	while(i>0)
	{
		while(!(i % 2))
		{
			i /= 2;
			spezMult(Elemhelp,Elemhelp,Elemhelp,NormalPolynom,Grad);
		}
		i--;
		spezMult(Ergebnis,Elemhelp,Ergebnis,NormalPolynom,Grad);
	}
	SYM_free((char *) Elemhelp);
	return(1);
}

/****************************************************************************/
/* Funktion triang bildet Dreiecksmatrix von Matrix                         */
/****************************************************************************/
static void triang(Matrix,Deg) INT **Matrix; INT Deg;

{
	INT i,j,k,l,pp,u;
	for(i=0;i<Deg;i++)
	{
		j=i;
		while((!(Matrix[i])[j]) && (j<Deg-1))
			j++;
		if(!(Matrix[i])[j])
		{
			j=0;
			while((j<i) && ((!(Matrix[i])[j]) || (Matrix[j][j])))
				j++;
		}
		if (Matrix[i][j])
		{
			u = UE_divg(1,Matrix[i][j]);
			for(k=i;k<Deg;k++)
				Matrix[k][j] = UE_multg(Matrix[k][j],u);
			for(k=0;k<Deg;k++)
				if (k!=j)
				{
					u = UE_subg(0,Matrix[i][k]);
					if (Matrix[i][k])
						for(l=i;l<Deg;l++)
						{
							Matrix[l][k] = UE_addg(Matrix[l][k],UE_multg(u,Matrix[l][j]));
						}
				}
			if (i!=j)
				for(k=i;k<Deg;k++)
				{
					pp = Matrix[k][i];
					Matrix[k][i] = Matrix[k][j];
					Matrix[k][j] = pp;
				}
		}
	}
}




/****************************************************************************/
/* Funktion testirrPolynom testet, ob Polynom irreduzibel ist.              */
/* Uebergabeparameter NormaltestPolynom,Grad                          */
/*        Rueckgabewert   1, falls NormaltestPolynom irreduzibel, 0 sonst    */
/****************************************************************************/
static INT testirrPolynom(NormaltestPolynom,Grad)
	INT *NormaltestPolynom;
	INT Grad;
{
	INT i;
	INT j;
	INT *Ableitung,*hf,*x,*q_mat;
	INT **Matrix;
	Ableitung = (INT *) SYM_calloc(Grad+1,sizeof(INT));
	/* Bildung der Ableitung */
	for(i=0;i<Grad-1;i++)
		Ableitung[i] = UE_multg(NormaltestPolynom[i+1],i+1);
	Ableitung[Grad-1] = Grad % Charakteristik;

	for(i=0;i<Grad;i++)
		if(Ableitung[i] != 0)
			i = Grad + 1;
	/* Alle EINTraege = 0 -> Ableitung = 0   -> nicht irreduzibel */
	if (i == Grad)
	{
		SYM_free((char *) Ableitung);
		return(0);
	}

	if (!spezEinsGGT(NormaltestPolynom,Ableitung,Grad))
	{
		SYM_free((char *) Ableitung);
		return(0);
	}

	hf = (INT *) SYM_calloc(Grad,sizeof(INT));
	q_mat = (INT *) SYM_calloc(Grad*Grad,sizeof(INT));
	x = (INT *) SYM_calloc(Grad*2,sizeof(INT));
	Matrix = (INT **) SYM_calloc(Grad,sizeof (INT *));
	
	i=0;
	for (j=0;j<Grad;j++)
	{
		Matrix[j]=q_mat+(j*Grad);
	}

	(Matrix[0])[0] = 1;
	x[1] = 1;
	spezHoch(x,Charakteristik,x,NormaltestPolynom,Grad);
	for(i=1;i<Grad;i++)
	{
		for(j=0;j<Grad;j++)
		{
			hf[j] = (Matrix[i-1])[j];
		}
		spezMult(hf,x,hf,NormaltestPolynom,Grad);
		for(j=0;j<Grad;j++)
			{
			(Matrix[i])[j] = hf[j];
			}
	}
	for(i=0;i<Grad;i++)
		(Matrix[i])[i]=UE_subg((Matrix[i])[i],1);
	triang(Matrix,Grad);
	j=0;
	for(i=0;i<Grad;i++)
		if ((Matrix[i])[i]==1)
			j++;
	SYM_free((char *) hf);
	SYM_free((char *) x);
	SYM_free((char *) q_mat);
	SYM_free((char *) Matrix);
	SYM_free((char *) Ableitung);
	if(j==(Grad-1))
		return(1);
	return(0);
}





/****************************************************************************/
/* Funktion testNormalPol berprft, ob Polynom NormalPolynom ist.          */
/*                                                                          */
/* bergabeparameter : NormalPolynom, Grad                                  */
/*                                                                          */
/* Rckgabeparameter : 1, falls Normalpolynom, 0 sonst                      */
/****************************************************************************/
static INT testNormalPol(NormaltestPolynom,Grad)
	INT *NormaltestPolynom;
	INT Grad;
{
	INT i;
	INT j;
	INT *Permutation;
	INT *NormalPolynom;
	INT *a_Hoch_q;
	INT **Pol1;

	if(!(NormalPolynom = (INT *) UE_malloc(Grad*sizeof(INT))))
	{
		return no_memory();
	}

	for (i=0;i<Grad;i++)
		NormalPolynom[i] = NormaltestPolynom[i];

	if(!(Permutation = (INT *) UE_malloc(Grad*sizeof(INT))))
	{
		SYM_free((char *) NormalPolynom);
		return no_memory();
	}

	if(!(Pol1 = (INT **) UE_malloc((Grad+1)*sizeof(INT*))))
	{
		SYM_free((char *) NormalPolynom);
		SYM_free((char *) Permutation);
		return(0);
	}

	if(!(a_Hoch_q = (INT *) SYM_calloc(Charakteristik+1,sizeof(INT))))
	{
		SYM_free((char *) NormalPolynom);
		SYM_free((char *) Permutation);
		SYM_free((char *) Pol1);
		return(0);
	}

	/* Belegung von ax^(m-1)+a^qx^(m-2)+...a^(q^(m-1)) */
	for (i=0;i<=Grad;i++)
		if(!(Pol1[i] = (INT *) SYM_calloc(Grad,sizeof(INT))))
		{
			SYM_free ((char *) a_Hoch_q);
			SYM_free((char *) NormalPolynom);
			SYM_free((char *) Permutation);
			for (j=i-1;i>=0;j--)
				SYM_free((char *) Pol1[j]);
			SYM_free((char *) Pol1);
			return(0);
		}

	Pol1[Grad-1][1] = 1; /* a */

	a_Hoch_q[Charakteristik] = 1;
	reduzierpoly(a_Hoch_q,Charakteristik,NormalPolynom,Grad);
	for (i=0;i<Grad && i<=Charakteristik;i++)
		Pol1[Grad-2][i] = a_Hoch_q[i];
	SYM_free ((char *) a_Hoch_q);

	for (i=Grad-3;i>=0;i--)
		spezHoch(Pol1[i+1],Charakteristik,Pol1[i],NormalPolynom,Grad);

	if (!gausszerlegu(Pol1,Grad,Permutation))
	{
		for (i=0;i<=Grad;i++)
			SYM_free((char *) Pol1[i]);
		SYM_free((char *) Pol1);
		SYM_free((char *) Permutation);
		SYM_free((char *) NormalPolynom);
		return(0);
	}
	else
	{
		for (i=0;i<=Grad;i++)
			SYM_free((char *) Pol1[i]);
		SYM_free((char *) Pol1);
		SYM_free((char *) Permutation);
		SYM_free((char *) NormalPolynom);
		return(1);
	}

}


/****************************************************************************/
/* Funktion getNormalPol erzeugt ein Normalpolynom.                         */
/*                                                                          */
/* Uebergabeparameter : NormalPolynom, Grad                                  */
/*                                                                          */
/* Rueckgabeparameter : OK falls erfolgreich, ERROR sonst                         */
/****************************************************************************/
static INT getNormalPol(NormalPolynom,Grad) INT *NormalPolynom, Grad;
{
	INT i;
	INT j;

	/* Vorbelegung von NormalPolynom */
	for (i=1;i<Grad-1;i++)
		NormalPolynom[i] = 0;
	NormalPolynom[0] = 1;
	NormalPolynom[Grad-1] = UE_subg(0,1);
	NormalPolynom[Grad] = 1;

	while(!(testirrPolynom(NormalPolynom,Grad) && testNormalPol(NormalPolynom,Grad)))
	{
		j = 0;
		while(NormalPolynom[j]==(Charakteristik-1))
		{
			if (j>0)
				NormalPolynom[j] = 0;
			else
				NormalPolynom[0] = 1;
			j++;
			if (j==Grad-1)
				return(ERROR);
		}
		if (j==Grad-1)
			return(ERROR);
		NormalPolynom[j]++;
	}
	return(OK);
}


/****************************************************************************/
/* Funktion minimalPolynom berechnet zu einem Element in                    */
/*          Normalbasenreprsentation das Minimalpolynom,                   */
/* bergabeparameter : Element (Element[0] = Grad, dann die EINTrge a,a^p,.*/
/*                     minPolynom : Grad eINTrge Platz  (da normiert)      */
/*                     (aufsteigende x-Potenzen                             */
/* Rckgabewert : 1, falls Minimalpoylom berechnet., 0 sonst                */
/****************************************************************************/
static INT minimalPolynom(Element,minPolynom) INT *Element; INT *minPolynom;
{
	INT rueckwert = 1;
	INT Grad = Element[0];
	INT i;
	INT j;
	INT *ElementPotenz;
	INT *MinusElementPotenz;
	INT *zwischElement;
	INT **Polynom;
	if(!(Polynom = (INT **) UE_malloc((Grad+1)*sizeof(INT *))))
		return no_memory();

	UE_Platz(&ElementPotenz);
	UE_Platz(&MinusElementPotenz);
	for (i=0;i<=Grad;i++)
		ElementPotenz[i] = Element[i];

	UE_negativ(&ElementPotenz,&MinusElementPotenz);
	UE_Platz(&zwischElement);

	/* Minimalpolynom mit 0 vorbelegen */
	for(i=0;i<=Grad;i++)
	{
		UE_Platz(&Polynom[i]);
		Polynom[i][0] = (INT)1;
		Polynom[i][1] = (INT)0;
	}

	/* Fuer die Multiplikation mit x-a^q^i starten wir bei der hchsten
       Potenz, auf diese Weise kann das Schiften fr die x-Multiplikation
       vernachlssigt werden */

	Polynom[Grad][1] = (INT)1;
	for(i=0;i<=Grad;i++)
		Polynom[Grad-1][i] = MinusElementPotenz[i];

	/* Berechnung des Minimalpolynoms */
	for(i=Grad;i>1;i--)
	{
		UE_hoch(&ElementPotenz,Charakteristik,&ElementPotenz);
		UE_negativ(&ElementPotenz,&MinusElementPotenz);
		for(j=i;j<=Grad;j++)
		{
			UE_mult(&MinusElementPotenz,&Polynom[j-1],&zwischElement);
			UE_add(&Polynom[j-2],&zwischElement,&Polynom[j-2]);
		}
		UE_add(&MinusElementPotenz,&Polynom[Grad-1],&Polynom[Grad-1]);
	}
	/* berprfung ob Ergebnispolynom nur aus Skalaren besteht */
	for (i=0;i<Grad;i++)
	{
		minimalErw(&Polynom[i]);
		if(Polynom[i][0] != 1)
		{
			for(j=0;j<Grad;j++)
				UE_Zeige(&Polynom[j]);
			rueckwert = 0;
		}
		minPolynom[i] = (Polynom[i])[1];
		UE_Free(& Polynom[i]);
	}
	UE_Free(& Polynom[Grad]);
	SYM_free(Polynom);
	UE_Free(& ElementPotenz);
	UE_Free(& MinusElementPotenz);
	UE_Free(&zwischElement);
	return(rueckwert);
}



/******************************************************************************/
/* erzeugePol erzeugt ein Tracecompatibles Polynom                            */
/* Uebergabeparameter :                                                      */
/* Datei = Dateizeiger, Grad = gewuenschter Erweiterungsgrad,                  */
/* tracePolynom = Zeiger auf Tracecompatibles Polynom                         */
/*                                                                            */
/* Rueckgabe = 1 falls Erzeugung erfolgreich, 0 sonst.                         */
/******************************************************************************/
static INT erzeugePol(Grad,tracePolynom)
	INT Grad;           /* gewnschter Erweiterungsgrad */
	INT *tracePolynom;  /* Platz fr tracecompatibles Polynom */

{
	INT Gradsich ;
	INT i=2;
	INT j;
	INT k;
	INT spur,hll;

	INT *kleinPolynom;        /* Tracepolynom p^(n-1)         */
	INT kleinGrad;            /* Grad von kleinPolynom */
	INT *kleinElement;        /* Element in GF(p^(n-1)) */
	INT *grossElement;        /* Element in GF(p^n)     */
	INT *minPolynom;          /* Minimalpolynom von kleinElement */
	INT *xHOCHmPLUS1;         /* Polynom x^m+1  */
	INT *Faktor;              /* Faktor zu x^p^(Grad-1) - 1      */

	INT anzahlPrimfakt = 0;   /* Anzahl der Primpotenzfaktoren */
	INT Basis[20];            /* Basen der Primpotenzen */
	INT Potenz[20];           /* Potenzen der Primpotenzen */
	INT **multTafel[20];      /* Zeiger auf Multiplikationstafeln */

	INT **Gauss;              /* fr Gaussalgorithmus */
	INT *Permutation;         /* fr Gaussalgorithmus */
	INT *NormalPolynom;       /* Platz fr Normalpolynom */
	INT **hilfsZeiger;        /* Hilfszeiger */

	/* Zerlegung von Grad in Primfaktoren */
	Gradsich = Grad;
	while (Gradsich > 1)
	{
		while(!(Gradsich%i) && Gradsich > 1)
		{
			Gradsich /= i;
			if (anzahlPrimfakt>0 && Basis[anzahlPrimfakt-1] == i)
				Potenz[anzahlPrimfakt-1] ++;
			else
			{
				Basis[anzahlPrimfakt] = i;
				Potenz[anzahlPrimfakt] = 1;
				anzahlPrimfakt++;
			}
		}
		i++;
	}

	/* Falls nur eine Primpotenz -> Erzeugung, andernfalls Berechnung aus
        Multiplikationstabellen bestehender Erweiterungspolynome ->
        Rekursiver Aufruf */

	if (anzahlPrimfakt==1)    /* Starten des Erzeugungsvorgangs */
	{
		/* Erzeugen eines Normalpolynoms */
		UE_Erw_Grad = Grad; /* AK 130197 */
		kleinGrad = Grad/Basis[0];
		UE_Platz(&kleinElement);

		if(!(NormalPolynom = (INT *) UE_malloc((Grad+1)*sizeof(INT))))
			return no_memory();

		if(getNormalPol(NormalPolynom,Grad) != OK)
		{
			SYM_free((char *) NormalPolynom);
			/*
                        printf("Kann kein Normalpolynom zum Grad %d erzeugen.\n",Grad);
                        return(0);
*/
			error("ff.c: internal error FF-40");
		}

		/* Hole Polynom vom Grad p^(n-1) */
		if(!(kleinPolynom = (INT *) UE_malloc((kleinGrad+1)*sizeof(INT))))
		{
			SYM_free((char *) NormalPolynom);
			return no_memory();
		}

		if(!(minPolynom = (INT *) UE_malloc((Grad+1)*sizeof(INT))))
		{
			SYM_free((char *) NormalPolynom);
			SYM_free((char *) kleinPolynom);
			return no_memory();
		}

		if(liestracepol(kleinGrad,kleinPolynom,1) != OK)
		{
			SYM_free((char *) NormalPolynom);
			SYM_free((char *) minPolynom);
			SYM_free((char *) kleinPolynom);
			error("internal error FF201");
			return ERROR;
		}

		if(erzmulttafel(Grad,-1,NormalPolynom) != OK)
		{
			SYM_free((char *) NormalPolynom);
			SYM_free((char *) minPolynom);
			SYM_free((char *) kleinPolynom);
			error("internal error FF202");
			return ERROR;
		}
		kleinElement[0] = kleinGrad;
		for(i=1;i<=kleinGrad;i++)
			kleinElement[i] = 0;
		k = 1;
		while(k)
		{
			j = 1;
			while(kleinElement[j]==Charakteristik-1)
			{
				kleinElement[j] = 0;
				j++;
				if (j>kleinGrad)
				{
					SYM_free((char *) NormalPolynom);
					SYM_free((char *) kleinPolynom);
					SYM_free((char *) minPolynom);
					UE_Free(& kleinElement);
					error("internal error FF203");
					return ERROR;
				}
			}
			if (j>kleinGrad)
			{
				SYM_free((char *) NormalPolynom);
				SYM_free((char *) kleinPolynom);
				SYM_free((char *) minPolynom);
				UE_Free(& kleinElement);
				error("internal error FF204");
				return ERROR;
			}
			kleinElement[j]++;

/* spur wird mit -Spur von Kleinelement belegt. fuer Trace-kompatibilitaet ist
    spur == 1 erforderlich  auaerdem mua der 1. Koeffizient
    <> 0 sein, da andernfalls das Element (geschiftet) bereits
    berprft wurde     */

			spur = 0;
			for (i=1;i<=kleinGrad;i++)
				spur = UE_addg(spur,kleinElement[i]);

			if(kleinElement[1] && spur == 1)
			{
				minimalPolynom(kleinElement,minPolynom);
				for(i=0;i<kleinGrad;i++)
					if(minPolynom[i] != kleinPolynom[i])
						i = kleinGrad + 1;
				if(i==kleinGrad)
					k = 0;
			}
		}

		SYM_free((char*)NormalPolynom);
		UE_Platz(&grossElement);
		xHOCHmPLUS1 = (INT *) SYM_calloc(Grad+1,sizeof(INT));
		xHOCHmPLUS1[0] = UE_subg(0,1);
		xHOCHmPLUS1[Grad] = 1;
		Faktor = (INT *) SYM_calloc(Basis[0],sizeof(INT));
		Faktor[0] = 0;
		grossElement[0] = Grad;

		for (i=1;i<=kleinGrad;i++)
			{
			grossElement[i-1] = kleinElement[i];
			}

		UE_Free(&kleinElement);

		for (i=kleinGrad;i<=Grad;i++)
			grossElement[i] = 0;
		k = 1;
		while(k && !spezEinsGGT(xHOCHmPLUS1,grossElement,Grad))
		{
			j = 0;
			while(Faktor[j]==Charakteristik-1)
			{
				Faktor[j] = 0;
				grossElement[j] = UE_subg(grossElement[j],1);
				grossElement[kleinGrad+j] = UE_addg(grossElement[kleinGrad+j],1);
				j++;
				if (j==Basis[0])
				{
					SYM_free((char *) kleinPolynom);
					SYM_free((char *) minPolynom);
					SYM_free((char *) grossElement);
					error("internal error FF206");
					return ERROR;
				}
			}
			Faktor[j]++;
			grossElement[j] = UE_subg(grossElement[j],1);
			grossElement[kleinGrad+j] = UE_addg(grossElement[kleinGrad+j],1);
		}
		SYM_free((char*)xHOCHmPLUS1); /* AK 030294 */
		SYM_free((char*)minPolynom); /* AK 030294 */
		SYM_free((char *) kleinPolynom); /* AK 040293 */
		SYM_free((char*)Faktor); /* AK 030294 */
		for (i=Grad;i>0;i--)
			grossElement[i] = grossElement[i-1];
		grossElement[0] = Grad;
		minimalPolynom(grossElement,tracePolynom);
 		UE_Free(& grossElement);  /* AK 030294 */
	}
	/****************************************************************************/
else /* Polynom erzeugen aus bestehenden
	                                     Polynomen */
	{
		/* Belegung von Basis[i] mit Basis[i]^Potenz[i] */
		for(i=0;i<anzahlPrimfakt;i++)
			Basis[i] = UE_power(Basis[i],Potenz[i]);


		/* Erzeugung der bentigten Multiplikationstabellen */
		for (i=0;i<anzahlPrimfakt;i++)
		{
			if (erzmulttafel(Basis[i],1,NULL) != OK)
			{
				/*
				for (j=0;j<i;j++)
					{
					SYM_free((char *) multTafel[j]);
					}
				*/ /* AK 090197 */
				error("internal error FF207");
				return ERROR;
			}
			else
				{
				multTafel[i]=Mult_Tafel;
				}
		}

		/* Erzeugung der Multiplikationsmatrix aus den berechneten Tafeln */
		if(!(Mult_Tafel = (INT **) UE_malloc(Grad*sizeof(INT*))))
		{
			/*
			for (j=0;j<anzahlPrimfakt;j++)
				SYM_free((char *) multTafel[j]);
			*/ /* AK 090197 */
			return no_memory();
		}

		if(!(UE_Platz_Mult = (INT *) UE_malloc(Grad*Grad*sizeof(INT))))
		{
			/*
			for (j=0;j<anzahlPrimfakt;j++)
				SYM_free((char *) multTafel[j]);
			*/ /* AK 090197 */
			return no_memory();
		}

		k = 0;
		for (i=0;i<Grad;i++)
		{
			Mult_Tafel[i] = &UE_Platz_Mult[k];
			k += Grad;
		}

		for(j=0;j<Grad*Grad;j++)
			UE_Platz_Mult[j] = 1;

		for(k=0;k<Grad;k++)
			for(j=0;j<Grad;j++)
				for(i=0;i<anzahlPrimfakt;i++)
					Mult_Tafel[k][j] *= multTafel[i][k%Basis[i]][j%Basis[i]];

/*
		for(i=0;i<anzahlPrimfakt;i++)
			SYM_free((char *) multTafel[i]);
*/


		/* Um aus der Multiplikationstafel das zugehrige Polynom zu berechnen
        geht man wie folgt vor:
        Aufstellen der Basisdarstellung von 1,a,a^2,a^3, ... in Normalbasen-
        reprsentation == Matrix A
        Aufstellen des Vektors a^Grad in Normalbasenreprsentation = Vektor v
        Lsen des Gleichungssystems Ax = v  -> Lsung x ist a^Grad in Basis
        1,a,a^2,a^3, ... Tracecompatibles Polynom
        f(x) = x^Grad-v[Grad-1]*x^(Grad-1)-v[Grad-2]*x^(Grad-2)-....-v[0] . */

		/* Vorbereitungen */
		UE_Erw_Grad = Grad;
		if(!(Permutation = (INT *) UE_malloc(Grad*sizeof(INT))))
			return no_memory();
		if(!(Gauss = (INT **) UE_malloc(Grad*sizeof(INT*))))
		{
			SYM_free((char *) Permutation);
			return no_memory();
		}

		if(!(hilfsZeiger = (INT **) UE_malloc((Grad+1)*sizeof(INT*))))
		{
			SYM_free((char *) Permutation);
			SYM_free((char *) Gauss);
			return no_memory();
		}

		for(i=0;i<=Grad;i++)
			UE_Platz(&hilfsZeiger[i]);

		/* Belegung des 1-Elementes   */
		hilfsZeiger[0][0] = Grad;
		for(i=1;i<=Grad;i++)
			hilfsZeiger[0][i] = 1;
		/* Belegung von a^1 */
		hilfsZeiger[1][0] = Grad;
		hilfsZeiger[1][1] = 1;
		for(i=2;i<=Grad;i++)
			hilfsZeiger[1][i] = 0;

		/* Belegung von a^2 bis a^(Grad-1) */
		for(i=2;i<=Grad;i++)
			UE_mult(&hilfsZeiger[1],&hilfsZeiger[i-1],&hilfsZeiger[i]);

		for(i=0;i<Grad;i++)
			Gauss[i] = &hilfsZeiger[i][1];

		/* transponieren von Gauss  */
		for(i=0;i<Grad-1;i++)
			for(j=i+1;j<Grad;j++)
			{
				k = Gauss[i][j];
				Gauss[i][j] = Gauss[j][i];
				Gauss[j][i] = k;
			}

		if (!gausszerlegu(Gauss,Grad,Permutation))
		{
			for(i=0;i<=Grad;i++)
				UE_Free(& hilfsZeiger[i]);

			SYM_free((char *) Permutation);
			SYM_free((char *) Gauss);
			SYM_free((char *) hilfsZeiger);
		error("internal error FF208");
			return ERROR;
		}
		gaussaufloes(Gauss,Grad,&hilfsZeiger[Grad][1],Permutation);
		for(i=1;i<=Grad;i++)
			tracePolynom[i-1] = UE_subg(0,hilfsZeiger[Grad][i]);
		for(i=0;i<=Grad;i++)
			UE_Free(& hilfsZeiger[i]);

		SYM_free((char *) Permutation);
		SYM_free((char *) Gauss);
		SYM_free((char *) hilfsZeiger);
		SYM_free((char *) Mult_Tafel);
		SYM_free((char *) UE_Platz_Mult);

	}
	einfuegTrace(Grad,tracePolynom);
	return OK;
}


/******************************************************************************/
/* Funktion getString verwandelt eine Zahl in einen entsprechenden String im  */
/*                    10 'ner System.                                         */
/* bergabeparameter       Zahl : umzuwandelnde Zahl                          */
/*                         String       : Zeiger auf Platz fr String         */
/*                                                                            */
/* Rckgabeparameter : Lnge : Lnge des Zugehrigen Strings                  */
/******************************************************************************/
static INT getString(Zahl,String) INT Zahl; char *String;
{
	INT i=49;
	char hilfsString[50];

	if(Zahl == 0)
	{
		String[0] = '0';
		return(1);
	}
	while(Zahl)
	{
		hilfsString[i--] = 48 + (Zahl % 10);
		Zahl /= 10;
	}
	Zahl = i;
	for (i=Zahl+1;i<=49;i++)
		String[i-Zahl-1] = hilfsString[i];
	return(49-Zahl);
}




/******************************************************************************/
/*   Funktion lies_tracepol liesst das tracecompatible Polynom zu gegebener   */
/*   Charakteristik und gegebenen Erweiterungsgrad ein.                       */
/*                                                                            */
/*   In der Datei trace_??.pol (?? stehen fr die Charakterisktik bei         */
/*      Charakteristik > 99 wird z.B. trac1021.pol gesucht)                   */
/*   wird nach 'G<GRAD>:' gesucht. Die nachfolgenden Zahlen enthalten die     */
/*   Positionen a[0] bis a[GRAD-1] des zugehrigen Polynoms.                  */
/*   Sollte dieses nicht vorhanden sein, versucht das Programm es zu erzeugen.*/
/*                                                                            */
/*   Rueckgabewert : 0 , falls das Polynom nicht initialisiert werden konnte, */
/*                   1 , sonst.                                               */
/*                                                                            */
/*                                   Verfasser: Ulrich Eidt                   */
/*                                   Stand    : 16.01.94                       */
/******************************************************************************/
static INT liestracepol(Grad,tracePolynom,DateiOffen)
	INT Grad;           /* Gibt den gewuenschten Erweiterungsgrad an.            */
	INT tracePolynom[]; /* Vektor mit Platz fuer die EINTraege des ermittelten   */
/* Polynoms (die i-te Stelle von tracePolynom gibt den   */
/* Koeffizienten zu x^i an der hoechste Koeffizient wird */
/* (da normiert) nicht belegt)).                         */
	INT DateiOffen;     /* Kennzeichen ob die Datei bereits offen ist */
{
	INT datneu = 0;     /* Kennzeichen ob Datei neu  */
	INT gefunden = 0;   /* Kennzeichen ob Polynom gefunden */
	INT zahl;           /* Einlesevariable */
	/* INT gelesen=1;*/      /* Anzahl der gelesenen Zeichen, 0 falls Dateiende*/
	INT Pufferzeiger=0; /* Zeiger fuer Bearbeitung des Puffer             */
	INT hilfsChar=Charakteristik;
	INT i;
	INT ret_val = OK;    /* Rckgabewert */
	char Puffer[50];             /* Einlesepuffer                                 */
	char Dateiname[15] ; /* Name der Datei                   */
	char Zeichen;       /* Platz fuer ein Zeichen wird benutzt beim       */
	/*  Einlesen des Polynoms                         */
	strcpy(Dateiname,"trace_00.pol");

	if (!DateiOffen)
	{
		/* Datei oeffnen und erstes Zeichen lesen     */
		if(Charakteristik<100)
		{
			Dateiname[6] = 48+(Charakteristik / 10);
			Dateiname[7] = 48+(Charakteristik % 10);
		}
		else
			if(Charakteristik>=100000000)
			{
/*
				printf("Charakteristik zu gross,\n");
				printf("Charakteristik muss < 100000000 sein !\n");
*/
				error("ff.c:internal error FF50");
				return(0);
			}
			else
			{
				i = 7;
				while(hilfsChar)
				{
					Dateiname[i--] = 48 + (hilfsChar % 10);
					hilfsChar /= 10;
				}
			}

		Datei = fopen(Dateiname,"r+");
		if (Datei == 0)
		{
			Datei = fopen(Dateiname,"w");
			if (Datei == 0)
			{
				/*printf("Die Datei %s ist nicht erstellbar !\n",Dateiname);*/
				error("ff.c:internal error FF51");
				return(0);
			}
			datneu = 1;
		}
		/* Lese erstes Zeichen der Datei falls <> 'G' -> altes Format */
		Puffer[0] = getc(Datei);
		if(Puffer[0] != 'G')
			datneu = 1;
		if(datneu)
		{
			Datei = freopen(Dateiname,"w+",Datei);
			if (Datei == 0)
			{
				/* printf("Die Datei %s ist nicht erstellbar !\n",Dateiname); */
				error("ff.c:internal error FF52");
				return(0);
			}
			putc('G',Datei);
			putc('1',Datei);
			putc(':',Datei);
			Pufferzeiger = getString(Charakteristik-1,Puffer);
			for (i=0;i<Pufferzeiger;i++)
				putc(Puffer[i],Datei);
			putc('\n',Datei);
		}
	}
	Puffer[0] = 'G';
	Pufferzeiger = getString(Grad,&(Puffer[1]));
	Puffer[Pufferzeiger+1] = ':';
	Pufferzeiger += 2;

	/* Suchen des Strings ('G<GRAD>:')      */
	fseek(Datei,0,0);
	i = 0;
	while(!gefunden && (Zeichen = getc(Datei)) != (char)EOF)
	{
		if(Zeichen==Puffer[i])
			i++;
		else
			i = 0;

		if (i==Pufferzeiger)
			gefunden = 1;
	}
	/* falls gefunden -> Einlesen */
	if (gefunden)
	{
		for (i=0;i<Grad;i++)
		{
			/* */ 
			zahl = 0;
			while((Zeichen = getc(Datei)) != (char)32 && Zeichen != (char)10 && (ret_val==OK))
			{
				if (Zeichen < (char)48 || Zeichen > (char)57)
				{
/*
		printf("Unbekanntes Zeichen beim Einlesen des Polynoms Grad %ld: %d\n",Grad,Zeichen);
		printf("Abbruch\n");
*/
			error("ff.c: internal error FF55");
					ret_val = ERROR;
				}
				else
					zahl = zahl*10+(int)Zeichen-48;
			}
			tracePolynom[i] = zahl;
		}
	}
	else
	{
		if (erzeugePol(Grad,tracePolynom) != OK)
		{
			error("ff.c: internal error FF56");
			fclose(Datei);
			ret_val = ERROR;
		}
	}
	if (!DateiOffen)
		fclose(Datei);
	return(ret_val);
}



#endif /* FFTRUE */

