О сложности поиска периодов функций, заданных многочленами над конечным простым полем

О сложности поиска периодов функций, заданных многочленами над конечным простым полем

Селезнева С. Н.
Дискретный анализ и исследование операций, 29, 1, 56-73 (2022)
Скачать статью

УДК 519.712.3+512.622+510.52 
DOI: 10.33048/daio.2022.29.727

Аннотация:

Рассматриваются многочлены над конечным простым полем $F_p = (E_p; +, \cdot)$, содержащим $p$ элементов, при этом с каждым таким многочленом $f(x_1, \ldots , x_n)$ связывается $p$-значная функция $f : E_p^n \to E_p$, которую этот многочлен определяет. Периодом $p$-значной функции $f(x_1, \ldots , x_n)$ называется набор $a = (a_1, \ldots , a_n)$ элементов из $E_p$ такой, что имеет место равенство $f(x_1 + a_1, \ldots , x_n + a_n) = f(x_1, \ldots , x_n)$. В работе предложен алгоритм, который для простого $p$ и произвольной $p$-значной функции $f(x_1, \ldots , x_n)$, заданной многочленом над полем $F_p$, находит базис линейного пространства всех периодов этой функции $f$, при этом сложность алгоритма равна $n^{O(d)}$, где $d$ — степень многочлена, задающего функцию $f$. Как следствие, показано, что в случае простого $p$ при каждом заданном числе $d$ задача поиска базиса линейного пространства всех периодов $p$-значной функции, заданной многочленом степени не выше $d$, может быть решена полиномиальным алгоритмом относительно числа переменных этой функции.

Литература:
  1. Логачёв О. А., Сальников А. А., Смышляев С. В., Ященко В. В. Булевы функции в теории кодирования и криптологии. М.: МЦНМО, 2012. 584 с.
     
  2. Dawson E., Wu C.-K. On the linear structure of symmetric Boolean functions // Australas. J. Comb. 1997. V. 16. P. 239–243.
     
  3. Леонтьев В. К. О некоторых задачах, связанных с булевыми полиномами // Журн. вычисл. математики и мат. физики. 1999. Т. 39, вып. 6. С. 1045–1054.
     
  4. Селезнева С. Н. О сложности распознавания полноты множеств булевых функций, реализованных полиномами Жегалкина // Дискрет. математика. 1997. Т. 9, вып. 4. С. 24–31.
     
  5. Селезнева С. Н. Полиномиальный алгоритм для распознавания принадлежности реализованной полиномом функции $k$-значной логики предполным классам самодвойственных функций //Дискрет. математика. 1998. Т. 10, вып. 3. С. 64–72.
     
  6. Grigoriev D. Yu. Testing shift-equivalence of polynomials by deterministic, probabilistic and quantum machines // Theor. Comput. Sci. 1997. V. 180, No. 1–2. P. 217–228.
     
  7. Григорьев Д. Ю. Распознавание эквивалентности многочленов с точностью до сдвига: детерминированные, вероятностные и квантовые вычисления // Итоги науки и техники. Сер. Соврем. математика. и её прил. 1996. Т. 34. С. 98–116.
     
  8. Селезнева С. Н. О поиске периодов многочленов Жегалкина // Дискрет. математика. 2021. Т. 33, вып. 3. С. 107–120.
     
  9. Лидл Р., Нидеррайтер Г. Конечные поля. Т. 1. М.: Мир, 1988. 430 с.
     
  10. Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001. 384 с.
     
  11. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.

Исследование выполнено при поддержке Российского фонда фундаментальных исследований (проект № 19–01–00200–а) и Минобрнауки РФ в рамках программы Московского центра фундаментальной и прикладной математики (проект № 075–15–2019–1621).

Селезнева Светлана Николаевна
  1. Московский гос. университет им. М. В. Ломоносова, 
    Ленинские горы, 1, 119991 Москва, Россия

E-mail: selezn@cs.msu.ru

Статья поступила 14 ноября 2021 г. 
После доработки — 14 ноября 2021 г. 
Принята к публикации 26 ноября 2021 г.

Abstract:

We consider polynomials over the prime field $F_p = (E_p; +, \cdot)$ of $p$ elements. With each polynomial $f(x_1, \ldots , x_n)$ under consideration, we associate a $p$-valued function $f : E_p^n \to E_p$ that the polynomial defines. A period of a $p$-valued function $f(x_1, \ldots , x_n)$ is a tuple $a = (a_1, \ldots , a_n)$ of elements from $E_p$ such that $f(x_1 + a_1, \ldots , x_n + a_n) = f(x_1, \ldots , x_n)$. In the paper, we propose an algorithm that, for $p$ prime and an arbitrary $p$-valued function $f(x_1, \ldots , x_n)$ given by a polynomial over the field $F_p$, finds a basis of the linear space of all periods of $f$. Moreover, the complexity of the algorithm is equal to $n^{O(d)}$, where $d$ is the degree of the polynomial that defines $f$. As a consequence, we show that for $p$ prime and each fixed number $d$ the problem of searching for a basis of the linear space of all periods of a function $f$ given by a polynomial of the degree at most $d$ can be solved by a polynomialtime algorithm with respect to the number of variables of the function.

References:
  1. O. A. Logachyov, A. A. Sal’nikov, S. V. Smyshlyaev, and V. V. Yashchenko, Boolean Functions in Coding Theory and Cryptology (MTsNMO, Moscow, 2012) [Russian].
     
  2. E. Dawson and C.-K. Wu, On the linear structure of symmetric Boolean functions, Australas. J. Comb. 16, 239–243 (1997).
     
  3. V. K. Leont’ev, Certain problems associated with Boolean polynomials, Zh. Vychisl. Mat. Mat. Fiz. 39 (6), 1045–1054 (1999) [Russian] [Comput. Math. Math. Phys. 39 (6), 1006–1015 (1999)].
     
  4. S. N. Selezneva, On the complexity of completeness recognition of systems of Boolean functions realized in the form of Zhegalkin polynomials, Diskretn. Mat. 9 (4), 24–31 (1997) [Russian] [Discrete Math. Appl. 7 (6), 565–572 (1997)].
     
  5. S. N. Selezneva, A polynomial algorithm for the recognition of belonging a function of $k$-valued logic realized by a polynomial to precomplete classes of selfdual functions, Diskretn. Mat. 10 (3), 64–72 (1998) [Russian] [Discrete Math. Appl. 8 (5), 483–492 (1998)].
     
  6. D. Yu. Grigoriev, Testing shift-equivalence of polynomials by deterministic, probabilistic and quantum machines, Theor. Comput. Sci. 180 (1–2), 217–228 (1997).
     
  7. D. Yu. Grigoriev, Testing the shift-equivalence of polynomials using quantum machines, Itogi Nauki Tekh., Ser. Sovrem. Mat. Pril. 34, 98–116 (1996) [Russian] [J. Math. Sci 82 (1), 3184–3193 (1996)].
     
  8. S. N. Selezneva, On searching periods of Zhegalkin polynomials, Diskretn. Mat. 33 (3), 107–120 (2021) [Russian].
     
  9. R. Lidl and H. Niederreiter, Finite Fields (Camb. Univ. Press, Cambridge, 1985; Mir, Moscow, 1988 [Russian]).
     
  10. S. V. Yablonskii, Introduction to Discrete Mathematics (Vysshaya Shkola, Moscow, 2001) [Russian].
     
  11. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979; Mir, Moscow, 1982 [Russian]).