To search for a target n-product Boolean vector of fixed weight d, we propose an important method involving the notion of a fixed-weight "vector label" accompanied with a vector label restoration algorithm. ...To search for a target n-product Boolean vector of fixed weight d, we propose an important method involving the notion of a fixed-weight "vector label" accompanied with a vector label restoration algorithm. Based on these, we present a new quantum algorithm designed to search for a fixed-weight target whose computation complexity, specifically O ((Cdn+1)^(1/2)) , is better than that for a classical algorithm. Finally, we use the procedure to search for the NTRU private key as an example to verify the efficiency of the new algorithm in searching for fixed-weight target solutions.展开更多
基金Supported by the National Natural Science Foundation of China under Grant No.60434030(国家自然科学基金)the National High-Tech Research and Development Plan of China under Grant No.2006AA01Z218(国家高技术研究发展计划(863))the National Research Foundation for the Doctoral Program of Higher Education of China under Grant No.20050335020(国家教育部博士点基金)
文摘To search for a target n-product Boolean vector of fixed weight d, we propose an important method involving the notion of a fixed-weight "vector label" accompanied with a vector label restoration algorithm. Based on these, we present a new quantum algorithm designed to search for a fixed-weight target whose computation complexity, specifically O ((Cdn+1)^(1/2)) , is better than that for a classical algorithm. Finally, we use the procedure to search for the NTRU private key as an example to verify the efficiency of the new algorithm in searching for fixed-weight target solutions.
