# Handbook of Finite Fields

## Edited by: Gary L. Mullen and Daniel Panario

Series: Discrete Mathematics and Its Applications
Hardback: ISBN 9781439873786
eBook: ISBN 9781439873823
June 2013, 1068 pages

CRC webpage for the Handbook of Finite Fields

## Contents

Irreducible polynomials

# Irreducible Polynomials of Lowest Weight

This section is devoted to giving the (monic) lowest weight irreducible polynomial over GF(q) of lowest lexicographical order, where q <= 27. For reliability, we use a brute force method: we exhaustively search through binomials (if applicable), followed by trinomials, tetranomials (if applicable) and pentanomials. In all cases, we observe that we need not search for polynomials with more than five terms. To check irreducibility, we use the deterministic iterative irreducibility test in NTL.

The output always begins with the degree of the polynomial.

Over GF(2), the comma-separated output lists the degree, followed by the degree of the terms with non-zero coefficients, not including the constant term (which is necessarily 1).

For higher characteristics, the comma-separated output lists the degree, followed by the degree of the terms with non-zero coefficients and the coefficient (in NTL-readable format) enclosed in brackets.

If the base field is GF(p^n) with n > 1, then the first line of the output gives the defining polynomial of the field.

# Primitive Polynomials of Lowest Weight

This section is devoted to giving the (monic) lowest weight primitive polynomial over GF(q) of lowest lexicographical order, where q = 2,3,5. For reliability, we use a brute force method: we exhaustively search through binomials (if applicable), followed by trinomials, tetranomials (if applicable) and pentanomials. In all cases, we observe that we need not search for polynomials with more than five terms. To compute the primitivity, we use the Cunningham tables to obtain the factorization of p^n-1 and use this to compute the order of a root of the polynomial. We halt at the first occurrence of a composite factor listed in the Cunningham tables.

The output always begins with the degree of the polynomial.

Over GF(2), the comma-separated output lists the degree, followed by the degree of the terms with non-zero coefficients, not including the constant term (which is necessarily 1).

For higher characteristics, the comma-separated output lists the degree, followed by the degree of the terms with non-zero coefficients with the coefficient enclosed in brackets.

# Normal Bases

This section gives the normal basis of GF(2^n) over GF(2) of minimum complexity, 2 <= n <= 34, in various formats. We observe that when n = 18,19, there are two normal bases of minimum complexity and we give generators for both bases.

We provide three ways of obtaining the basis: 1) we give the modulus of the extension (in NTL GF2X format), followed by the element of least lexicographic order that generates the normal bases (in NTL GF2X format); that is, the element together with its conjugates form the basis. 2) We give the minimum polynomial of the normal elements (in NTL GF2X format). 3) We give the multiplication tables of the normal basis (in NTL mat_GF2 format).

## Normal Bases of Minimum Complexity

### Normal basis of GF(2^n) over GF(2) of minimum complexity, 2 <= n <= 34.

Output: n complexity [modulus] [normal element 1] [normal element 2 (n=18,19 only)]

### Minimum polynomial of element generating normal basis of GF(2^n) over GF(2) of minimum complexity, 2 <= n <= 34

Output: n complexity [minimum polynomial]

### Multiplication tables of normal bases of GF(2^n) over GF(2) of minimum complexity, 2 <= n <= 34

Output: n complexity \n [multiplication table]

## Gauss periods

### Lowest type t of a Gauss period generating a normal basis of GF(q^n) over GF(q)

Output: "n,t". If no t<=50 exists, output is "n,-1"