Moment subset sums over finite fields

Published

February 1, 2020

Author(s)

Tim LAI, Alicia Marino, Angela Robinson, Daqing Wan

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

Citation

Finite Fields and Their Applications

Volume

62

Pub Type

Journals

Download Paper

https://doi.org/10.1016/j.ffa.2019.101607

Local Download

Keywords

subset sum, finite fields, moment sum

Citation

LAI, T. , Marino, A. , Robinson, A. and Wan, D. (2020), Moment subset sums over finite fields, Finite Fields and Their Applications, [online], https://doi.org/10.1016/j.ffa.2019.101607, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=928827 (Accessed October 10, 2025)