并行LLL算法研究综述  

Survey on Parallel LLL Algorithms

作　　者：刘洋[1] 陈经纬[2] 冯勇[2] 吴文渊[2] LIU Yang;CHEN Jingwei;FENG Yong;WU Wenyuan(School of Information Science and Engineering, Chongqing Jiaotong University, Chongqing 400074, China;Chongqing Key Lab of Automated Reasoning & Cognition, Chongqing Institute of Green and Intelligent Technology, Chinese Academy of Sciences, Chongqing 400714, China)

机构地区：[1]重庆交通大学信息科学与工程学院,重庆400074 [2]中国科学院重庆绿色智能技术研究院自动推理与认知重庆市重点实验室,重庆400714

出　　处：《计算机工程与应用》2019年第16期36-41,共6页Computer Engineering and Applications

基　　金：国家自然科学基金(No.11501540,No.11671377,No.61572024,No.11771421);中国科学院青年创新促进会项目(No.Y71A120D10)

摘　　要：Lenstra-Lenstra-Lovasz(LLL)格基约化算法自1982年被提出以来,已被成功应用于计算机代数、编码理论、密码分析、算法数论、整数规划等众多领域。经过三十多年的发展,串行LLL算法的理论分析和实际效率都已得到显著改进,但仍不能满足密码分析等领域处理较大规模问题的需要。因此,并行LLL算法研究被寄予厚望。对并行LLL算法的研究现状进行了综述,总结了当前并行LLL算法设计与分析中存在的问题和难点,并对其未来发展趋势进行了展望。Since 1982,the Lenstra-Lenstra-Lovasz(LLL)algorithm has been successfully applied in computer algebra,coding theory,cryptanalysis,algorithmic number theory,integer programming,etc.After over 30 years,both of theoretical and practical aspects of the sequential LLL algorithm have been significantly improved.However,it still does not satisfy the need of problems with large size,especially in cryptanalysis.Therefore,parallel LLL algorithms have its own importance.This paper surveys the state-of-the-art of parallel LLL algorithms,summarizes and analyzes the existing problems and difficulties for the current parallel LLL algorithms,and proposes the future directions for further study.

关 键 词：格 格基约化 LLL算法 并行计算 

分 类 号：TP311.1[自动化与计算机技术—计算机软件与理论]