Title: Speeding up Euclid's GCD algorithm with no magnitude comparisons

Authors: Che Wun Chiou, Fu Hua Chou, Yun-Chi Yeh

Addresses: Department of Computer Science and Information Engineering, Ching Yun University, 229, Chien-Hsin Rd., Chung-Li 320, Taiwan. ' Department of Electronic Engineering, Ching Yun University, 229, Chien-Hsin Rd., Chung-Li 320, Taiwan. ' Department of Electronic Engineering, Ching Yun University, 229, Chien-Hsin Rd., Chung-Li 320, Taiwan

Abstract: Euclid|s Greatest Common Divisor (GCD) algorithm is an efficient approach for calculating multiplicative inversions. It relies mainly on a fast modular arithmetic algorithm to run quickly. A traditional modular arithmetic algorithm based on nonrestoring division needs a magnitude comparison for each iteration of shift-and-subtract operation. This process is time consuming, since it requires magnitude comparisons for every computation iteration step. To eradicate this problem, this study develops a new fast Euclidean GCD algorithm without magnitude comparisons. The proposed modular algorithm has an execution time that is about 33% shorter than the conventional modular algorithm.

Keywords: greatest common divisor; GCD; modular arithmetic; public key cryptosystems; multiplicative inversions; division; Euclid; cryptography; security.

DOI: 10.1504/IJICS.2010.031855

International Journal of Information and Computer Security, 2010 Vol.4 No.1, pp.1 - 8

Published online: 26 Feb 2010 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article