On composite modulo k polynomiality checking for k-valued logic functions of one variable

Recieved: 06/30/2023

Accepted: 12/13/2023

Published: 04/02/2024

Keywords: k-valued logic function, polynomial function, polynomial modulo k, algorithm, complexity

To cite this article

Selezneva S.N. On composite modulo k polynomiality checking for k-valued logic functions of one variable. // Moscow University Journal. Series 15. Computational Mathematics and Cybernetics. 2024. N 2, p.47-57 https://doi.org/10.55959/MSU/0137-0782-15-2024-47-2-47-57.

This work is licensed under a Сreative Commons Atribiution - NonCommercial 4.0 International (CC BY-NC 4.0)

Selezneva S.N. (Lomonosov Moscow State University (MSU))

Abstract

Polynomiality characterizations are proposed for k-valued logic functions of one variable for a composite modulo k which is a power of a prime number. Based on these characterizations, for each prime number p, polynomiality checking algorithms are obtained for pm-valued logic functions of one variable, m > 1. In these algorithms, the calculations are performed in the residue ring modulo pm. In the case of the positive answer, the algorithms find the canonical polynomial of a input function. The complexity of the obtained algorithms are evaluated (with respect to number of operations from the field of p elements with possible constants).