The circuit complexity of checking polynomiality for functions over residue ring modulo a composite number is linear

DOI10.3103/S0278641913010032zbMath1275.65099OpenAlexW2076623897MaRDI QIDQ357917

Svetlana N. Selezneva

Publication date: 15 August 2013

Published in: Moscow University Computational Mathematics and Cybernetics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3103/s0278641913010032

zbMATH Keywords

algorithmpolynomial functioncircuitcircuit complexitymultivalued functions\(k\)-valued logic functionsfunction over a finite ringpolynomial over a finite ring

Mathematics Subject Classification ID

Boolean functions (06E30) Complexity and performance of numerical algorithms (65Y20) Many-valued logic (03B50)

Related Items (1)

On the number of functions of \(k\)-valued logic which are polynomials modulo composite \(k\)

Cites Work

• Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
• On polynomial functions (mod m)
• A Generalization of Fermat's Theorem
• A fast algorithm for the construction of polynomials modulo k for k-valued functions for composite k
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The circuit complexity of checking polynomiality for functions over residue ring modulo a composite number is linear