Comment trouver l'inverse des éléments dans un très grand $\mathbb{Z}_n$ groupe?

Question

Supposons que j'ai un élément $a\in\mathbb{Z}_n$ où $n$ correspond à des milliers de chiffres (base 10) et $\gcd(a,n)=1$. Existe-t-il un moyen efficace de trouver l'inverse de$a$? ou n'importe quel moyen de trouver l'inverse de$a$ quelque temps dans cette décennie?

Edit 1: Je suis fan de python si vous souhaitez répondre avec un algorithme réel.

Mise à jour: l' algorithme euclidien étendu le fera (Python ci-dessous):

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

L'algorithme euclidien est très rapide. https://en.m.wikipedia.org/wiki/Euclidean_algorithm