Document Type
Article
Publication Date
2-1-2005
Publication Title
Journal of Algorithms
Abstract
This paper describes the first algorithm to compute the greatest common divisor (GCD) of two n-bit integers using a modular representation for intermediate values U, V and also for the result. It is based on a reduction step, similar to one used in the accelerated algorithm [T. Jebelean, A generalization of the binary GCD algorithm, in: ISSAC '93: International Symposium on Symbolic and Algebraic Computation, Kiev, Ukraine, 1993, pp. 111–116; K. Weber, The accelerated integer GCD algorithm, ACM Trans. Math. Softw. 21 (1995) 111–122] when U and V are close to the same size, that replaces U by (U-bV)/p, where p is one of the prime moduli and b is the unique integer in the interval (-p/2,p/2) such that b=UV ^-1(mod p) . When the algorithm is executed on a bit common CRCW PRAM with O(n log n log log log n) processors, it takes O(n) time in the worst case. A heuristic model of the average case yields O(n/log n) time on the same number of processors.
Repository Citation
Weber, Kenneth; Trevisan, Vilmar; and Martins, Luiz Felipe, "A Modular Integer GCD Algorithm" (2005). Mathematics and Statistics Faculty Publications. 156.
https://engagedscholarship.csuohio.edu/scimath_facpub/156
DOI
10.1016/j.jalgor.2004.06.006
Version
Postprint
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Volume
54
Issue
2
Comments
Research reported here was done primarily at UFRGS - Instituto de Matematica. First author funded by CNPq grant number 301314194-2. Second author partially funded by FAPERGS, grant number 011316.6.