Como encontrar o inverso dos elementos em um grande $\mathbb{Z}_n$ grupo?

Aug 16 2020

Suponha que eu tenha um elemento $a\in\mathbb{Z}_n$ Onde $n$ tem milhares de dígitos (base 10) e $\gcd(a,n)=1$. Existe uma maneira computacionalmente eficiente de encontrar o inverso de$a$? ou qualquer maneira de encontrar o inverso de$a$ alguma vez nesta década?

Edit 1: Eu sou um fã de python, se você quiser responder com um algoritmo real.

Atualização: O Algoritmo Euclidiano estendido fará isso (Python abaixo):

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

Respostas

3 JCAA Aug 16 2020 at 17:39

O algoritmo euclidiano é muito rápido. https://en.m.wikipedia.org/wiki/Euclidean_algorithm