Deterministic Algorithms to Solve the $(n,k)$-Complete Hidden Subset Sum Problem
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912243409485824 |
|---|---|
| author | Luo, Lixia Li, Changheng Li, Qiongxiu |
| author_facet | Luo, Lixia Li, Changheng Li, Qiongxiu |
| contents | The Hidden Subset Sum Problem (HSSP) is a significant NP-complete problem in number theory and combinatorics, with applications in cryptography and AI privacy. For the $(n,k)$-complete HSSP, where a target multiset must be recovered from its all $k$-subset sums, existing algorithms face limitations due to high complexity or intractability. This paper proposes two deterministic algorithms: a brute-force approach, and a novel method leveraging symmetric polynomials and Vieta's formulas with $O\left(\sum_{u=1}^n p(u,\leq k)^3+\binom{n}{k}n\right)$ complexity, where $ p(u,\leq k)$ counts the number of partitions of a positive integer $u$ into at most $k$ parts. The latter constructs an $n$-th degree polynomial via Vieta's formulas, whose roots correspond to the hidden multiset elements. Additionally, the discussion about the homogeneous symmetric polynomial rings is of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_04967 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Deterministic Algorithms to Solve the $(n,k)$-Complete Hidden Subset Sum Problem Luo, Lixia Li, Changheng Li, Qiongxiu Combinatorics Number Theory The Hidden Subset Sum Problem (HSSP) is a significant NP-complete problem in number theory and combinatorics, with applications in cryptography and AI privacy. For the $(n,k)$-complete HSSP, where a target multiset must be recovered from its all $k$-subset sums, existing algorithms face limitations due to high complexity or intractability. This paper proposes two deterministic algorithms: a brute-force approach, and a novel method leveraging symmetric polynomials and Vieta's formulas with $O\left(\sum_{u=1}^n p(u,\leq k)^3+\binom{n}{k}n\right)$ complexity, where $ p(u,\leq k)$ counts the number of partitions of a positive integer $u$ into at most $k$ parts. The latter constructs an $n$-th degree polynomial via Vieta's formulas, whose roots correspond to the hidden multiset elements. Additionally, the discussion about the homogeneous symmetric polynomial rings is of independent interest. |
| title | Deterministic Algorithms to Solve the $(n,k)$-Complete Hidden Subset Sum Problem |
| topic | Combinatorics Number Theory |
| url | https://arxiv.org/abs/2412.04967 |