|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
О мультиаффинных многочленах над конечным полем
С. Н. Селезнева МГУ имени М.В. Ломоносова
Аннотация:
Рассматриваются такие многочлены $f(x_1, \ldots, x_n)$ над конечным полем, что для некоторого элемента $b$ этого поля множество решений уравнения $f(x_1, \ldots, x_n) = b$ совпадает с множеством решений какой-то системы линейных уравнений над этим полем. Такие многочлены названы мультиаффинными с правой частью $b$. Найдены свойства мультиаффинных многочленов над конечным полем. Доказано, что проверить мультиаффинность многочлена над конечным полем относительно некоторой правой части можно полиномиальным алгоритмом относительно числа его переменных и числа его слагаемых. Кроме того, показано, что при положительном ответе найти соответствующую систему линейных уравнений также можно полиномиальным алгоритмом относительно этих же величин.
Ключевые слова:
конечное поле, многочлен, мультиаффинность, система линейных уравнений над конечным полем, алгоритм, сложность, полиномиальный алгоритм.
Статья поступила: 14.01.2020 Переработанный вариант поступил: 24.07.2020
Образец цитирования:
С. Н. Селезнева, “О мультиаффинных многочленах над конечным полем”, Дискрет. матем., 32:3 (2020), 85–97; Discrete Math. Appl., 31:6 (2021), 421–430
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm1608https://doi.org/10.4213/dm1608 https://www.mathnet.ru/rus/dm/v32/i3/p85
|
Статистика просмотров: |
Страница аннотации: | 267 | PDF полного текста: | 52 | Список литературы: | 34 | Первая страница: | 13 |
|