Survey on Parallel LLL Algorithms

doi:10.3778/j.issn.1002-8331.1903-0355

Computer Engineering and Applications ›› 2019, Vol. 55 ›› Issue (16): 36-41.DOI: 10.3778/j.issn.1002-8331.1903-0355

Previous Articles Next Articles

Survey on Parallel LLL Algorithms

LIU Yang, CHEN Jingwei, FENG Yong, WU Wenyuan

1.School of Information Science and Engineering, Chongqing Jiaotong University, Chongqing 400074, China
2.Chongqing Key Lab of Automated Reasoning & Cognition, Chongqing Institute of Green and Intelligent Technology, Chinese Academy of Sciences, Chongqing 400714, China

Online:2019-08-15 Published:2019-08-13

并行LLL算法研究综述

刘洋，陈经纬，冯勇，吴文渊

1.重庆交通大学信息科学与工程学院，重庆 400074
2.中国科学院重庆绿色智能技术研究院自动推理与认知重庆市重点实验室，重庆 400714

Abstract

Abstract: 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.

Key words: lattice, lattice basis reduction, LLL algorithm, parallel computing

摘要： Lenstra-Lenstra-Lovasz（LLL）格基约化算法自1982年被提出以来，已被成功应用于计算机代数、编码理论、密码分析、算法数论、整数规划等众多领域。经过三十多年的发展，串行LLL算法的理论分析和实际效率都已得到显著改进，但仍不能满足密码分析等领域处理较大规模问题的需要。因此，并行LLL算法研究被寄予厚望。对并行LLL算法的研究现状进行了综述，总结了当前并行LLL算法设计与分析中存在的问题和难点，并对其未来发展趋势进行了展望。

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

LIU Yang, CHEN Jingwei, FENG Yong, WU Wenyuan. Survey on Parallel LLL Algorithms[J]. Computer Engineering and Applications, 2019, 55(16): 36-41.

刘洋，陈经纬，冯勇，吴文渊. 并行LLL算法研究综述[J]. 计算机工程与应用, 2019, 55(16): 36-41.

[1]	ZHANG Chengling, LI Jinjin, LIN Yidong. Attribute Reduction in Formal Contexts Based on OE-Concept Lattices [J]. Computer Engineering and Applications, 2021, 57(15): 82-89.
[2]	YANG Geying, SHEN Xiajiong, SHI Xianjin, ZHANG Lei. Visualization of Association Rules in Context of Concept Lattices [J]. Computer Engineering and Applications, 2021, 57(1): 84-91.
[3]	DU Wei, FU You. GPU-Based Least Squares Monte Carlo Algorithm Option Pricing [J]. Computer Engineering and Applications, 2020, 56(4): 225-229.
[4]	JIN Zhiyan, YANG Lei, LIN Junmin, WANG Zhe. Communication Avoiding Algorithm of Generalized Conjugate Residual Method [J]. Computer Engineering and Applications, 2020, 56(3): 74-79.
[5]	LIU Jiahua, CHEN Jingyu. Design of Multi-core Parallel Spiking Neural Network Simulator [J]. Computer Engineering and Applications, 2020, 56(22): 244-250.
[6]	YE Qing, YANG Xiaomeng, QIN Panke, ZHAO Zongqu, TANG Yongli. Novel Against Quantum Attacks Group Signature Scheme Based on NTRU Lattice [J]. Computer Engineering and Applications, 2020, 56(2): 89-96.
[7]	SHE Yanhong, HU Mengting, HE Xiaoli, ZENG Wanglin. Comparative Study Between Two Multigranulation Formal Concept Analysis Models [J]. Computer Engineering and Applications, 2020, 56(10): 51-55.
[8]	WU Yangyang, TANG Jianguo. Research Progress of Attribute Reduction Based on Rough Set in Context of Big Data [J]. Computer Engineering and Applications, 2019, 55(6): 31-38.
[9]	HE Xiaoli, LIU Huali, LIU Yaoyao. Interval Formal Concept Analysis Approach for Multigranulation Data [J]. Computer Engineering and Applications, 2019, 55(19): 52-57.
[10]	ZENG Youling, CHEN Gengduo, XIONG Wei, LI Zhe. Parallel Design of FBP Reconstruction Algorithm for CT Image Based on Spark [J]. Computer Engineering and Applications, 2019, 55(10): 218-224.
[11]	QU Hanhua1, HUI Jianzhong1, HE Xianfeng2, WANG Muhua1, HE Xiaofeng1, FENG De’en1. Formal concept analysis model of meteorological services [J]. Computer Engineering and Applications, 2018, 54(9): 257-264.
[12]	LIU Rentao1，2, CHEN Wei1. Application of nearest-neighbor searching employed in modeling of porous material with lattice model [J]. Computer Engineering and Applications, 2018, 54(7): 239-244.
[13]	WEI Zijin1，2，3, XIAO Li2，3. Parallel dynamic level-of-detail construct algorithm based on domain decomposition [J]. Computer Engineering and Applications, 2018, 54(6): 168-177.
[14]	QIN Jinbo1, ZENG Zhiqiang1，2, LIANG Ji1, YANG Mingxiang2, ZHANG Jian1. Review of application GPU technology in hydraulic parallel optimization calculation [J]. Computer Engineering and Applications, 2018, 54(3): 23-29.
[15]	HUANG Fei1, LIAO Zuhua2. Measure of fuzzy filters and fuzzy prime filters on lattices [J]. Computer Engineering and Applications, 2018, 54(24): 26-33.

Survey on Parallel LLL Algorithms

并行LLL算法研究综述

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics