Том 29, номер 1, 2022 г., Стр. 56-73

УДК 519.712.3+512.622+510.52
Селезнева С. Н.
О сложности поиска периодов функций, заданных многочленами над конечным простым полем

Аннотация:
Рассматриваются многочлены над конечным простым полем $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$, может быть решена полиномиальным алгоритмом относительно числа переменных этой функции.
Библиогр. 11.

Ключевые слова: $p$-значная функция (функция $p$-значной логики), конечное поле, простое поле, многочлен над полем, периодичность, алгоритм, сложность.

DOI: 10.33048/daio.2022.29.727

Селезнева Светлана Николаевна ¹
1. Московский гос. университет им. М. В. Ломоносова,
Ленинские горы, 1, 119991 Москва, Россия
е-mail: selezn@cs.msu.ru

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

Литература

[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 с.