Moment Subset Sums Over Finite Fields

Lai, Tim; Marino, Alicia; Robinson, Angela; Wan, Daqing

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

Journal Article

Moment Subset Sums Over Finite Fields

Published: February 1, 2020
Citation: Finite Fields and Their Applications vol. 62, article no. 101607 (February 2020) pp. 1-25

Author(s)

Tim Lai (Indiana University), Alicia Marino (University of Hartford), Angela Robinson (NIST), Daqing Wan (UC Irvine)

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

Keywords

Moment subset sums; Dickson polynomial; Weil bound

Control Families

None selected

Documentation

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

Supplemental Material:
Preprint (pdf)

Document History:
02/01/20: Journal Article (Final)

Topics

Security and Privacy

cryptography