## `Dom::GaloisField` -- finite fields

#### Introduction

`Dom::GaloisField``(p, n, f)` creates the residue class field Zp[X]/⟨f⟩, a finite field with pn elements. If `f` is not given, it is chosen at random among all irreducible polynomials of degree n.

`Dom::GaloisField``(q)` (where q=pn) is equivalent to `Dom::GaloisField``(p,n)`.

`Dom::GaloisField``(F, n, f)` creates the residue class field F[X]/⟨f⟩, a finite field with |F| n elements. If `f` is not given, it is chosen at random among all irreducible polynomials of degree n.

#### Domain

`Dom::GaloisField(q)`
`Dom::GaloisField(p, n)`
`Dom::GaloisField(p, n, f)`
`Dom::GaloisField(F, n)`
`Dom::GaloisField(F, n, f)`

#### Parameters

`q` | - | prime power
`p` | - | prime
`n` | - | positive integer
`f` | - | univariate irreducible polynomial over `Dom::IntegerMod``(p)` or `F`, or polynomial expression convertible to such
`F` | - | finite field of type `Dom::IntegerMod` or `Dom::GaloisField`.

#### Details

- If `f` is not given, a random irreducible polynomial of appropriate degree is used; some free identifier is chosen as its variable, and this one must also be used when creating domain elements.
- Although n=1 is allowed, `Dom::IntegerMod` should be used for representing prime fields.
- If `F` is of type `Dom::GaloisField`, consisting of residue classes of polynomials, the variable of these polynomials must be distinct from the variable of `f`. If a tower several of Galois fields is constructed, the variable used in the uppermost Galois field must not equal any of those used in the tower. A special entry `"VariablesInUse"` serves to keep track of all variables appearing somewhere in the tower.

#### Introduction

`Dom::GaloisField``(p,n,f)(g)` (or, respectively, `Dom::GaloisField``(F,n,f)(g)`) creates the residue class of `g` modulo `f`. It is represented by the unique polynomial in that class that has smaller degree than `f`.

#### Creating Elements

``Dom::GaloisField`(p, n, f)(g)`

#### Parameters

`g` | - | univariate polynomial over the ground field in the same variable as `f`, or polynomial expression convertible to such

#### Categories

`Cat::Field`

, `Cat::Algebra(F)`, `Cat::VectorSpace(F)`

#### Related Domains

`Dom::AlgebraicExtension`, `Dom::IntegerMod`

#### Entries

zero

  the zero element of the field

one

  the unit element of the field

characteristic

  the characteristic of the field

size

  the number of elements of the field

PrimeField

  the prime field, which equals `Dom::IntegerMod``(p)`.

Variable

  the variable of the polynomial `f`.

VariablesInUse

  a list consisting of `"Variable"` and the variables used by the ground field.

companionMatrix

  an n times n-matrix over the ground field, where n is the degree of the field over its ground field. It can be used for representing field elements as matrices since its minimal polynomial is `f`.

companionPowers

  a list of the first n-1 powers of the companion matrix.

#### Method iszero: test for zero

- `iszero(dom a)`
- - This method returns `TRUE` if `a` equals the zero element of the field, and `FALSE` if not.
  - It overloads the function `iszero`.

#### Method _power: integer power of an element

- `_power(dom a, integer n)`
- - This method computes an.
  - It overloads `_power`.

#### Method frobenius: Frobenius map

- `frobenius(dom a)`
- - This method computes ap, where p is the size of the ground field.

#### Method conjugates: conjugates of an element

- `conjugates(dom a)`
- - This method computes the list of all distinct conjugates of `a`.

#### Method order: order of an element

- `order(dom a)`
- - This method computes the smallest postive integer n such that an=1.

#### Method isSquare: test whether an element is a square

- `isSquare(dom a)`
- - This method returns `TRUE` if there exists an x in the field such that x2=a, and `FALSE` otherwise.

#### Method ln: discrete logarithm

- `ln(dom a, dom b)`
- - This method returns the smallest positive integer n such that bn=a, or `infinity` if such an integer does not exist. `b` must be nonzero.

#### Method elementNumber: enumerate field elements

- `elementNumber(dom a)`
- - This method assigns to every element ∑i=0n-1 ai xi the number ∑i=0n-1 φ(ai) qi , where q is the number of elements of the ground field, and φ assigns to each element of the ground field a number between 0 and q-1: if the ground field is a `Dom::GaloisField` itself, its method `elementNumber` is used; if the ground field is a prime field, φ is taken to be the mapping that assigns, to each residue class modulo q, its smallest nonnegative member.
  - The inverse of this mapping has not been implemented.

#### Method matrixRepresentation: isomorphism to the algebra generated by the companion matrix

- `matrixRepresentation(dom a)`
- - This method implements the unique isomorphism between the field F[X]/⟨f⟩ and the algebra of all linear combinations of powers of the companion matrix that maps X to the companion matrix.
  - If A is the companion matrix, the image of ∑i ai Xi is ∑i ai Ai.

#### Method randomPrimitive: choose a primitive element at random

- `randomPrimitive()`
- - This method returns a randomly chosen primitive element of the field. The result is uniformly distributed.

#### Method isBasis: tests elements for being a basis over the ground field

- `isBasis(list of dom l)`
- - This method tests whether the field elements in the list `l` constitute a basis of the field, viewed as vector space over the ground field.

#### Method isNormal: tests whether a given field element is normal

- `isNormal(dom a)`
- - Let n be the degree of the field over its ground field. This method tests whether the powers a0 ...an-1 form a base of the field over its ground field. If this is the case, `TRUE` is returned; otherwise the result is `FALSE`.

#### Method randomNormal: choose normal element at random

- `randomNormal()`
- - This method chooses a random normal element simply by choosing random elements until a normal one is found.

#### Method isPrimitivePolynomial: tests whether a polynomial over the field is primitive

- `isPrimitivePolynomial(univariate polynomial over dom h)`
- - Let G be the field represented by dom. If `h` is a polynomial in z, this method returns `TRUE` if `h` is irreducible and all nonzero elements of the extension field G[z]/⟨h⟩ are powers of z. Otherwise, `FALSE` is returned.

#### Method convert: conversion from other types

- `convert(any a)`
- - The object `a` can be converted to an element of the Galois field exactly if it can be converted to an element of the super-domain, `Dom::AlgebraicExtension`.

#### Method convert_to: conversion to other types

- `convert_to(dom a, domain T)`
- - returns an object of type `T` if `a` can converted to that type, or `FAIL` otherwise. In the current version, only conversions to the type `DOM_POLY` are possible.

#### Example 1

We define `L` to be the field with 4 elements. Then a4=a for every a ∈L, by a well-known theorem.

    >> L:=Dom::GaloisField(2, 2, u^2+u+1): L(u+1)^4

                                       u + 1

#### Super-Domain

`Dom::AlgebraicExtension`

#### Axioms

`Ax::canonicalRep`

#### Changes

- no changes

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000