Polynomials

Detailed Description

The MeatAxe can work with polynomials over a finite field. A polynomial is represented by a Poly_t structure. Each polynomial carries the field order, i.e., you can work with polynomials over different fields on one program. However, this feature is currently of little use since all standard operations only work on polynomials over the same field, and there is no easy way to identify polynomials over a field and its subfields.

There is a second representation of polynomials as product of factors, see FPoly_t.

Data Structures
struct	factor_t
	Internal representation of a factor. More...
class	Poly_t
	A Polynomial. More...
class	FPoly_t
	A Factored Polynomial. More...

Functions
FPoly_t *	Factorization (const Poly_t *pol)
	Factor a polynomial. More...
int	FpIsValid (const FPoly_t *p)
	Check a Factored Polynomial. More...
FPoly_t *	FpAlloc ()
	Allocate a Factored Polynomial. More...
int	FpFree (FPoly_t *x)
	Free a Factored Polynomial. More...
FPoly_t *	FpDup (const FPoly_t *src)
	Duplicate a Factored Polynomial. More...
FPoly_t *	FpMulP (FPoly_t *dest, const Poly_t *src, int pwr)
	Multiply With an Irreducible Polynomial. More...
FPoly_t *	FpMul (FPoly_t *dest, const FPoly_t *src)
	Multiply Factored Polynomials. More...
int	FpPrint (const char *name, const FPoly_t *p)
	Print a factored polynomial. More...
Poly_t *	PolAdd (Poly_t *dest, const Poly_t *src)
	Add Polynomials. More...
Poly_t *	PolAlloc (int fl, int n)
	Allocate a polynomial This function creates the polynomial p(x)=x^n over the current field. More...
int	PolCompare (const Poly_t *a, const Poly_t *b)
	Compare Two Plynomials. More...
Poly_t *	PolDerive (Poly_t *pol)
	Derive a Polynomial. More...
Poly_t *	PolDivMod (Poly_t *a, const Poly_t *b)
	Polynomial Division. More...
Poly_t *	PolDup (const Poly_t *p)
	Duplicate a Polynomial. More...
int	PolFree (Poly_t *x)
	Free a polynomial" This function frees a polynomial data structure and cleans up all internal data. More...
Poly_t *	PolGcd (const Poly_t *a, const Poly_t *b)
	Greatest Common Divisor of two Polynomials. More...
int	PolGcdEx (const Poly_t *a, const Poly_t *b, Poly_t **result)
	Greatest Common Divisor of two Polynomials. More...
int	PolIsValid (const Poly_t *p)
	Check a polynomial. More...
Poly_t *	PolMod (Poly_t *a, const Poly_t *b)
	Polynomial division. More...
void	Pol_Normalize (Poly_t *p)
	Normalize a polynomial. More...
Poly_t *	PolLoad (const char *fn)
	Read a Polynomial from a File. More...
Poly_t *	PolMul (Poly_t *dest, const Poly_t *src)
	Multiply Polynomials. More...
void	PolPrint (char *name, const Poly_t *p)
	Print a Polynomial This function prints a polynomial on the standard output in a human-readable form. More...
Poly_t *	PolRead (FILE *f)
	Read a Polynomial from a File. More...
int	PolSave (const Poly_t *pol, const char *fn)
	Write a Polynomial to a File. More...
int	PolWrite (const Poly_t *p, FILE *f)
	Write a polynomial to a file. More...

Function Documentation

FPoly_t* Factorization

(

const Poly_t *

pol

)

Factor a polynomial.

This function decomposes a polynomial into irreducible factors using the Berlekamp algorithm.

Parameters

pol	Polynomial to factor.

Returns

The factorization of pol or 0 on error.

FPoly_t* FpAlloc

(

)

Allocate a Factored Polynomial.

This function creates a new Fpoly_t structure. The new polynomial is empty, i.e., it has no factors.

Returns

Pointer to the new FPoly_t structure or 0 on error.

FPoly_t* FpDup

(

const FPoly_t *

src

)

Duplicate a Factored Polynomial.

This function creates a copy of a factored polynomial.

Parameters

src	Pointer to a factored polynomial.

Returns

A pointer to a copy of src, or 0 on error.

int FpFree

(

FPoly_t *

x

)

Free a Factored Polynomial.

Returns

0 on success, -1 on error.

See also

FPoly_t FpAlloc

int FpIsValid

(

const FPoly_t *

p

)

Check a Factored Polynomial.

