О проверке полиномиальности функций k-значной логики одной переменной по составному модулю k

Поступила: 30.06.2023

Принята к публикации: 13.12.2023

Дата публикации в журнале: 02.04.2024

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

DOI: 10.55959/MSU/0137-0782-15-2024-47-2-47-57

Для цитирования статьи

Селезнева С.Н. О проверке полиномиальности функций k-значной логики одной переменной по составному модулю k // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. 2024. № 2. С. 47-57 https://doi.org/10.55959/MSU/0137-0782-15-2024-47-2-47-57.

Это произведение доступно по лицензии Creative Commons «Attribution-NonCommercial» («Атрибуция-Некоммерчески») 4.0 Всемирная

Селезнева С.Н. (Московский государственный университет им. М.В. Ломоносова (МГУ))

Аннотация

Предложены критерии полиномиальности функций к-значной логики одной переменной по составному модулю k, равному степени простого числа. На основе этих критериев для каждого простого числа р получены алгоритмы проверки полиномиальности функций pm-значной логики одной переменной, m > 1. В этих алгоритмах все вычисления проводятся в кольце вычетов по модулю pm. При положительном ответе эти алгоритмы находят канонический полином функции, поступающей на вход. Оценена сложность полученных алгоритмов (относительно числа операций поля из р элементов с возможными константами).