|
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.
Received 22.IV.2010
Citation:
V. G. Nikonov, “On the structure of strictly convex $k$-functions”, Mat. Vopr. Kriptogr., 2:1 (2011), 75–95
Linking options:
https://www.mathnet.ru/eng/mvk26https://doi.org/10.4213/mvk26 https://www.mathnet.ru/eng/mvk/v2/i1/p75
|
|