<aside> 😀
</aside>
一个常规的0-1子集和问题(0-1 subset sum problem) 的场景为(1)式, 其中xi∈{0,1},我们需要根据h和$(\alpha _0, \alpha _1.,..\alpha _n)$ 的值恢复出(xo, x1.... xn)的值
$$ h=x_0*\alpha_0+x_1*\alpha_1十x_2*\alpha_2+...+x_n*\alpha_n\ \ (1) $$
此时如果将表达式转移到模下的同余式
$$ h\equiv x_0*\alpha_0+x_1*\alpha_1十x_2*\alpha_2+...+x_n*\alpha_n $$
且$(\alpha _0, \alpha _1.,..\alpha _n)$ 的的值也未知(即我们需要根据h的值恢复出$(\alpha _0, \alpha _1.,..\alpha _n)$ 和(xo,x1...xn的值),此时该问题则变成了一个隐式子集和问题(hidden subset sum problem)
该问题可以通过 Nguyen-Stern 算法求解,即通过构造两次垂直格的形式进行 [LLL 格基规约]
<aside> 👉 文献A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem
</aside>