Cách tìm nghịch đảo của các phần tử trong rất lớn $\mathbb{Z}_n$ nhóm?

Aug 16 2020

Giả sử tôi có một phần tử $a\in\mathbb{Z}_n$ Ở đâu $n$ là hàng nghìn chữ số (cơ số 10) và $\gcd(a,n)=1$. Có cách nào hiệu quả về mặt tính toán để tìm ra nghịch đảo của$a$? hoặc bất kỳ cách nào để tìm ra nghịch đảo của$a$ một số thời điểm trong thập kỷ này?

Chỉnh sửa 1: Tôi là một fan hâm mộ của python nếu bạn muốn trả lời bằng một thuật toán thực tế.

Cập nhật: Thuật toán Euclidean mở rộng sẽ thực hiện điều đó (Python bên dưới):

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

Trả lời

3 JCAA Aug 16 2020 at 17:39

Thuật toán Euclid rất nhanh. https://en.m.wikipedia.org/wiki/Euclidean_algorithm