Máy tính Vành và Trường

Giới thiệu về Máy tính Vành và Trường

Máy Tính Vành Và Trường thực hiện các phép tính số học chính xác bên trong hai họ cấu trúc đại số hữu hạn quan trọng nhất: các vành modulo Z_n và các trường hữu hạn Galois GF(p^k). Nó xử lý phép cộng, phép trừ, phép nhân, phép chia, lũy thừa, nghịch đảo nhân, và cấp của phần tử, đồng thời làm phong phú thêm mọi kết quả bằng phân tích cấu trúc — các đơn vị, ước của không, phần tử lũy linh, phần tử lũy đẳng, căn nguyên thủy và bảng Cayley được mã hóa màu đầy đủ.

Z_n — Vành Modulo

Đối với một số nguyên dương n, vành Z_n = {0, 1, 2, …, n − 1} thực hiện các phép cộng và phép nhân được rút gọn theo modulo n. Một phần tử a là một đơn vị của Z_n (tức là có nghịch đảo nhân) khi và chỉ khi gcd(a, n) = 1, vì vậy nhóm nhân Z_n* có cấp φ(n), hàm phi của Euler.

Khi n là hợp số, các phần tử a có gcd(a, n) > 1 là các ước của không: tồn tại b ≠ 0 sao cho a · b ≡ 0 (mod n). Máy tính sẽ tự động phân loại mọi phần tử vào vai trò cấu trúc của nó.

Tìm nghịch đảo — Thuật toán Euclid mở rộng

Nếu gcd(a, n) = 1, thuật toán Euclid mở rộng tạo ra các số nguyên x, y sao cho a · x + n · y = 1, từ đó a⁻¹ ≡ x (mod n). Công cụ này hiển thị đồng nhất thức Bézout kết quả bất cứ khi nào bạn yêu cầu tìm nghịch đảo.

Cấp nhân

Đối với một đơn vị a, cấp nhân ord(a) là số nguyên k ≥ 1 nhỏ nhất sao cho a^k ≡ 1 (mod n). Theo định lý Lagrange, ord(a) chia hết cho φ(n). Một phần tử có ord(a) = φ(n) được gọi là căn nguyên thủy và sinh ra toàn bộ nhóm đơn vị. Một căn nguyên thủy tồn tại chính xác khi n là một trong các giá trị 1, 2, 4, p^k, hoặc 2p^k với p là số nguyên tố lẻ.

GF(p^k) — Trường hữu hạn (Galois)

Đối với mỗi số nguyên tố p và số nguyên dương k, có một trường duy nhất (tính đến đẳng cấu) với p^k phần tử: trường Galois GF(p^k) = 𝔽_p^k. Các phần tử của nó được biểu diễn dưới dạng các đa thức bậc < k với các hệ số trong GF(p) = Z_p, và phép toán số học được thực hiện theo modulo của một đa thức bất khả quy f(x) bậc k.

Máy tính gợi ý một đa thức bất khả quy tiêu chuẩn cho các cặp (p, k) phổ biến, ví dụ x² + x + 1 cho GF(4), x³ + x + 1 cho GF(8), x⁴ + x + 1 cho GF(16), và x² + 1 cho GF(9). Bạn có thể thay đổi nó bằng đa thức của riêng mình; công cụ sẽ xác minh tính bất khả quy thông qua kiểm tra gcd kiểu Rabin.

Tại sao f(x) phải bất khả quy?

Nếu f(x) được phân tích thành g(x)·h(x) với deg g, deg h ≥ 1, thì ảnh của g(x) và h(x) trong vành thương sẽ là các ước của không khác không — vành thương khi đó chỉ là một vành, không phải là một trường. Tính bất khả quy chính xác là điều kiện để GF(p)[x] / ⟨f(x)⟩ trở thành một trường.

Số học đa thức và nghịch đảo

Phép cộng được thực hiện theo từng hệ số mod p. Phép nhân là phép nhân đa thức thông thường sau đó là phép rút gọn: cho a(x)·b(x), chia cho f(x) và lấy phần dư r(x), với deg r < k. Nghịch đảo nhân có được từ thuật toán Euclid mở rộng trên vành đa thức GF(p)[x]: tìm u(x) và v(x) sao cho u(x)·a(x) + v(x)·f(x) = 1.

So sánh Vành và Trường trong nháy mắt

Cách sử dụng máy tính

1. Chọn một cấu trúc — Z_n cho các số nguyên modulo, hoặc GF(p^k) cho một trường mở rộng. Biểu mẫu sẽ sắp xếp lại để chỉ hiển thị các trường liên quan.
2. Nhập các tham số — modulo n, hoặc số nguyên tố p và bậc k. Đối với GF(p^k), bạn có thể để trống đa thức bất khả quy và máy tính sẽ điền vào một đa thức tiêu chuẩn.
3. Chọn một phép toán — bảy lựa chọn bao quát tất cả các nhiệm vụ phổ biến: cộng, trừ, nhân, chia, lũy thừa, tính nghịch đảo hoặc tìm cấp nhân.
4. Cung cấp các toán hạng — các số nguyên cho Z_n, hoặc các đa thức như x^2 + x + 1 cho GF(p^k). Dạng danh sách hệ số (1,1,1) cũng hoạt động.
5. Nhấp Tính toán. Bạn sẽ thấy kết quả cùng với các bước thực hiện, phân loại mọi phần tử và bảng Cayley bất cứ khi nào cấu trúc đủ nhỏ để hiển thị.

