Polynomial expressions of p-ary auction functions

2017/03/23 by Shizuo Kaji, Kaji, Shizuo, Toshiaki Maeno +5
Computer Science · #12Y05 #68R05 #Coding theory and cryptography #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Cryptography and Data Security #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.1703.07930

openalex publication_date 2017/03/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let \mathbbF_p be the finite field of prime order p. For any function f \colon \mathbbF_pⁿ → \mathbbF_p, there exists a unique polynomial over \mathbbF_p having degree at most p-1 with respect to each variable which coincides with f. We call it the minimal polynomial of f. It is in general a non-trivial task to find a concrete expression of the minimal polynomial of a given function, which has only been worked out for limited classes of functions in the literature. In this paper, we study minimal polynomial expressions of several functions that are closely related to some practically important procedures such as auction and voting.

Related

• Polynomial Expressions of Carries in p-ary Arithmetics
• Minimal Value Set Polynomials
• On the characterization of minimal value set polynomials
• Extensions of a valuation from K to K[x]
• On coefficient valuations of Eisenstein polynomials