तत्वों का विलोम कैसे पाया जाए $\mathbb{Z}_n$ समूह?

Question

मान लीजिए कि मेरे पास एक तत्व है $a\in\mathbb{Z}_n$ कहाँ पे $n$ हजारों अंक (आधार 10) और है $\gcd(a,n)=1$। क्या इसका उलटा खोजने का एक कम्प्यूटेशनल रूप से कुशल तरीका है$a$? या सिर्फ किसी भी तरह से उलटा खोजने के लिए$a$ इस दशक में कुछ समय?

संपादित 1: मैं अजगर का एक प्रशंसक हूं यदि आप एक वास्तविक एल्गोरिथ्म के साथ जवाब देना चाहते हैं।

अद्यतन: विस्तारित यूक्लिडियन एल्गोरिथ्म इसे करेगा (नीचे पायथन):

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

यूक्लिडियन एल्गोरिथ्म बहुत तेज है। https://en.m.wikipedia.org/wiki/Euclidean_algorithm