Ví dụ thực hiện — GF(8) = GF(2³)

Lấy f(x) = x³ + x + 1 (bất khả quy trên GF(2)). Nhân a(x) = x + 1 với b(x) = x²:

Nhóm nhân GF(8)* là nhóm xyclic cấp 7, và phần tử x là một phần tử nguyên thủy vì x^k chạy qua mọi phần tử khác không khi k = 1, 2, …, 7.

Tại sao điều này quan trọng

• Mật mã học — AES sử dụng số học trong GF(2⁸) với f(x) = x⁸ + x⁴ + x³ + x + 1. Mật mã đường cong elliptic và bài toán logarit rời rạc nằm trong GF(p) và GF(p^k).
• Mã hiệu chỉnh lỗi — Mã Reed-Solomon và mã BCH (được sử dụng trong đĩa CD, mã QR, DVB-T, tàu thăm dò không gian Voyager) được xây dựng từ các đa thức trên GF(2⁸) hoặc GF(2^m).
• Thiết kế tổ hợp — trường hữu hạn xây dựng các ma trận Hadamard, các mặt phẳng xạ ảnh và các hình vuông Latinh được sử dụng trong các thí nghiệm thống kê.
• Đại số máy tính — các thuật toán phân tích nhân tử và rút gọn modulo (Berlekamp, Cantor-Zassenhaus) được xây dựng trên các trường hữu hạn.
• Sư phạm lý thuyết số — Z_n, căn nguyên thủy và thặng dư bậc hai là cửa ngõ dẫn vào số học modulo, RSA và Diffie-Hellman.

Câu hỏi thường gặp

Khi nào Z_n là một trường?

Vành modulo Z_n là một trường khi và chỉ khi n là số nguyên tố. Trong trường hợp đó, mọi phần tử khác không đều là đơn vị vì gcd(a, n) = 1 với mọi 0 < a < n. Khi n là hợp số, Z_n có các ước của không và chỉ là một vành, không phải là một miền nguyên.

GF(p^k) là gì?

GF(p^k), còn được gọi là trường Galois cấp p^k, là trường hữu hạn duy nhất có p^k phần tử. Các phần tử của nó được biểu diễn dưới dạng đa thức bậc nhỏ hơn k trên GF(p), với các phép toán số học được thực hiện theo modulo của một đa thức bất khả quy f(x) bậc k. Đối với mỗi số nguyên tố p và số nguyên dương k, có duy nhất một trường như vậy tính đến đẳng cấu.

Đa thức bất khả quy là gì và tại sao nó cần thiết?

Một đa thức bất khả quy trên GF(p) là một đa thức không thể phân tích thành các đa thức bậc thấp hơn với các hệ số trong GF(p). Việc rút gọn theo modulo của một đa thức bất khả quy bậc k tạo ra một vành thương là một trường. Nếu không có tính bất khả quy, vành thương sẽ có các ước của không và không phải là một trường.

Ước của không là gì?

Một phần tử a khác không trong một vành là ước của không nếu tồn tại một phần tử b khác không sao cho a · b = 0. Trong Z_n, các ước của không chính xác là các phần tử a có gcd(a, n) lớn hơn 1. Các trường không có ước của không, đó là lý do tại sao Z_n là một trường chính xác khi n là số nguyên tố.

Cấp nhân của một phần tử là gì?

Cấp nhân của một đơn vị a là số nguyên dương k nhỏ nhất sao cho a^k bằng 1 trong vành. Theo định lý Lagrange, cấp này chia hết cho kích thước của nhóm nhân: φ(n) đối với Z_n, hoặc p^k − 1 đối với GF(p^k). Một phần tử có cấp bằng toàn bộ kích thước nhóm được gọi là căn nguyên thủy hoặc phần tử sinh.

Phần tử nguyên thủy của GF(p^k) có tác dụng gì?

Phần tử nguyên thủy là phần tử sinh của nhóm nhân GF(p^k)*, là nhóm xyclic cấp p^k − 1. Mọi phần tử khác không của trường có thể được viết dưới dạng lũy thừa của phần tử nguyên thủy, giúp thực hiện logarit rời rạc, mã BCH và hiệu chỉnh lỗi Reed-Solomon.

Đọc thêm

• Số học Modulo — Wikipedia
• Trường hữu hạn — Wikipedia
• Căn nguyên thủy modulo n — Wikipedia
• Hàm phi của Euler — Wikipedia
• Đa thức bất khả quy — Wikipedia