매우 큰 요소의 역을 찾는 방법 $\mathbb{Z}_n$ 그룹?

Aug 16 2020

요소가 있다고 가정합니다. $a\in\mathbb{Z}_n$ 어디 $n$ 수천 자리 (밑수 10)이며 $\gcd(a,n)=1$. 역을 찾는 계산적으로 효율적인 방법이 있습니까?$a$? 또는 그 반대를 찾는 방법$a$ 이번 10 년 동안?

편집 1 : 실제 알고리즘으로 대답하고 싶다면 파이썬 팬입니다.

업데이트 : 확장 된 유클리드 알고리즘이이를 수행합니다 (아래의 Python).

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

답변

3 JCAA Aug 16 2020 at 17:39

유클리드 알고리즘은 매우 빠릅니다. https://en.m.wikipedia.org/wiki/Euclidean_algorithm