Extended Euclidean Algorithm (ExtendedGCD)
Category: Local Optimality
Input
Two $n$-bit positive integers $a$ and $b$.
Problem
Compute integers $s$ and $t$ such that $as + bt = \gcd(a, b)$.
Status
Open (Borodin, von zur Gathen, and Hopcroft [1]).
Remarks
The analogous problem for $n^\text{th}$ degree polynomials is in $\NC$ [1]. Deng shows several other problems are $\NC$-equivalent to a closely related problem [2]. Two of these are expanding the continued fraction of the ratio of two integers and computing the sequence of convergents of two integers. See also Shallcross, Pan, and Lin-Kriz [3] and the remarks for Opt2ILP and IntegerGCD.
References
- A. Borodin, J. von zur Gathen, and J. E. Hopcroft (1982). Fast parallel matrix and GCD computations.
- X. Deng (1989). On the parallel complexity of integer programming.
- D. Shallcross, V. Pan, and Y. Lin-Kriz (1993). The NC equivalence of planar integer linear programming and Euclidean GCD.
- Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. Problem B.5.1.