非常に大きな要素の逆を見つける方法 $\mathbb{Z}_n$ グループ?

Aug 16 2020

私が要素を持っているとしましょう $a\in\mathbb{Z}_n$ どこ $n$ は数千桁(基数10)であり、 $\gcd(a,n)=1$。の逆を見つける計算効率の良い方法はありますか$a$?またはの逆を見つけるための任意の方法$a$ この10年のいつか?

編集1:実際のアルゴリズムで答えたいのなら、私はPythonのファンです。

更新:拡張ユークリッドアルゴリズムがそれを行います(以下の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