On bent and hyper-bent multiple-valued functions

Abstract

This paper is a contribution to the study of multiple-valued bent and hyper-bent functions in GF(p), p prime, p > 2. Special care has been given to the introduction of a sound formalism to allow giving formal proof of some properties and to characterize bent and hyper-bent functions. It is shown that multiple-valued bent functions, unlike in the binary case, may have an odd or an even number of arguments. A class of bent functions, called strict bent is introduced and its characterization is given. Hyper-bent functions are even more non-linear than bent functions. Hyper-bent p-valued functions are studied and their characterization is formalized using only simple algebra and basics of finite fields. Special classes of hyper-bent functions, called strict hyper-bent and strong hyper-bent are defined. A new representation of the Maiorana theorem is introduced, which allows an efficient generation of bent functions with a large even number of arguments. It is shown that there are at least 708,588 four place ternary strict bent functions, 486 two place ternary strict bent, 18 of which are hyper-bent, and the 100 one place five-valued functions that are bent, are also strict bent, and 20 are both strict and strong hyper-bent.