Skip to main content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Moment subset sums over finite fields

Published

Author(s)

Tim LAI, Alicia Marino, Angela Y. 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
Created February 1, 2020, Updated January 14, 2020