← All Problems
Open

Integer Greatest Common Divisor (IntegerGCD)

Category: Local Optimality

Input

Two $n$-bit positive integers $a$ and $b$.

Problem

Compute the greatest common divisor (gcd) of $a$ and $b$, denoted $\gcd(a, b)$.

Status

Open (von zur Gathen [1]).

Remarks

For $n^\text{th}$ degree polynomials $p, q \in \Q[x]$, computing $\gcd(p, q)$ is in $\NC^2$ via an $\NC^1$ reduction to Determinant (Cook and Sethi [2], Borodin, Cook, and Pippenger [3]). IntegerGCD is $\NC^1$ reducible to SV2 [1]. Kannan, Miller, and Rudolph give a sublinear CRCW-PRAM algorithm for computing the gcd of two $n$-bit integers [4]. Their algorithm requires $O(n \log \log n / \log n)$ time and $n^2 (\log n)^2$ processors. Chor and Goldreich give a CRCW-PRAM algorithm for the same problem with time bound $O(n / \log n)$ and processor bound $n^{1+\epsilon}$, for any positive constant $\epsilon$ [5].

Sorenson presents an algorithm called the $k$-ary gcd algorithm [6][7] whose sequential version is practical and whose parallel version has bounds that match those given in [5]. Also see (Deng [8], Lin-Kriz and Pan [9], Shallcross, Pan, and Lin-Kriz [10]) for additional research on IntegerGCD and related problems.

More recent developments include parallel algorithms in EREW PRAM in 2009 by Sorenson[11] , and for the GCD of many integers in 2017 by Sedjelmaci [12]. Both, however, still have a $\widetilde{\Omega}(n)$ time bound and the hardness of IntegerGCD remains open.

References

  1. J. von zur Gathen (1984). Parallel algorithms for algebraic problems.
  2. S. A. Cook and R. Sethi (1976). Storage requirements for deterministic polynomial time recognizable languages.
  3. A. Borodin, S. A. Cook, and N. J. Pippenger (1983). Parallel computation for well-endowed rings and space-bounded probabilistic machines.
  4. R. Kannan, G. L. Miller, and L. Rudolph (1987). Sublinear parallel algorithm for computing the greatest common divisor of two integers.
  5. B. Chor and O. Goldreich (1990). An improved parallel algorithm for integer GCD.
  6. J. Sorenson (1991). The k-ary GCD algorithm.
  7. J. Sorenson. Two fast GCD algorithms (1992). Manuscript, Department of Mathematics and Computer Science, Bulter University, Indianapolis, IN, January 1992..
  8. X. Deng (1989). On the parallel complexity of integer programming.
  9. Y. Lin-Kriz and V. Pan (1992). On parallel complexity of integer linear programming, GCD and the iterated mod function.
  10. D. Shallcross, V. Pan, and Y. Lin-Kriz (1993). The NC equivalence of planar integer linear programming and Euclidean GCD.
  11. J. P. Sorenson (2009). A randomized sublinear time parallel GCD algorithm for the EREW PRAM.
  12. S. M. Sedjelmaci (2017). Two Fast Parallel GCD Algorithms of Many Integers.
  13. Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. Problem B.5.3.

Related Problems