Parameters

p	The polynomial.

Returns

1 if p is a valid factores polynomial, 0 otherwise.

FPoly_t* FpMul	(	FPoly_t *	dest,
		const FPoly_t *	src
	)

Multiply Factored Polynomials.

Multiplies dest by src. The previous content of dest is lost.

See also

FpMulP()

Parameters

dest	Factored polynomial to modify.
src	Factored polynomial.

Returns

The function returns |dest| or |NULL| on error.

FPoly_t* FpMulP	(	FPoly_t *	dest,
		const Poly_t *	src,
		int	pwr
	)

Multiply With an Irreducible Polynomial.

This function multiplies a factored polynomial with the power of an an irreducible factor. It is not checked that src is irreducible.

See also

FpMul()

Parameters

dest	Factored polynomial to modify.
src	Irreducible polynomial.
pwr	Power of the irreducible polynomial.

Returns

The function returns dest or 0 on error.

int FpPrint	(	const char *	name,
		const FPoly_t *	p
	)

Print a factored polynomial.

This function prints a factored polynomial to the standard output. If name is not 0, "name=" is printed before the polynomial.

Parameters

name	Name of the polynomial or 0.
p	Pointer to the factored polynomial.

Returns

0 on success, -1 on error.

void Pol_Normalize

(

Poly_t *

p

)

Normalize a polynomial.

This function makes sure that the leading coefficient of a polynomial is non-zero.

Poly_t* PolAdd	(	Poly_t *	dest,
		const Poly_t *	src
	)

Add Polynomials.

Thus function adds src to dest. The polynomials must be over the same field.

Parameters

dest	Pointer to the first polynomial.
src	Pointer to the second polynomial.

Returns

dest, or 0 on error.

Poly_t * PolAlloc	(	int	fl,
		int	n
	)

Allocate a polynomial This function creates the polynomial p(x)=x^n over the current field.

If n is negative, a zero polynomial is created. The return value is a pointer to a newly allocated Poly_t structure. The caller is responsible for releasing memory by calling PolFree() when the polynomial is no longer needed.

Parameters

fl	Field order.
n	Degree of the polynomial.

Returns

Pointer to a new Poly_t structure or 0 on error.

int PolCompare	(	const Poly_t *	a,
		const Poly_t *	b
	)

Compare Two Plynomials.

This function compares two polynomials and returns 0 if the polynomials are equal, -1 if a<b, or 1 if a>b. The ordering of polynomials is defined as follows.

• If a and b are over different fields, the polynomials over the larger field is greater.
• Otherwise, if they have different degrees, the polynomial with the higher degree is greater.
• If both field and degree are equal, the result of the comparison is 0 if the polynomials are equal. Otherwise it is unspecified if the return value is +1 or -1.

  Parameters

  a	First polynomial.
  b	Second polynomial.

  Returns

  1 if a>b, -1 if a<b, 0 if a=b, or -2 on error.

Poly_t * PolDerive

(

Poly_t *

pol

)

Derive a Polynomial.

This function derives a polynomial. Note that the derived polynomial is stored in pol, replacing the original polynomial. The following piece of code shows how to keep the original polynomial intact while calculating the derivative:

Poly_t *pol, *der;
...
der = PolDerive(PolDup(pol));

Parameters

pol	Pointer to the polynomial.

Returns

pol.

Poly_t * PolDivMod	(	Poly_t *	a,
		const Poly_t *	b
	)

Polynomial Division.

This function performs a polynomial division. Given two polynomials a and b≠0 over the same field, PolDivMod() finds two polynomials q and r such that a=qb+r, and deg(r)<deg(b).

The quotient q is returned as the function result. This is a newly allocated polynomial. The caller is responsible for deleting the quotient when it no longer needed.

The remainder r, is stored in a and replaces the original value. If you need to preserve the value of a you must make a copy using PolDup() before calling PolDivMod(). b is not changed.

See also

PolMod()

Parameters

a	First polynomial (numerator) on call, remainder on return.
b	Second polynomial (denominator).

Returns

The quotient or 0 on error.

Poly_t * PolDup

(

const Poly_t *

p

)

Duplicate a Polynomial.

This function creates a copy of an existing polynomial.

Parameters

p	Pointer to the polynomial.

Returns

A copy of p or 0 on error.

See also

PolAlloc

int PolFree

(

Poly_t *

x

)

Free a polynomial" This function frees a polynomial data structure and cleans up all internal data.

