子集和组的求解以及真分式背包体制的攻破

Solving Subset Sum System Problem and Breaking Pure Fraction Knapsack Cryptosystem

本文采用概率的方法，证明了整数格中短向量‖Ｘ‖~２≤ｎ／２的期望个数是１＋２^（１．５４７２５－β）ｎ，β＝∑ｌｏｎｇ_２（ｍａｘａ_ｊｉ）／ｎ。本文修改了计算格归约基的Ｌ~３算法，用于解决一般的子集和组问题。本文还进一步分析了真分式背包体制的性能，介绍了使用修改的Ｌ~３算法攻击它的方法。

This paper shows that the expected number of short vectors in integer lattice is 1 + 2￣(1.54725-β)n,β=∑log_2(max a_ji)/n,by probability.The paper mends L￣3 lattice basis reduction algorithm to solve subset sum system problems.The paper further analyses the performance of the pure fraction knapsack cryptosystem,presents some methods to break them.