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)?