Computer Science – Symbolic Computation
Scientific paper
2012-03-06
Computer Science
Symbolic Computation
Scientific paper
In this paper we consider polynomial representability of functions defined over Z_{p^n}, where p is a prime and n is a positive integer. Our aim is to provide an algorithmic characterization that answers the decision problem: to determine whether a given function over Z_{p^n} is polynomially representable or not. The previous characterizations given by Carlitz (1964) and Kempner (1921) are existential in nature and only lead to an exhaustive search method, i.e. algorithm with complexity exponential in size of the input. We present a new characterization which leads to an algorithm whose running time is linear in size of input.
Dukkipati Ambedkar
Guha Ashwin
No associations
LandOfFree
An Algorithmic Characterization of Polynomial Functions over Z_{p^n} does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An Algorithmic Characterization of Polynomial Functions over Z_{p^n}, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Algorithmic Characterization of Polynomial Functions over Z_{p^n} will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-536856