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 | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2019. № 43. DOI: 10.17223/20710410/43/1

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 GF(pⁿ ). 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ⁿ n) elements from GF(p) and O(pⁿ n² d⁴ w ) 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.