Çok büyük bir elementin tersi nasıl bulunur $\mathbb{Z}_n$ grup?

Question

Bir elementim olduğunu varsayalım $a\in\mathbb{Z}_n$ nerede $n$ binlerce basamaktır (10 tabanı) ve $\gcd(a,n)=1$. Tersini bulmanın hesaplama açısından verimli bir yolu var mı?$a$? veya tersini bulmanın herhangi bir yolu$a$ bu on yılda bir süre?

Düzenleme 1: Gerçek bir algoritma ile cevap vermek isterseniz ben bir python hayranıyım.

Güncelleme: Genişletilmiş Öklid Algoritması bunu yapacak (aşağıdaki Python):

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

Öklid algoritması çok hızlıdır. https://en.m.wikipedia.org/wiki/Euclidean_algorithm