Title: A novel fast hybrid GCD computation algorithm

Authors: Faraoun Kamel Mohamed

Addresses: EEDIS Laboratory, Department of Computer Science, Faculty of Technology, Djilalli Liabbes University, Sidi Bel Abbès, 22000, Algeria

Abstract: We propose a novel algorithm for integer's greatest common divisor (GCD) computation that hybridises both Euclidian and binary algorithms according to a new schema, in order to accelerate the GCD computation especially in the case of large bit difference between the two inputs. The proposed algorithm run slightly faster than existing algorithms and is very much easier to implement. We provide a simple proof of correctness for the algorithm, and we show that best performances can be achieved for large integers when subtraction operator complexity is relatively low with respect to the division one.

Keywords: GCD computation; greatest common divisor; Euclidian algorithms; binary algorithms; computational complexity; discrete mathematics.

DOI: 10.1504/IJCSM.2014.059380

International Journal of Computing Science and Mathematics, 2014 Vol.5 No.1, pp.37 - 47

Received: 11 Feb 2013
Accepted: 16 Jun 2013
Published online: 30 Jun 2014 *

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