Moment Subset Sums Over Finite Fields

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

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

July 19, 2023: URLs for CSRC publication details pages have changed. Legacy URLs should automatically redirect to the new URLs. However, links to the actual publications have NOT changed (e.g., DOIs and PDFs on nvlpubs.nist.gov). Please send inquiries to csrc-inquiry@nist.gov.

Journal Article

Moment Subset Sums Over Finite Fields

Documentation Topics

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