计算机与数字工程2013，Vol.41Issue(2)：158-162,5.
基于DHSP的格上最短向量量子算法的研究
Research on Shortest Vector Problem of Quantum Algorithm Based on Dihedral Hidden Subgroup Problem
摘要
Abstract
The shortest vector problem is the basis of the public key cryptosystem based on grid. With improvement on Kupcrberg's algorithm, a DHSP algorithm is presented that runs in polynomial time. Based on the polynomial DHSP algorithm and Oded Regev's theory, a polynomial time quantum algorithm is proposed which solves the shortest vector problem. The algorithm runs in O(n3) with the factor of () (n3). Finally, a brief performance analysis about the method is made. This algorithm will have an important influence on the public key cryp-tosystem based on grid.关键词
DHSP/SVP/Oded RegevKey words
DHSP/ SVP/ Oded Regev分类
信息技术与安全科学引用本文复制引用
孙静,袁家斌,金广龙..基于DHSP的格上最短向量量子算法的研究[J].计算机与数字工程,2013,41(2):158-162,5.基金项目
NUAA Research Funding(编号:NP2011050)资助. （编号:NP2011050）
