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 April 19, 2024)
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, , 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
Keywords
subset sum, finite fields, moment sum
Citation
Created January 31, 2020, Updated October 12, 2021