文章基本信息

标题：Reviewing and Analyzing Efficient GCD/LCM Algorithms for Cryptographic Design
本地全文：下载
作者：Ibrahim Marouf ; Mohamad Musab Asad ; Qasem Abu Al-Haija 等
期刊名称：International Journal of New Computer Architectures and their Applications
印刷版ISSN：2220-9085
出版年度：2017
卷号：7
期号：1
页码：1-7
DOI：10.17781/P002301
出版社：Society of Digital Information and Wireless Communications
摘要：In this paper, we provide a practical review with numerical example and complexity analysis for greatest common divisor (GCD) and Least Common Multiple (LCM) algorithms that are commonly used in the computing coprocessors design such as Cryptoprocessor design. The paper discusses four common GCD algorithms: Dijkstra's algorithm, Euclidian algorithm, Binary GCD algorithm, Lehmers algorithm, and two LCM algorithms: LCM based Prime Factorizations algorithm and LCM based GCD reduction. It was found that Lehmers algorithm can be used efficiently to compute GCD and LCM with time complexity of 𝑶( 𝒏 𝒍𝒐𝒈(𝒏) ) which enhances the linear time (𝑶 (𝒏)) complexity of well-known Euclidian algorithm.