Cómo encontrar el inverso de elementos en un tamaño muy grande $\mathbb{Z}_n$ ¿grupo?

Aug 16 2020

Supongamos que tengo un elemento $a\in\mathbb{Z}_n$ dónde $n$ son miles de dígitos (base 10) y $\gcd(a,n)=1$. ¿Existe una forma computacionalmente eficiente de encontrar la inversa de$a$? o cualquier forma de encontrar la inversa de$a$ en algún momento de esta década?

Edición 1: soy un fanático de Python si desea responder con un algoritmo real.

Actualización: el algoritmo euclidiano extendido lo hará (Python a continuación):

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

Respuestas

3 JCAA Aug 16 2020 at 17:39

El algoritmo euclidiano es muy rápido. https://en.m.wikipedia.org/wiki/Euclidean_algorithm