Title :
A Circuit for GCD and Extended GCD Calculation With Unlimited Precision
Author :
Bouraoui, R. ; Guyot, A.
Author_Institution :
TIM3, IMAG, Grenoble, France
Abstract :
In this paper, we present the architecture and implementation of a new algorithm to find the greatest common divisor (GCD) and extended GCD of very large integers (>; 600 decimal digits). The method uses an internal radix 2 redundant representation and supports multiple precision. In addition, the design methodology was to find the best trade-offs between computation time and area.
Keywords :
integrated circuit design; redundancy; GCD circuit; extended GCD calculation; greatest common divisor; internal radix 2 redundant representation; multiple precision; unlimited precision; very large integers; Algebra; Application software; Arithmetic; Circuits; Computer architecture; Cost function; Cryptography; Design methodology; Hardware; Switches; GCD; extended GCD; most significant digit first algorithm; redundant number system; very large integers;
Conference_Titel :
Solid-State Circuits Conference, 1992. ESSCIRC '92. Eighteenth European
Conference_Location :
Copenhagen
Print_ISBN :
87-984232-0-7
DOI :
10.1109/ESSCIRC.1992.5468172
