A faster algorithm for testing polynomial representability of functions over finite integer rings

DOI10.1016/J.TCS.2015.02.013MaRDI QIDQ2344759zbMATH OpenOpenAlexFDO

Authors Ashwin Guha, Ambedkar Dukkipati

Publication date 18 May 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.5789

zbMATH Keywords

finite integer ringsKempner functionpolynomial functions

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Symbolic computation and algebraic computation (68W30)

Abstract: Given a function from $mathbb{Z}_n$ to itself one can determine its polynomial representability by using Kempner function. In this paper we present an alternative characterization of polynomial functions over $mathbb{Z}_n$ by constructing a generating set for the $mathbb{Z}_n$-module of polynomial functions. This characterization results in an algorithm that is faster on average in deciding polynomial representability. We also extend the characterization to functions in several variables.

Recommendations

• An algorithmic characterization of polynomial functions over \(\mathbb Z_{p^n}\)
• On polynomial functions from \(\mathbb{Z}_ n\) to \(\mathbb{Z}_ m\)
• Polynomial functions over finite commutative rings
• Constructing Polynomials for Functions over Residue Rings Modulo a Composite Number in Linear Time
• On polynomial functions from \(\mathbb{Z}_{n_ 1}\times \mathbb{Z}_{n_ 2}\times \cdots \times \mathbb{Z}_{n_ r}\) to \(\mathbb{Z}_ m\)

Cites work

• A generalization of the Smarandache function to several variables
• An algorithmic characterization of polynomial functions over \(\mathbb Z_{p^n}\)
• Counting polynomial functions \(\pmod{p^ n}\)
• Functions and polynomials ($mod p^n$)
• Functions and polynomials over Galois rings
• scientific article; zbMATH DE number 2143699 (Why is no real title available?)
• On polynomial functions (mod m)
• On polynomial functions from \(\mathbb{Z}_ n\) to \(\mathbb{Z}_ m\)
• On polynomial functions from \(\mathbb{Z}_{n_ 1}\times \mathbb{Z}_{n_ 2}\times \cdots \times \mathbb{Z}_{n_ r}\) to \(\mathbb{Z}_ m\)
• Polynomial functions (mod m)

Cited in

(6)

• Polynomial functions over finite commutative rings
• Polynomial functions on rings of dual numbers over residue class rings of the integers
• An algorithmic characterization of polynomial functions over \(\mathbb Z_{p^n}\)
• Constructing Polynomials for Functions over Residue Rings Modulo a Composite Number in Linear Time
• The circuit complexity of checking polynomiality for functions over residue ring modulo a composite number is linear
• scientific article; zbMATH DE number 7204372 (Why is no real title available?)

This page was built for publication: A faster algorithm for testing polynomial representability of functions over finite integer rings

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