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:

$$\exists u,v\in\mathbb Z$$ $$-q/2<u<q/2$$ $$-a/2<v<a/2$$ $$au+qv=1$$

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 $GCD(a,q)$ (now assumed may not be coprime)?