Find inverse of elements in a very large $\mathbb{Z}_n$ group

Question

Suppose I have an element $a\in\mathbb{Z}_n$ where $n$ is thousands of digits(base 10) and $\gcd(a,n)=1$. Is there a computationally efficient way of finding the inverse of $a$? or just any way to find the inverse of $a$ some time in this decade?

Edit 1: I am a fan of python if you would like to answer with an actual algorithm.

Update: The extended Euclidean Algorithm will do it (Python below):

def inverse(a, n):
    t    = 0
    newt = 1
    r    = n
    newr = a

    while newr != 0:
        quotient  = r//newr
        (t, newt) = (newt, t - quotient*newt) 
        (r, newr) = (newr, r - quotient*newr)

    if r > 1:
        return "a is not invertible"
    if t < 0:
        t = t + n

    return t

Answer 1

Euclidean algorithm is very fast. https://en.m.wikipedia.org/wiki/Euclidean_algorithm