On the subset sum problem over finite fields

被引：71
|
作者：
Li, Jiyou [1 ]
Wan, Daqing [2 ]
机构：
[1] Peking Univ, Sch Math Sci, Beijing 100871, Peoples R China
[2] Univ Calif Irvine, Dept Math, Irvine, CA 92697 USA
来源：
FINITE FIELDS AND THEIR APPLICATIONS | 2008年 / 14卷 / 04期
基金：
中国国家自然科学基金;
关键词：
Subset sum problem; Finite fields; Decoding problem; Reed-Solomon codes; Deep holes;
D O I：
10.1016/j.ffa.2008.05.003
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
The subset sum problem over finite fields is a well-known NP-complete problem. It arises naturally from decoding generalized Reed-Solomon codes. In this paper, we study the number of solutions of the subset sum problem from a mathematical point of view. In several interesting cases, we obtain explicit or asymptotic formulas for the solution number. As a consequence, we obtain some results on the decoding problem of Reed-Solomon codes. (C) 2008 Elsevier Inc. All rights reserved.
引用
收藏
页码：911 / 929
页数：19
相关论文
共 50 条
  • [41] The Minimal Ramification Problem for Rational Function Fields over Finite Fields
    Bary-Soroker, Lior
    Entin, Alexei
    Fehm, Arno
    INTERNATIONAL MATHEMATICS RESEARCH NOTICES, 2023, 2023 (21) : 18199 - 18253
  • [42] On the cuspidalization problem for hyperbolic curves over finite fields
    Wakabayashi, Yasuhiro
    KYOTO JOURNAL OF MATHEMATICS, 2016, 56 (01) : 125 - 164
  • [43] MaxMinMax problem and sparse equations over finite fields
    Igor Semaev
    Designs, Codes and Cryptography, 2016, 79 : 383 - 404
  • [44] MaxMinMax problem and sparse equations over finite fields
    Semaev, Igor
    DESIGNS CODES AND CRYPTOGRAPHY, 2016, 79 (02) : 383 - 404
  • [45] On an elementary density problem for polynomials over finite fields
    Yao, WC
    FINITE FIELDS AND THEIR APPLICATIONS, 2001, 7 (03) : 441 - 448
  • [46] Generalizing cryptosystems based on the subset sum problem
    Kate, Aniket
    Goldberg, Ian
    INTERNATIONAL JOURNAL OF INFORMATION SECURITY, 2011, 10 (03) : 189 - 199
  • [47] On the two-dimensional subset sum problem
    Plagne, A
    ASTERISQUE, 1999, (258) : 375 - 409
  • [48] Priority algorithms for the subset-sum problem
    Yuli Ye
    Allan Borodin
    Journal of Combinatorial Optimization, 2008, 16 : 198 - 228
  • [49] Brief Announcement: On the Fair Subset Sum Problem
    Nicosia, Gaia
    Pacifici, Andrea
    Pferschy, Ulrich
    ALGORITHMIC GAME THEORY, SAGT 2015, 2015, 9347 : 309 - 311
  • [50] A new approach to address Subset Sum Problem
    Jain, Eeti
    Jain, Akarsh
    Mankad, Sapan H.
    2014 5TH INTERNATIONAL CONFERENCE CONFLUENCE THE NEXT GENERATION INFORMATION TECHNOLOGY SUMMIT (CONFLUENCE), 2014, : 953 - 956
12345