Jak znaleźć odwrotność elementów w bardzo dużym pliku $\mathbb{Z}_n$ Grupa?

Aug 16 2020

Załóżmy, że mam element $a\in\mathbb{Z}_n$ gdzie $n$ to tysiące cyfr (podstawa 10) i $\gcd(a,n)=1$. Czy istnieje skuteczny obliczeniowo sposób na znalezienie odwrotności$a$? lub po prostu jakikolwiek sposób, aby znaleźć odwrotność$a$ jakiś czas w tej dekadzie?

Edycja 1: Jestem fanem Pythona, jeśli chcesz odpowiedzieć za pomocą rzeczywistego algorytmu.

Aktualizacja: Rozszerzony algorytm euklidesowy zrobi to (Python poniżej):

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

Odpowiedzi

3 JCAA Aug 16 2020 at 17:39

Algorytm euklidesowy jest bardzo szybki. https://en.m.wikipedia.org/wiki/Euclidean_algorithm