<p>Despite centuries of search extended <span class="math-container">$GCD$</span> is known to accommodate one algorithm which is the Euclidean algorithm (the solution through Integer Linear Programming which needs basis reduction goes through a step similar to Euclidean algorithm).</p>
<p>Is there evidence that extended <span class="math-container">$GCD$</span> might be in <span class="math-container">$TC^0$</span>?</p>

CC BY-SA 4.0
2024-05-30T18:13:42.133Z
IIRC even just gcd (let alone extended gcd) is not known to be in NC, and TC0 is contained in NC1. So...what kind of evidence would you hope for?
Joshua Grochow
CC BY-SA 4.0
2024-05-30T18:17:53.097Z
GCD on two numbers seems to be a minimal non trivial operation on two numbers which is more complex than the TC^0 operation of multiplication of two numbers.
Turbo
<cc.complexity-theory><ds.algorithms><nt.number-theory>
Evidence extended GCD is in $TC^0$
Turbo
# Evidence extended GCD is in $TC^0$

(Asked by: username_0 on 2024-05-30)

Despite centuries of search extended $GCD$ is known to accommodate one algorithm which is the Euclidean algorithm (the solution through Integer Linear Programming which needs basis reduction goes through a step similar to Euclidean algorithm).

Is there evidence that extended $GCD$ might be in $TC^0$?

**Tags:** cc.complexity-theory, ds.algorithms, nt.number-theory

> **Comments:**
> **username_1**: IIRC even just gcd (let alone extended gcd) is not known to be in NC, and TC0 is contained in NC1. So...what kind of evidence would you hope for?  
> **username_0**: GCD on two numbers seems to be a minimal non trivial operation on two numbers which is more complex than the TC^0 operation of multiplication of two numbers.  

---

## 0 answers

