The fast Euclidean algorithm runs in time $O(M(n)\log n)$, where $n=\log q,$ and $M(n)$ is the time to multiply two $n$-bit integers. This yields a bit-complexity of $$ O(n\log^2 n\log\log n) $$ for the time to compute the inverse of an integer modulo $q$, using the standard Schonhage-Strassen algorithm for multiplying integers (a slightly better asymptotic result can be obtained using Furer's multiplication algorithm).
To understand the basic idea behind the fast Euclidean algorithm, recall that the standard Euclidean algorithm computes the (extended) gcd of two integers $r_0 > r_1$ by successively computing $m_i=\lfloor r_{i-1}/r_i\rfloor$ and setting $$ r_{i+1} = r_{i-1} - m_ir_i, $$ until it obtains $r_{k+1} = 0$, at which point $r_k = \gcd (r_0, r_1)$. This can be expressed in matrix form as $$ R_1 = \begin{bmatrix} r_0\newline r_1 \end{bmatrix};\qquad R_{i+1} = \begin{bmatrix} r_i\newline r_{i+1}\end{bmatrix} = M_iR_i;\qquad M_i=\begin{bmatrix} 0&1\newline 1&-m_i \end{bmatrix}, $$ and if we compute the matrix $S_k=M_kM_{k-1}\ldots M_1$, we have $R_{k+1}=S_kR_1$ which expresses the entry $r_k=\gcd(r_0,r_1)$ as a linear combination of $r_0$ and $r_1$. Assuming this gcd is 1, we can then read off the inverse of $r_1$ modulo $r_0$ (and vice versa) from the top row of $S_k$.
As described above, this involves $O(k)$ arithmetic operations on integers of size $O(n)$, and one can show that $k=O(n)$, leading to a running time that is roughly quadratic in $n$. The fast Euclidean algorithm achieves a quasi-linear running time by only computing $O(\log n)$ of the matrices $S_i$. Roughly speaking (and ignoring many important details), this is done by directly computing $S_{k/2}$ using what is known as a "half-gcd" algorithm, computing $R_{k/2+1}=S_{k/2}R_1$, and then proceeding recursively. The half-gcd algorithm, in turn, works by recursively calling itself. The depth of the recursion is $O(\log n)$ and this yields an $O(M(n)\log n)$ complexity bound.
This algorithm also works over polynomial rings and is often described in this setting. Further details can be found in the (incomplete) list of references below:
Chapter 11 of von zur Gathen and Gerhard, "Modern Computer Algebra," Cambridge University Press, 2003.
Chapter 2 of Yap, "Fundamental Problems of Algorithmic Algebra," Oxford University Press, 2000.
N. Moller, "On Schonhage's algorithm and subquadratic integer GCD computation," Mathematics of Comutation 77(261), pp. 589-607 (2008).
Stehle and Zimmerman, "A binary recursive GCD algorithm,algorithm," ANTS-VI, LCNS 3076, pp. 411-425, 2004.
