O35 — Greatest common divisors in NC

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Integers are supplied in binary; polynomial time means a polynomial number of classical bit operations in total input length. A function is in $\mathsf{NC}$ if a uniform family of Boolean circuits of polynomial size and depth $(\log L)^{O(1)}$ computes its output on inputs of bit length $L$; gates have bounded fan-in.

Statement recorded in the supplied source.

Is $(a,b)\mapsto\gcd(a,b)$ for positive binary integers in $\mathsf{NC}$? [S2]

Short English statement

Can integer greatest common divisors be computed with polynomially many parallel resources and polylogarithmic depth?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 8400040 (AMR-083-0040). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Leonard M. Adleman and Kevin S. McCurley, Open Problems in Number Theory Complexity, II, in Algorithmic Number Theory, LNCS 877 (1994), pp. 291--322, C35/O35, manuscript p. 22 (LNCS p. 312). https://mccurley.org/papers/open.ps.gz.