Bài 16.4. Modular inverse trong Python

Chào mừng các bạn đến với bài viết hôm nay! Trong thế giới toán học và lập trình, đặc biệt là trong lĩnh vực mật mã học và lý thuyết số, khái niệm nghịch đảo modular đóng một vai trò vô cùng quan trọng. Bài viết này sẽ giúp bạn hiểu rõ về định nghĩa, cách tìm nghịch đảo modular và cách triển khai nó trong Python một cách dễ dàng thông qua các ví dụ minh họa cụ thể.

Nghịch đảo Modular là gì?

Hãy tưởng tượng bạn đang làm việc với phép chia trong số học đồng dư. Trong số học thông thường, nghịch đảo của một số a là một số b sao cho a × b = 1. Tương tự, trong số học đồng dư, nghịch đảo modular của một số nguyên a theo modulo m là một số nguyên x sao cho:

(a × x) mod m = 1

Điều này có nghĩa là khi bạn nhân a với x, phần dư của phép chia cho m là 1.

Một số lưu ý quan trọng:

Nghịch đảo modular của a theo modulo m chỉ tồn tại khi a và m là nguyên tố cùng nhau (ước chung lớn nhất của a và m là 1), hay còn gọi là gcd(a, m) = 1.
Nghịch đảo modular là duy nhất trong phạm vi từ 0 đến m - 1.

Cách tìm nghịch đảo Modular

Có nhiều phương pháp để tìm nghịch đảo modular, nhưng trong bài viết này, chúng ta sẽ tập trung vào một phương pháp phổ biến và dễ hiểu, đó là sử dụng Thuật toán Euclid mở rộng.

Tuy nhiên, đối với các trường hợp nhỏ, chúng ta cũng có thể tìm nghịch đảo modular bằng cách thử lần lượt các giá trị.

Ví dụ minh họa trong Python

Bây giờ, hãy cùng xem một vài ví dụ cụ thể về cách tìm nghịch đảo modular trong Python.

Ví dụ 1: Tìm nghịch đảo modular bằng phương pháp thử

Giả sử chúng ta muốn tìm nghịch đảo modular của 3 theo modulo 7. Chúng ta sẽ thử các số từ 1 đến 6 để xem số nào khi nhân với 3 và chia cho 7 có phần dư là 1.

(3 × 1) mod 7 = 3
(3 × 2) mod 7 = 6
(3 × 3) mod 7 = 2
(3 × 4) mod 7 = 5
(3 × 5) mod 7 = 1 <- Đây chính là nghịch đảo modular!
(3 × 6) mod 7 = 4

Vậy, nghịch đảo modular của 3 theo modulo 7 là 5.

Chúng ta có thể viết một đoạn code Python đơn giản để thực hiện việc này:

def modular_inverse_naive(a, m):
    """Tìm nghịch đảo modular của a theo modulo m bằng phương pháp thử."""
    for x in range(1, m):
        if (a * x) % m == 1:
            return x
    return None

# Ví dụ sử dụng
a = 3
m = 7
inverse = modular_inverse_naive(a, m)
if inverse:
    print(f"Nghịch đảo modular của {a} theo modulo {m} là {inverse}")
else:
    print(f"Không tìm thấy nghịch đảo modular cho {a} theo modulo {m}")
