广义模子集和问题及其格基归约分析

EMSSP and its lattice reduction analysis

将子集和问题推广到广义模子集和问题 ,并应用格基归约方法进行了分析 ,证明了几乎所有密度d小于 0 488…的广义模子集和问题都可通过仅调用LatticeOracle在多项式时间内解出 .

The SSP (subset su m problem) is extended to the EMSSP (extended modular subset sum problem), and i ts lattice basis reduction analysis is presneted. It is proved that almost all E MSSPs of density d< 0 488… can be solved in polynomial time if it coul d invoke a polynomial time algorithm for finding the shortest non-zero vector i n a lattice.