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

DOI10.3103/S0278641913010032MaRDI QIDQ357917zbMATH OpenOpenAlexFDO

Authors 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

algorithmcircuitcircuit complexitypolynomial function\(k\)-valued logic functionsfunction over a finite ringmultivalued functionspolynomial over a finite ring

Mathematics Subject Classification ID

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

Recommendations

• Constructing Polynomials for Functions over Residue Rings Modulo a Composite Number in Linear Time
• Complex polynomials and circuit lower bounds for modular counting
• An Upper Bound on the Complexity of Multiplication of Polynomials Modulo a Power of an Irreducible Polynomial
• A faster algorithm for testing polynomial representability of functions over finite integer rings
• On the reduction in multiplicative complexity achieved by the polynomial residue number system
• scientific article; zbMATH DE number 3889515
• scientific article; zbMATH DE number 177033
• Computing modular polynomials in quasi-linear time
• Efficient checking of polynomials and proofs and the hardness of approximation problems
• Polynomial multiplication over finite fields: from quadratic to straight-line complexity

Cites work

• scientific article; zbMATH DE number 3873237 (Why is no real title available?)
• scientific article; zbMATH DE number 4074960 (Why is no real title available?)
• scientific article; zbMATH DE number 3706373 (Why is no real title available?)
• scientific article; zbMATH DE number 5242388 (Why is no real title available?)
• A Generalization of Fermat's Theorem
• A fast algorithm for the construction of polynomials modulo \(k\) for \(k\)-valued functions for composite \(k\)
• On polynomial functions (mod m)
• Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen

Cited in

(2)

• Constructing Polynomials for Functions over Residue Rings Modulo a Composite Number in Linear Time
• On the number of functions of k-valued logic which are polynomials modulo composite k

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q357917)