`

Giải thích code:

Hàm modular_inverse_naive(a, m) nhận hai đối số là số a và modulo m.
Hàm duyệt qua các số x từ 1 đến m-1.
Trong mỗi lần lặp, hàm kiểm tra xem (a * x) % m có bằng 1 hay không.
Nếu tìm thấy một giá trị x thỏa mãn điều kiện, hàm sẽ trả về giá trị đó.
Nếu sau khi duyệt hết mà không tìm thấy, hàm sẽ trả về None.

Ví dụ 2: Sử dụng hàm có sẵn (cho trường hợp modulo là số nguyên tố)

Trong Python, nếu modulo m là một số nguyên tố, chúng ta có thể sử dụng hàm pow(a, -2, m) để tính nghịch đảo modular. Lưu ý rằng đây là một cách hiệu quả hơn so với phương pháp thử đối với các số lớn.

def modular_inverse_pow(a, m):
    """Tìm nghịch đảo modular của a theo modulo m sử dụng hàm pow (chỉ hoạt động khi m là số nguyên tố)."""
    return pow(a, m - 2, m)

# Ví dụ sử dụng
a = 3
m = 7 # 7 là số nguyên tố
inverse = modular_inverse_pow(a, m)
print(f"Nghịch đảo modular của {a} theo modulo {m} là {inverse}")

a = 5
m = 11 # 11 là số nguyên tố
inverse = modular_inverse_pow(a, m)
print(f"Nghịch đảo modular của {a} theo modulo {m} là {inverse}")

# Ví dụ trường hợp không tồn tại nghịch đảo (gcd(a, m) != 1)
a = 4
m = 6 # gcd(4, 6) = 2
try:
    inverse = modular_inverse_pow(a, m)
    print(f"Nghịch đảo modular của {a} theo modulo {m} là {inverse}")
except ValueError as e:
    print(f"Lỗi: {e}")

Giải thích code:

Hàm modular_inverse_pow(a, m) sử dụng hàm pow(a, m - 2, m). Trong số học đồng dư, nếu m là số nguyên tố, theo định lý Fermat nhỏ, a\<sup>m-2\</sup> mod m là nghịch đảo modular của a mod m.
Chúng ta thử với a = 3, m = 7 và a = 5, m = 11, đều là các trường hợp hợp lệ.
Chúng ta cũng thử với a = 4, m = 6. Trong trường hợp này, 4 và 6 không phải là nguyên tố cùng nhau, nên nghịch đảo modular không tồn tại và hàm pow sẽ trả về lỗi ValueError.

Ví dụ 3: Sử dụng Thuật toán Euclid mở rộng

Phương pháp tổng quát hơn để tìm nghịch đảo modular, hoạt động ngay cả khi m không phải là số nguyên tố (miễn là gcd(a, m) = 1), là sử dụng Thuật toán Euclid mở rộng.

def extended_gcd(a, b):
    """Thuật toán Euclid mở rộng để tìm gcd(a, b) và các hệ số x, y sao cho ax + by = gcd(a, b)."""
    if a == 0:
        return b, 0, 1
    gcd, x1, y1 = extended_gcd(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    return gcd, x, y

def modular_inverse_gcd(a, m):
    """Tìm nghịch đảo modular của a theo modulo m sử dụng Thuật toán Euclid mở rộng."""
    gcd, x, y = extended_gcd(a, m)
    if gcd != 1:
        return None  # Nghịch đảo không tồn tại
    return (x % m + m) % m

# Ví dụ sử dụng
a = 3
m = 7
inverse = modular_inverse_gcd(a, m)
if inverse:
    print(f"Nghịch đảo modular của {a} theo modulo {m} là {inverse}")
else:
    print(f"Không tìm thấy nghịch đảo modular cho {a} theo modulo {m}")

a = 5
m = 11
inverse = modular_inverse_gcd(a, m)
if inverse:
    print(f"Nghịch đảo modular của {a} theo modulo {m} là {inverse}")
else:
    print(f"Không tìm thấy nghịch đảo modular cho {a} theo modulo {m}")

a = 4
m = 6
inverse = modular_inverse_gcd(a, m)
if inverse:
    print(f"Nghịch đảo modular của {a} theo modulo {m} là {inverse}")
else:
    print(f"Không tìm thấy nghịch đảo modular cho {a} theo modulo {m}")

Giải thích code:

Hàm extended_gcd(a, b) thực hiện Thuật toán Euclid mở rộng. Nó trả về ba giá trị: ước chung lớn nhất (gcd) của a và b, và hai hệ số x và y sao cho a × x + b × y = gcd(a, b).
Hàm modular_inverse_gcd(a, m) gọi hàm extended_gcd(a, m). Nếu gcd là 1, điều đó có nghĩa là a và m là nguyên tố cùng nhau và nghịch đảo modular tồn tại. Trong trường hợp này, giá trị x từ kết quả của extended_gcd (sau khi được chuẩn hóa về phạm vi từ 0 đến m - 1) chính là nghịch đảo modular.
Chúng ta thử lại các ví dụ trước, và phương pháp này hoạt động đúng cho cả trường hợp gcd(a, m) = 1 và gcd(a, m) != 1. Khi nghịch đảo không tồn tại, hàm sẽ trả về None.

Ứng dụng của nghịch đảo Modular

Nghịch đảo modular có rất nhiều ứng dụng quan trọng trong các lĩnh vực khác nhau, bao gồm:

Mật mã học: Được sử dụng rộng rãi trong các thuật toán mã hóa và giải mã, đặc biệt là trong mật mã khóa công khai như RSA.
Lý thuyết số: Là một khái niệm cơ bản trong các bài toán liên quan đến số học đồng dư.
Khoa học máy tính: Được sử dụng trong các thuật toán băm (hashing), kiểm tra tính toàn vẹn dữ liệu và nhiều ứng dụng khác.

Kết luận

Trong bài viết này, chúng ta đã tìm hiểu về khái niệm nghịch đảo modular và cách triển khai nó trong Python thông qua các ví dụ minh họa. Chúng ta đã xem xét phương pháp thử, sử dụng hàm pow (cho trường hợp modulo là số nguyên tố) và phương pháp tổng quát hơn là sử dụng Thuật toán Euclid mở rộng. Hiểu rõ về nghịch đảo modular là một bước quan trọng để bạn có thể khám phá sâu hơn về các lĩnh vực như mật mã học và lý thuyết số.

```

#HappyCoding cùng FullhouseDev! 🚀

Comments

There are no comments at the moment.