Cách tìm nghịch đảo của các phần tử trong rất lớn $\mathbb{Z}_n$ nhóm?
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
Thuật toán Euclid rất nhanh. https://en.m.wikipedia.org/wiki/Euclidean_algorithm