Parameters

x	Pointer to the polynomial.

Returns

$0$ on success, $-1$ on error.

Poly_t * PolGcd	(	const Poly_t *	a,
		const Poly_t *	b
	)

Greatest Common Divisor of two Polynomials.

This function calculates the gratest common divisor of two poynomials. The polynomials must be over the same field, and at least one of them must be different from zero. Unlike most polynomial functions, PolGcd() normalizes the result, i.e., the leading coefficient of the g.c.d., is always one.

See also

PolGcdEx()

Parameters

a	First polynomial.
b	Second polynomial.

Returns

Greatest common divisor of a and b, 0 on error.

int PolGcdEx	(	const Poly_t *	a,
		const Poly_t *	b,
		Poly_t **	result
	)

Greatest Common Divisor of two Polynomials.

Given two polynomials a and b, this function calculates the greatest common divisor g=gcd(a,b) and two polynomials p, q such that g=pa+qb. Both a and b must be nonzero. The leading coefficient of g is always one.

result must be a pointer to an array of three Poly_t * elements. If the function is successful, pointers to g, p, and q have been stored in result[0], result[1], and result[2], respectively. The caller is responsible for destroying these polynomials when they are no longer needed. In particular, you must not use the same |result| buffer again with PolGcdEx() before the contents have been freed.

See also

PolGcd()

Parameters

a	First polynomial.
b	Second polynomial.
result	Result buffer for the g.c.d. and coefficients (see below).

Returns

0 on sucess, -1 on error.

int PolIsValid

(

const Poly_t *

p

)

Check a polynomial.

This function checks if the argument is a pointer to a valid polynomial. If the polynomial the function returns 1. Otherwise, an error is signalled and, if the error handler does not terminate the program, the function returns 0.

Parameters

p	The polynomial to check.

Returns

1 if p points to a valid polynomial, 0 otherwise.

Poly_t * PolLoad

(

const char *

fn

)

Read a Polynomial from a File.

This function opens a file, reads a single polynomial, and closes the file. The return value is a pointer to the polynomial or NULL on error. If the file contains more than one polynomial, only the first one is read.

If a polynomial was successfully read, the function returns a pointer to a newly created Poly_t object. The caller is responsible for deleting this object as soon as it no longer needed.

See also

PolRead()

Parameters

fn	File name.

Returns

Pointer to the polynomial read from the file, or 0 on error.

Poly_t * PolMod	(	Poly_t *	a,
		const Poly_t *	b
	)

Polynomial division.

This function replaces a with the remainder of the division of a by b.

See also

PolDivMod()

Parameters

a	First polynomial (numerator) on call, remainder on return.
b	Second polynomial (denominator).

Returns

a or 0 on error.

Poly_t * PolMul	(	Poly_t *	dest,
		const Poly_t *	src
	)

Multiply Polynomials.

This function multiplies dest by src and returns dest. The polynomials must be over the same field.

Parameters

dest	Pointer to the first polynomial.
src	Pointer to the second polynomial.

Returns

dest, or 0 on error.

void PolPrint	(	char *	name,
		const Poly_t *	p
	)

Print a Polynomial This function prints a polynomial on the standard output in a human-readable form.

If name is not 0, the name followed by an equal sign is printed before the polynomial. For example, the statement PolPrint("P",P) could produce the following output:

P=3x^2+x+1

Parameters

name	Name to print before the polynomial or 0.
p	Pointer to the polynomial.

Returns

0 on success, -1 on error.

Poly_t * PolRead

(

FILE *

f

)

Read a Polynomial from a File.

This function reads a polynomial from a file. If successful, the return value is a pointer to a new Poly_t object. The caller is responsible for deleting this polynomial with PolFree() when it is no longer needed.

See also

PolLoad()

Parameters

f	File to read from.

Returns

Pointer to the polynomial, or 0 on error.

int PolSave	(	const Poly_t *	pol,
		const char *	fn
	)

Write a Polynomial to a File.

This function creates a file, writes a single polynomial to the file and closes the file. If a f ile with the specified name already exists, it's contents are destroyed.

See also

PolWrite

Parameters

pol	Polynomial to write.
fn	File name.

Returns

0 on success, -1 on error.

int PolWrite	(	const Poly_t *	p,
		FILE *	f
	)

Write a polynomial to a file.

See also

PolSave()

Parameters

p	Pointer to the polynomial.
f	File to write to.

Returns

0 on success, -1 on error.