Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Polynomial functions over finite commutative rings
Bulyovszky B., Horváth G. Theoretical Computer Science703  76-86,2017.Type:Article
Date Reviewed: Jan 22 2018

The problem dealt with is as follows: given a finite ring ~R and a function f: RR, decide if f can be represented by a polynomial ~p (that is, f(x) = p(x) for all x ϵ R), and if so, find such ~p. For a field ~R, it is well known that the answer is always positive and that p can be found by methods already shown by Newton, Lagrange, and others.

Recently an algorithmic solution has been found for the case R = Zn by Guha and Dukkipati [1]. In the paper under review, this result is generalized to arbitrary finite commutative rings with unity. The problem is first reduced to the case of a local ring ~R, and it is assumed that R itself and certain data like the unique maximal ideal are known in advance and ring operations can be performed in constant time. Under these provisions, the algorithm developed has quasilinear complexity in terms of |R|, which corresponds to the size of the input.

Reviewer:  Heinrich Rolletschek Review #: CR145798 (1805-0235)
1) Guha, A.; Dukkipati, A. A faster algorithm for testing polynomial representability of functions over finite integer rings. Theoretical Computer Science 579, (2015), 88–99.
Bookmark and Share
 
Interpolation (G.1.1 )
 
 
Computations In Finite Fields (F.2.1 ... )
 
 
Polynomials, Methods For (G.1.5 ... )
 
 
Analysis Of Algorithms And Problem Complexity (F.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Interpolation": Date
Systolic computation of interpolating polynomials
Cappello P., Koç Ç., Gallopoulos E. Computing 45(2): 95-117, 2000. Type: Article
Jun 1 1991
Interpolation of data on the surface of a sphere
Renka R. (ed) ACM Transactions on Mathematical Software 10(4): 417-436, 1984. Type: Article
Nov 1 1985
Incremental linear interpolation
Field D. ACM Transactions on Graphics (TOG) 4(1): 1-11, 1985. Type: Article
Jun 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy