Máy tính Căn nguyên thủy

Chào mừng bạn đến với Máy tính căn nguyên thủy, một công cụ trực tuyến miễn phí mạnh mẽ giúp tìm tất cả các căn nguyên thủy modulo cho bất kỳ số nguyên dương n nào. Máy tính này cung cấp xác minh từng bước, bảng lũy thừa và hình ảnh trực quan hóa nhóm cyclic động để giúp bạn hiểu cách các căn nguyên thủy tạo ra các nhóm nhân. Cho dù bạn đang học lý thuyết số, chuẩn bị cho các kỳ thi mật mã học hay làm việc với số học modulo trong lập trình thi đấu, công cụ này sẽ mang lại kết quả chính xác tức thì cùng với các kiến thức giáo dục bổ ích.

Căn nguyên thủy là gì?

Một căn nguyên thủy modulo n là một số nguyên g mà các lũy thừa của nó tạo ra tất cả các số nguyên nguyên tố cùng nhau với n. Về mặt hình thức, g là một căn nguyên thủy mod n nếu bậc nhân của g modulo n bằng hàm phi Euler \(\varphi(n)\). Điều này có nghĩa là tập hợp

chứa chính xác tất cả \(\varphi(n)\) số nguyên từ 1 đến n-1 nguyên tố cùng nhau với n. Một căn nguyên thủy về cơ bản là một phần tử sinh của nhóm cyclic \((\mathbb{Z}/n\mathbb{Z})^*\).

Ví dụ nhanh

Xét n = 7. Vì 7 là số nguyên tố, \(\varphi(7) = 6\). Hãy kiểm tra xem g = 3 có phải là căn nguyên thủy không:

• 3¹ mod 7 = 3
• 3² mod 7 = 2
• 3³ mod 7 = 6
• 3⁴ mod 7 = 4
• 3⁵ mod 7 = 5
• 3⁶ mod 7 = 1

Các lũy thừa tạo ra {3, 2, 6, 4, 5, 1} = {1, 2, 3, 4, 5, 6}, bao gồm tất cả các số nguyên nguyên tố cùng nhau với 7. Vì vậy, 3 là một căn nguyên thủy modulo 7.

Khi nào căn nguyên thủy tồn tại?

Căn nguyên thủy modulo n tồn tại khi và chỉ khi n có một trong các dạng sau:

• n = 1, 2, hoặc 4
• n = p^k trong đó p là một số nguyên tố lẻ và k ≥ 1
• n = 2p^k trong đó p là một số nguyên tố lẻ và k ≥ 1

Ví dụ, căn nguyên thủy tồn tại cho 7, 9, 11, 13, 14, 18, 23, 25, 27, 46, nhưng không tồn tại cho 8, 12, 15, 16, 20, 21, 24.

Cách tìm căn nguyên thủy

1. Nhập modulo: Nhập một số nguyên dương n (từ 2 đến 100.000) vào ô nhập liệu.
2. Tính toán: Nhấp vào "Tìm căn nguyên thủy" hoặc nhấn Enter.
3. Xem tất cả các căn: Xem danh sách đầy đủ các căn nguyên thủy, cùng với hàm phi Euler và số liệu thống kê.
4. Nghiên cứu bảng lũy thừa: Kiểm tra cách căn nguyên thủy nhỏ nhất tạo ra tất cả các thặng dư nguyên tố cùng nhau.
5. Trực quan hóa nhóm cyclic: Đối với các modulo nhỏ, hãy xem vòng quay hoạt hình hiển thị cấu trúc cyclic.

n có bao nhiêu căn nguyên thủy?

Nếu căn nguyên thủy modulo n tồn tại, số lượng căn bằng:

Ví dụ, với n = 13: \(\varphi(13) = 12\) và \(\varphi(12) = 4\), vì vậy có chính xác 4 căn nguyên thủy modulo 13 (đó là 2, 6, 7, 11).

Thuật toán xác minh

Để kiểm tra xem g có phải là căn nguyên thủy modulo n một cách hiệu quả:

1. Tính \(\varphi(n)\) bằng cách phân tích thừa số nguyên tố của n
2. Tìm tất cả các thừa số nguyên tố phân biệt \(p_1, p_2, \ldots, p_k\) của \(\varphi(n)\)
3. Với mỗi thừa số nguyên tố \(p_i\), kiểm tra: \(g^{\varphi(n)/p_i} \not\equiv 1 \pmod{n}\)
4. Nếu TẤT CẢ các kiểm tra đều đạt, thì g là một căn nguyên thủy

Phương pháp này nhanh hơn nhiều so với việc tính toán tất cả các lũy thừa của g, vì chúng ta chỉ cần thử nghiệm \(k\) phép lũy thừa thay vì \(\varphi(n)\) phép.

Căn nguyên thủy trong mật mã học

Trao đổi khóa Diffie-Hellman

Giao thức Diffie-Hellman sử dụng một số nguyên tố lớn p và một căn nguyên thủy g modulo p. Alice chọn bí mật a, gửi \(g^a \bmod p\). Bob chọn bí mật b, gửi \(g^b \bmod p\). Cả hai tính toán bí mật chung \(g^{ab} \bmod p\). Bảo mật dựa trên việc bài toán logarit rời rạc là cực kỳ khó về mặt tính toán.

Mã hóa ElGamal

ElGamal cũng sử dụng một căn nguyên thủy làm phần tử sinh. Khóa công khai là \((p, g, g^x \bmod p)\) trong đó x là bí mật. Thực tế là g tạo ra tất cả các phần tử đảm bảo rằng mọi thông điệp đều có thể được mã hóa.

Chữ ký số

DSA (Thuật toán chữ ký số) và các sơ đồ liên quan sử dụng căn nguyên thủy trong các nhóm con của \((\mathbb{Z}/p\mathbb{Z})^*\) để tạo và xác minh chữ ký số.

Bảng tham khảo: Căn nguyên thủy nhỏ nhất

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

Căn nguyên thủy modulo n là gì?

Một căn nguyên thủy modulo n là một số nguyên g sao cho các lũy thừa \(g^1, g^2, \ldots, g^{\varphi(n)}\) tạo ra tất cả các số nguyên nguyên tố cùng nhau với n khi lấy modulo n. Nói cách khác, g sinh ra toàn bộ nhóm nhân \((\mathbb{Z}/n\mathbb{Z})^*\). Bậc nhân của g modulo n bằng hàm phi Euler \(\varphi(n)\).

Căn nguyên thủy tồn tại cho những giá trị nào của n?

Căn nguyên thủy modulo n tồn tại khi và chỉ khi n là 1, 2, 4, p^k, hoặc 2p^k, trong đó p là một số nguyên tố lẻ và k ≥ 1. Ví dụ, căn nguyên thủy tồn tại cho n = 7 (số nguyên tố), n = 9 (3²), n = 14 (2×7), nhưng KHÔNG tồn tại cho n = 8, 12, 15, hoặc 16.

n có bao nhiêu căn nguyên thủy?

Nếu căn nguyên thủy modulo n tồn tại, số lượng căn nguyên thủy bằng \(\varphi(\varphi(n))\), trong đó \(\varphi\) là hàm phi Euler. Ví dụ, với n = 13 (số nguyên tố), \(\varphi(13) = 12\) và \(\varphi(12) = 4\), vì vậy có chính xác 4 căn nguyên thủy modulo 13.

Tại sao căn nguyên thủy quan trọng trong mật mã học?

Căn nguyên thủy là nền tảng cho giao thức trao đổi khóa Diffie-Hellman và hệ thống mã hóa ElGamal. Trong các giao thức mật mã này, một căn nguyên thủy g modulo một số nguyên tố lớn p được sử dụng làm phần tử sinh. Bảo mật dựa trên độ khó của bài toán logarit rời rạc: cho \(g^x \bmod p\), việc tìm x là rất khó về mặt tính toán.

Làm thế nào để xác minh g là một căn nguyên thủy modulo n?

Để xác minh g là căn nguyên thủy mod n: (1) Tính \(\varphi(n)\). (2) Tìm tất cả các thừa số nguyên tố \(p_1, p_2, \ldots, p_k\) của \(\varphi(n)\). (3) Kiểm tra xem \(g^{\varphi(n)/p_i} \not\equiv 1 \pmod{n}\) cho mỗi thừa số nguyên tố \(p_i\). Nếu tất cả các kiểm tra đều đạt, g là một căn nguyên thủy. Phương pháp này nhanh hơn nhiều so với việc tính toán tất cả các lũy thừa của g.

Công cụ liên quan