Moment subset sums over finite fields

摘要

The k-subset sum problem over finite fields is a classical NP-complete problem. Motivated by coding theory applications, a more complex problem is the higher m-th moment k-subset sum problem over finite fields. We show that there is a deterministic polynomial time algorithm for the m-th moment k-subset sum problem over finite fields for each fixed m when the evaluation set is the image set of a monomial or Dickson polynomial of any degree n. In the classical case m = 1, this recovers previous results of Nguyen-Wang (the case m = 1, p 2) [22] and the results of Choe-Choe (the case m = 1, p = 2) [3]. Published by Elsevier Inc.