Modular inverse is known to be computable by Extended Euclidean algorithm which is the reaping the rewards of computing the GCD of two numbers or proving two numbers are coprime.
If we already know the numbers $a,q$ are coprime then do we know any better way to compute $a^{-1}\bmod q$ without Euclidean algorithm?
Essentially can we solve the integer program:
\begin{gather*} \exists u,v\in\mathbb Z \\ -q/2<u<q/2 \\ -a/2<v<a/2 \\ au+qv=1 \end{gather*}
without LLL algorithm?
Why cannot we think differently than the Euclidean algorithm? Is there any barrier?
Implicit in the question is why cannot we NC reduce Extended GCD algorithm to GCD computation itself as we can replace last constraint by $$au+qv=g$$ where $g$ now is $\operatorname{GCD}(a,q)$ (now assumed may not be coprime)?
$NC$ stands for Nick's class. Essentially Euclidean algorithm is performed on $O(n)$ sequential steps where $n$ is number of bits in $a$ and $q$ on a single processor. Can we increase the number of processors to $poly(n)$ and reduce the number of steps to $O(poly(\log n))$? This question is captured by the class $NC$.
