Research On Optimization And Application Of Heuristic Sieve Methods-GaussSieve Algorithm

Lattice theory has an important position in cryptography,and the lattice calculation problem is used to design new cryptographic systems.In addition,the related algorithms of lattice theory also play an important role in other fields.They can be used to solve subset sum problems.In the paper,we study the optimization heuristic sieve method—GaussSieve algorithm,and apply it to solving subset sum problems to do the following work:1)Based on the Cross-polytope position-sensitive hashing(CP-LSH)proposed by Thijs Laarhoven scholars,we construct a 2-norm-based hash function(ED)to classify the vector to get ED+CP-LSH,And used to optimize GaussSieve to reduce the time complexity of the algorithm screening step.2)The low-weight subset and problem can be equivalent to the shortest non-zero vector problem.Therefore,we propose to construct the lattice base and redefine the vector length calculation formula to apply GaussSieve to solve the subset sum problem,and use ED+CP-LSH to optimize the solution speed,so as to solve the subset sum problem more effectively.The 40-dimensional high knapsack density subset sum problem are used to experimentally verify the performance of GaussSieve to solve the subset sum problem,and it is concluded that it is more effective than the LLL algorithm.Finally,analyze and compare the acceleration effect of ED+CP-LSH and CP-LSH under different parameter combinations on GaussSieve's solving subset sum problem.It is concluded that ED+CP-LSH has better classification capabilities for vectors to reduce algorithm search vectors.Therefore,it performs better than CP-LSH under different parameter combinations.