Thuật toán Euclid mở rộng tính A^-1 MOD N:
Nhập vào số nguyên dương A và N để tính phần tử nghịch đảo
Thuật toán cài đặt Euclid mở rộng
Khởi tạo giá trị
- X[0] = A
- X[1] = N
- A[0] = 1
- A[1] = 0
- B[0] = 0
- B[1] = 1
- Y[0] = NULL
- Y[1] = X[0] / X[1]
Thuật toán
Thực hiện lặp cho đến khi X[i] = 1 hoặc X[i] = 0- X[i] = X[i-2] mod X[i-1]
- Y[i] = X[i-1] div X[i]
- A[i] = A[i-2] - (A[i-1]*Y[i-1]
- A[i] = B[i-2] - (B[i-1]*Y[i-1]
Nếu X[i] = 1
- B[i] < 0 trả về while(B[i] < 0) B[i] = B[i]+N;(cộng n lần N cho tới khi B[i] dương)
- B[i] >= 0 trả về B[i]
