Title: Design alternatives of Euclidian greatest common divisor with enhanced architecture

Authors: Qasem Abu Al-Haija; Mohammad M. Asad; Ibrahim Marouf; Mahmoud A. Smadi

Addresses: Department of Electrical Engineering, King Faisal University, Saudi Arabia ' Department of Electrical Engineering, King Faisal University, Saudi Arabia ' Department of Electrical Engineering, King Faisal University, Saudi Arabia ' Department of Electrical Engineering, Hashemite University, Jordan

Abstract: In this paper, we proposed different comparable reconfigurable hardware implementations for greatest common divisor (GCD) and least common multiple (LCM) coprocessors using Euclid's method and plus-minus method with variable datapath sizes. The proposed designs utilised Altera Cyclone IV FPGA family with target chip device EP4CGX-22CF19C7 along with Quartus II simulation package. Also, the proposed designs were synthesised and benchmarked in terms of the maximum operational frequency, the total path delay, the total design area and the total thermal power dissipation. Thus, plus-minus method proved its enhanced performance by speeding up the operational frequency recoding around 142 MHz of data processing frequency with is as twice as its counterpart for Euclid's method while reducing the total path delay by almost 50% compared to Euclid's method. However, Euclid's method listed less hardware utilisation and power dissipation with almost 36% and 10% less than the values for plus-minus method respectively. Consequently, plus-minus method can be efficiently employed to enhance the speed of computation for many GCD-based applications such embedded system designs for public key cryptography.

Keywords: number theory; greatest common divisor; GCD; Euclidian GCD; least common multiple; LCM; plus-minus GCD; field programmable gate arrays; FPGA; integrated circuit synthesis; Altera Cyclone IV FPGA kit; critical path delay; FPGA thermal power dissipation; logic elements.

DOI: 10.1504/IJCAET.2020.110480

International Journal of Computer Aided Engineering and Technology, 2020 Vol.13 No.4, pp.425 - 436

Accepted: 18 Jan 2018
Published online: 22 Oct 2020 *

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