IISc Logo    Title

etd AT Indian Institute of Science >
Division of Electrical Sciences >
Computer Science and Automation (csa) >

Please use this identifier to cite or link to this item: http://hdl.handle.net/2005/2337

Title: An Algorithmic Characterization Of Polynomial Functions Over Zpn
Authors: Guha, Ashwin
Advisors: Dukkipati, Ambedkar
Keywords: Polynomial Functions
Polynomials Over Finite Fields
Polynomials Over Finite Rings
Polynomial Representability
Polynomial Functions - Algorithms
Functional Polynomial Equations
Submitted Date: Feb-2012
Series/Report no.: G25316
Abstract: The problem of polynomial representability of functions is central to many branches of mathematics. If the underlying set is a finite field, every function can be represented as a polynomial. In this thesis we consider polynomial representability over a special class of finite rings, namely, Zpn, where p is a prime and n is a positive integer. This problem has been studied in literature and the two notable results were given by Carlitz(1965) and Kempner(1921).While the Kempner’s method enumerates the set of distinct polynomial functions, Carlitz provides a necessary and sufficient condition for a function to be polynomial using Taylor series. Further, these results are existential in nature. The aim of this thesis is to provide an algorithmic characterization, given a prime p and a positive integer n, to determine whether a given function over Zpn is polynomially representable or not. Note that one can give an exhaustive search algorithm using the previous results. Our characterization involves describing the set of polynomial functions over Zpn with a ‘suitable’ generating set. We make use of this result to give an non-exhaustive algorithm to determine whether a given function over Zpn is polynomial representable.nβ
Abstract file URL: http://etd.ncsi.iisc.ernet.in/abstracts/3004/G25316-Abs.pdf
URI: http://hdl.handle.net/2005/2337
Appears in Collections:Computer Science and Automation (csa)

Files in This Item:

File Description SizeFormat
G25316.pdf481.29 kBAdobe PDFView/Open

Items in etd@IISc are protected by copyright, with all rights reserved, unless otherwise indicated.


etd@IISc is a joint service of SERC & IISc Library ||
|| Powered by DSpace || Compliant to OAI-PMH V 2.0 and ETD-MS V 1.01