Come trovare l'inverso di elementi in un file $\mathbb{Z}_n$ gruppo?

Aug 16 2020

Supponiamo che io abbia un elemento $a\in\mathbb{Z}_n$ dove $n$ è migliaia di cifre (base 10) e $\gcd(a,n)=1$. Esiste un modo computazionalmente efficiente per trovare l'inverso di$a$? o semplicemente in qualsiasi modo per trovare l'inverso di$a$ qualche tempo in questo decennio?

Modifica 1: sono un fan di Python se desideri rispondere con un algoritmo reale.

Aggiornamento: l'algoritmo euclideo esteso lo farà (Python sotto):

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

Risposte

3 JCAA Aug 16 2020 at 17:39

L'algoritmo euclideo è molto veloce. https://en.m.wikipedia.org/wiki/Euclidean_algorithm