|
ИСТИНА |
Войти в систему Регистрация |
Интеллектуальная Система Тематического Исследования НАукометрических данных |
||
О сложности поиска периодов функций, заданных многочленами над конечным простым полемстатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК- Автор: Селезнева С.Н.
- Журнал: Дискретный анализ и исследование операций
- Том: 29
- Номер: 1
- Год издания: 2022
- Издательство: Изд-во Ин-та математики
- Местоположение издательства: Новосибирск
- Первая страница: 56
- Последняя страница: 73
- DOI: 10.33048/daio.2022.29.727
- Аннотация: Рассматриваются многочлены над конечным простым полем Fp=(Ep;+,⋅), содержащим p элементов, при этом с каждым таким многочленом f(x1,…,xn) связывается p-значная функция f:Ep^n→Ep, которую этот многочлен определяет. Периодом p-значной функции f(x1,…,xn) называется набор a=(a1,…,an) элементов из Ep такой, что имеет место равенство f(x1+a1,…, xn+an)=f(x1,…,xn). В работе предложен алгоритм, который для простого p и произвольной p-значной функции f(x1,…,xn), заданной многочленом над полем Fp, находит базис линейного пространства всех периодов этой функции f, при этом сложность алгоритма равна n^{O(d)}, где d - степень многочлена, задающего функцию f. Как следствие, показано, что в случае простого p при каждом заданном числе d задача поиска базиса линейного пространства всех периодов p-значной функции, заданной многочленом степени не выше d, может быть решена полиномиальным алгоритмом относительно числа переменных этой функции.
- Добавил в систему: Селезнева Светлана Николаевна
Прикрепленные файлы
| № | Имя | Описание | Имя файла | Размер | Добавлен |
|---|