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...

See full abstract
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) and the results of Choe-Choe (the case

*m*=1,

*p*=2).

Hide full abstract