О проверке полиномиальности функций k-значной логики одной переменной по составному модулю kстатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 26 июня 2024 г.
Аннотация:Предложены критерии полиномиальности функций k-значной логики одной переменной по составному модулю k, равному степени простого числа. На основе этих критериев для каждого простого числа p получены алгоритмы проверки полиномиальности функций p^m-значной логики одной переменной, m>=1. В этих алгоритмах все вычисления проводятся в кольце вычетов по модулю p^m. При положительном ответе эти алгоритмы находят канонический полином функции, поступающей на вход. Оценена сложность полученных алгоритмов (относительно числа операций поля из p элементов с возможными константами).