RUS  ENG
Full version
JOURNALS // Matematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography] // Archive

Mat. Vopr. Kriptogr., 2011 Volume 2, Issue 1, Pages 75–95 (Mi mvk26)

On the structure of strictly convex $k$-functions

V. G. Nikonov

Academy of Cryptography of Russian Federation, Moscow

Abstract: This article deals with strictly convex $k$-functions $f(x_1,\dots,x_n)$, $x_1,\dots,x_n\in\{0,1,\dots,k-1\}$. For such functions each equation $f(x_1,\dots,x_n)=\alpha$, $\alpha\in\{0,1,\dots,k-\nobreakspace1\}$, may be represented by an equivalent system of linear inequalities. The minimal number $r_\alpha$ of inequalities in the system is called the threshold index for the considering equation. For strictly convex $k$-function $f(x_1,\dots,x_n)$ the total threshold complexity $h=\sum_{\alpha=0}^{k-1}r_\alpha$ is considered and the range of $h$ is investigated.

Key words: $k$-functions, convex $k$-functions, systems of linear inequalities.

UDC: 579.716.32

Received 22.IV.2010

DOI: 10.4213/mvk26



© Steklov Math. Inst. of RAS, 2025