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

DOI10.3103/S0278641913010032zbMATH Open1275.65099OpenAlexW2076623897MaRDI QIDQ357917FDOQ357917

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

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

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)

Cites Work

• Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
• On polynomial functions (mod m)
• A Generalization of Fermat's Theorem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A fast algorithm for the construction of polynomials modulo \(k\) for \(k\)-valued functions for composite \(k\)
• Title not available (Why is that?)

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)