journal.isu.ru

Начальная страница

Конечная страница

УДК

Раздел
     

Файл
Скачать Изменить файл

Название RU

Авторы RU

Аннотация RU
<p>Представления функций над конечными полями, в том числе полиномиальные, в настоящее время активно исследуются. Одним из основных направлений этих исследований является сложность таких представлений. В данной работе исследуется сложность задания функций квазиполиномами над конечными полями.</p> <p>Квазиполином можно рассматривать как полином многих переменных, в котором вхождения <em>x_i⁰, . . . , x_i^k−1</em> одной из переменных заменены на функции из некоторого множества {<em>g₀(x_i), . . . , g_k−1(x_i)</em>} линейно независимых одноместных функций.</p> <p>Под сложностью полинома над конечным полем обычно понимают количество слагаемых в нем, число вхождений переменных или степень. В случае квазиполиномов напрямую можно оценивать количество слагаемых, число вхождений переменных и степень требуют обобщения. В статье в качестве сложности квазиполинома исследуется количество слагаемых в нем. Для случая квазиполиномов по модулю простого <em>k</em> ранее была известна верхняя оценка такой сложности, а именно, сложность задания квазиполиномами <em>n</em>-местной функции над конечным полем простого порядка <em>k</em> не превосходит величины <em>k·kⁿ/(k+1)</em>.</p> <p>В работе получена верхняя оценка сложности представления квазиполиномами функций над произвольным конечным полем порядка <em>q</em>, которая при <em>q ≥ 3</em> усиливает ранее известную верхнюю оценку, полученную для случая квазиполиномов по модулю простого числа. А именно, если <em>q = kⁿ</em>, где <em>k</em> — простое, а <em>n ≥ 1</em> для любой <em>n</em>-местной функции над конечным полем порядка <em>q </em>сложность её задания квазиполиномами ограничена сверху величиной <em>(q-1)·qⁿ/(q-q^1-q).</em></p>

Ключевые слова RU

Литература RU
1. Пантелеев В. И. Полиномиальные разложения k-значных функций по операторам дифференцирования и нормализации / В. И. Пантелеев // Изв. высш. учеб. заведений. Математика. – 1998. – № 1. – С. 17–21. 2. Перязев Н. А. Сложность булевых функций в классе полиномиальных поляризованных форм / Н. А. Перязев // Алгебра и логика. – 1995. – Т. 34. – №. 3. – С. 323–326. 3. Селезнева С. Н. О сложности k-значных функций в одном классе полиномов / С. Н. Селезнева // Проблемы теоретической кибернетики : материалы XVI Междунар. конф. (Нижний Новгород, 20–25 июня 2011 г.). – Н. Новгород : Изд-во Нижегор. ун-та, 2011. – С. 430–434. 4. Селезнева С. Н. О сложности представления функций многозначных логик поляризованными полиномами / С. Н. Селезнева // Дискрет. математика. – 2002. – Т. 14, № 2. – С. 48–53.

Название EN

Авторы EN

Аннотация EN
<p>Representations of functions over finite fields, including polynomial representations, are being actively investigated. The complexity of such representations is one of main directions of research.</p> <p>This paper is about quasi polynomial complexity of functions over finite fields. Quasi polynomial can be considered as a regular polynomial with the following transformation: every occurence <em>x_i⁰, . . . , x_i^k−1</em> of selected variable <em>x</em>_<em>i</em>is replaced by a function from a set {<em>g₀(x_i), . . . , g_k−1(x_i)</em>} of linearly independent unary functions.</p> <p>The number of terms, the number of occurences of variables, or the degree of a polynomial are usually used as a measure of complexity. In the case of quasi polynomials one can use the number of terms as a natural measure of complexity, while further generalization are required for the number of occurences of variables and the degree of a polynomial. In this paper the number of terms is used as a measure of complexity. Previously, the upper bound of such a complexity was known for polynomials over finite fields of prime order. Namely, the quasi polynomial complexity of <em>n</em>-ary function over finite field of prime order <em>k</em> is at most <em>k·kⁿ/(k+1)</em>.</p> <p>In this paper an upper bound for the quasi polynomial complexity of functions over finite fields of arbitrary order <em>q</em> has been obtained, which significantly improves previously known upper bound for modulo prime quasi polynomials, if <em>q ≥ 3</em>. Namely, the quasi polynomial complexity of any <em>n</em>-ary function over finite field of order <em>q</em> is at most <em>(q-1)·qⁿ/(q-q^1-q)</em>.</p>

Ключевые слова EN

Литература EN
1. Panteleev V. I. Polynomial representations of k-valued functions by derivative and normalization operators (in Russian). Russian Mathematics (Iz. VUZ). Izvestiya VUZ. Matematika., 1998, no. 1, pp. 17–21. 2. Peryazev N. A. The complexity of Boolean functions in the class of polarized polynomial forms (in Russian). Algebra and Logic, 1995, vol. 34, no. 3, pp. 323–326. 3. Selezneva S. N. On the complexity of k-valued functions in one class of polynomials (in Russian). Problemy Theoreticheskoi Kibernetiki, Nizhny Novgorod, University of Nizhny Novgorod, 2011, pp. 430–434. 4. Selezneva S. N. On the complexity of representations of functions over multivalued logics by polarized polynomials (in Russian). Discrete Mathematics and Applications, 2002, vol. 14, no. 2. pp. 48–53.