Moment subset sums over finite fields
Moment subset sums over finite fields
复制标题
DOI：
10.1016/j.ffa.2019.101607
复制
发表时间：
2019-10
影响因子：
1
通讯作者：
Tim Lai;Alicia Marino;Angela Robinson;D. Wan
中科院分区：
文献类型：
--
作者：
Tim Lai;Alicia Marino;Angela Robinson;D. Wan
有限域上的 k 子集和问题是一个经典的 NP 完全问题。受编码理论应用的推动，一个更复杂的问题是有限域上的高 m 矩 k 子集和问题。我们证明，当评估集是任意次数 n 的单项式或 Dickson 多项式的图像集时，对于每个固定 m 的有限域上的 m 阶矩 k 子集和问题，存在确定性多项式时间算法。在经典情况 m= 1 中，这恢复了 Nguyen-Wang 先前的结果（情况 m= 1，p> 2）[22] 和 Choe-Choe 的结果（情况 m= 1，p= 2）[3]。
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)[22] and the results of Choe-Choe (the case m= 1, p= 2)[3].