Cấu trúc dữ liệu và Giải thuật Bài 69: Lý thuyết số nâng cao - Thuật toán Euclid mở rộng và Nghịch đảo modulo.

Trong kiến trúc bảo mật backend, các hệ thống mã hóa hiện đại (như RSA, chữ ký số ECDSA, hay các giao thức xác thực token) thường xuyên phải thực hiện các phép tính số học trên một trường hữu hạn với số nguyên tố lớn ($MOD$). Tại đây, phép chia thông thường không tồn tại, và chúng ta buộc phải sử dụng Nghịch đảo modulo (Modular Multiplicative Inverse), được giải quyết tối ưu bằng Thuật toán Euclid mở rộng (Extended Euclidean Algorithm).

1. Bản chất của Nghịch đảo modulo và Thuật toán Euclid mở rộng

• Phép chia trong Modulo: Trong toán học modulo, bạn không thể tính trực tiếp biểu thức $a / b \pmod m$. Thay vào đó, ta phải nhân với phần tử nghịch đảo của $b$ (ký hiệu là $b^{-1}$), sao cho thỏa mãn điều kiện: $(b \cdot b^{-1}) \equiv 1 \pmod m$.

• Định lý Bézout: Thuật toán Euclid mở rộng không chỉ tìm ước chung lớn nhất $\gcd(a, b)$ mà còn giải phương trình Diophantus tuyến tính dạng $ax + by = \gcd(a, b)$. Khi $\gcd(a, m) = 1$, hệ số $x$ thu được chính là nghịch đảo modulo của $a$ dưới modulo $m$.

2. Triển khai Extended GCD và Modular Inverse bằng Golang

Dưới đây là mã nguồn chuẩn mực thực hiện thuật toán Euclid mở rộng và tìm nghịch đảo modulo bằng ngôn ngữ Go:

Go

package main

import "fmt"

// Thuật toán Euclid mở rộng trả về gcd(a, b) cùng với các hệ số x, y sao cho: a*x + b*y = gcd(a, b)
func extendedGCD(a, b int64) (int64, int64, int64) {
	if b == 0 {
		return a, 1, 0
	}
	gcd, x1, y1 := extendedGCD(b, a%b)
	x := y1
	y := x1 - (a/b)*y1
	return gcd, x, y
}

// Tính nghịch đảo modulo của a dưới modulo m
// Trả về -1 nếu nghịch đảo không tồn tại (khi gcd(a, m) != 1)
func ModInverse(a, m int64) int64 {
	gcd, x, _ := extendedGCD(a, m)
	if gcd != 1 {
		return -1 // Không tồn tại nghịch đảo
	}
	// Đảm bảo kết quả trả về là số dương trong khoảng [0, m-1]
	return (x%m + m) % m
}

func main() {
	var a int64 = 3
	var m int64 = 11

	inv := ModInverse(a, m)
	fmt.Printf("Nghịch đảo modulo của %d dưới modulo %d là: %d\n", a, m, inv)
	// Kiểm tra lại: (3 * 4) % 11 = 12 % 11 = 1 (Chính xác!)
}

3. Hiệu năng và Ứng dụng Thực tế

• Độ phức tạp thời gian: $O(\log(\min(a, m)))$, hoàn toàn tương đồng với tốc độ của thuật toán Euclid tìm ước chung lớn nhất, cho phép tính toán cực nhanh ngay cả với các số nguyên lớn.

• Ứng dụng trong Bảo mật hệ thống: Được sử dụng trực tiếp trong các thuật toán mã hóa bất đối xứng (như tính khóa bí mật trong RSA từ khóa công khai) hoặc trong các hệ thống chữ ký số phân tán trên các nền tảng enterprise.