A new parallel lattice reduction algorithm for BKZ reduced bases  

作　　者：LIU XiangHui FANG Xing WANG Zheng XIE XiangHui 

机构地区：[1]Department of Applied Mathematics,Zhengzhou Information Science and Technology Institute [2]State Key Laboratory of Mathematical Engineering and Advanced Computing

出　　处：《Science China(Information Sciences)》2014年第9期132-141,共10页中国科学（信息科学）（英文版）

基　　金：supported by National Natural Science Foundation of China(Grant No.61003291);Open Project Program of the State Key Laboratory of Mathematical Engineering and Advanced Computing(Grant No.2013A03)

摘　　要：In order to implement the original BKZ algorithm in parallel,we describe it in terms of parallelism and give its parallel implementation scheme. Then we analyze the efficiency of algorithm＇s parallel implementation and show that the speedup factor of BKZ algorithm in parallel is extremely low. Therefore we present a new parallel lattice reduction algorithm suitable for multiprocessor computer architecture. The new algorithm can obtain a BKZ reduced basis and the parallel speedup is effective. Also with the practical results,although the computational complexity increases compared with the original BKZ algorithm,we still indicate that the new algorithm performs well in parallel and the time cost in parallel is less. At the same time,we show that the length of the shortest vector is smaller.In order to implement the original BKZ algorithm in parallel,we describe it in terms of parallelism and give its parallel implementation scheme. Then we analyze the efficiency of algorithm＇s parallel implementation and show that the speedup factor of BKZ algorithm in parallel is extremely low. Therefore we present a new parallel lattice reduction algorithm suitable for multiprocessor computer architecture. The new algorithm can obtain a BKZ reduced basis and the parallel speedup is effective. Also with the practical results,although the computational complexity increases compared with the original BKZ algorithm,we still indicate that the new algorithm performs well in parallel and the time cost in parallel is less. At the same time,we show that the length of the shortest vector is smaller.

关 键 词：lattice reduction BKZ algorithm Goldstein-type lattices parallel algorithm multiprocessor computer architecture 

分 类 号：TN918.1[电子电信—通信与信息系统]