Wie man die Umkehrung von Elementen in einem sehr großen findet $\mathbb{Z}_n$ Gruppe?

Question

Angenommen, ich habe ein Element $a\in\mathbb{Z}_n$ wo $n$ ist Tausende von Ziffern (Basis 10) und $\gcd(a,n)=1$. Gibt es eine rechnerisch effiziente Möglichkeit, die Umkehrung von zu finden?$a$? oder einfach irgendein Weg, um das Gegenteil von zu finden$a$ irgendwann in diesem Jahrzehnt?

Edit 1: Ich bin ein Fan von Python, wenn Sie mit einem tatsächlichen Algorithmus antworten möchten.

Update: Der erweiterte euklidische Algorithmus wird es tun (Python unten):

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

Der euklidische Algorithmus ist sehr schnell. https://en.m.wikipedia.org/wiki/Euclidean_algorithm