An algorithm for finding the minimum degree of~a~polynomial over~a~finite field for~a~function over~a~vector space depending on~the~choice of~an~irreducible polynomial

S. A. Belov

Prikladnaâ diskretnaâ matematika, no. 1 (2019), pp. 5-15

Résumé

The transformations of the vector space of $p$-ary vectors of length $n$, where $p$ is a prime number, are considered. Each such a transformation is assigned to a polynomial over a finite field $\mathrm{GF}(p^n)$. The finite field is represented by a residue ring modulo an irreducible polynomial. In general, depending on the choice of the irreducible polynomial, different polynomials over the finite field will correspond to the transformation over the vector space. In this paper, we propose an algorithm for finding the minimal degree of such a polynomial and an irreducible polynomial at which this degree is achieved. The algorithm is based on the calculation of expressions for polynomial coefficients through its values. In the process of the algorithm, the elements of finite fields are treated as polynomials. To compute specific irreducible polynomials, the Euclid algorithm computes the greatest common divisor of these expressions and the polynomial, which is the product of all irreducible polynomials of degree $n$. To work up to degree $d$, the algorithm requires storage of O$(p^nn)$ elements from GF$(p)$ and O$(p^nn^2d^4w)$ operations of addition and multiplication modulo $p$ where $w$ is the number of elements on which the polynomial is nonzero. Thus, the algorithm is especially effective for functions that have many zero values. The minimal degree polynomials for the S-boxes of block ciphers (GOST 28147-89, ICEBERG, LUFFA, LUCIFER, SERPENT, AES, PRESENT, GOST 34.12-2015) as well as the irreducible polynomials at which this degree is achieved have been computed.

Détail

Keywords: finite field, irreducible polynomial, Boolean functions, block cipher.