DISCRETE PROBLEM OF CONSTRUCTING HIGH ORDER ELEMENTS IN MULTIPLICATIVE GROUP OF FINITE FIELD

Abstract

The resistance to cracking of a number of known models for solving cryptographic problems is based on the computational complexity of the discrete logarithm problem in the chosen group. This is ensured by finding high order elements in the group. Various options for solving the discrete problem of constructing high order elements in the multiplicative group of an extended finite field are considered. In the case when it is possible to choose all three parameters that describe the mathematical model of such a field, and the extension polynomial is a binomial, an approach is proposed to strengthen the lower bound for the order of elements. This approach is combinatorial in nature. The well known fact that the degree of expansion is the product of two quantities is used. Therefore, as one of them increases, the other decreases. Depending on the relationship between these quantities, we obtain the lower bound for the order of the element in different ways. In the first case, we consider linear expressions obtained as powers of the initial element, and in the second, nonlinear expressions. We find a lower bound for the number of pairwise different products of such expressions. This is the lower bound for the order of the element. The approach does not require the factorization of the number of elements of the group into prims, it gives the element of high order and the lower bound for the order of this element in explicit form. Some values of the number of elements of the initial field and conditions on the degree of the field extension, for which there exist irreducible binomials over this field, are given. Computational data comparing the known and obtained lower bounds for the order of an element of the extended field for a number of values of the parameters, that define the field, are obtained.