Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Moment subset sums over finite fields

Published

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

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 June 21, 2024)

Issues

If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.

Created January 31, 2020, Updated October 12, 2021