Máy Tính Căn Nguyên Thủy

Tìm tất cả các căn nguyên thủy của một modulo n cho trước — các phần tử sinh của nhóm nhân (Z/nZ)*. Nhập bất kỳ số nguyên dương nào để nhận các căn nguyên thủy, hàm phi Euler, trực quan hóa nhóm xyclic và xác minh từng bước với bảng lũy thừa.

Embed Máy Tính Căn Nguyên Thủy Widget

Giới thiệu về Máy Tính Căn Nguyên Thủy

Máy tính Căn nguyên thủy tìm tất cả các căn nguyên thủy của một mô-đun n cho trước — các số nguyên g mà lũy thừa của chúng \(g^1, g^2, \ldots, g^{\varphi(n)}\) sinh ra mọi phần tử của nhóm nhân \((\mathbb{Z}/n\mathbb{Z})^*\). Nhập bất kỳ số nguyên dương nào để xem ngay lập tức tất cả các căn nguyên thủy, hàm số phi của Euler \(\varphi(n)\), hình ảnh trực quan tương tác về nhóm tuần hoàn, bảng lũy thừa và xác minh từng bước về căn nguyên thủy nhỏ nhất.

Ứng dụng của Căn nguyên thủy

🔐

Diffie-Hellman

Giao thức trao đổi khóa sử dụng căn nguyên thủy làm phần tử sinh

🔏

Mã hóa ElGamal

Hệ thống mật mã khóa công khai dựa trên logarit rời rạc

✍

Chữ ký số

Chữ ký DSA và Schnorr dựa trên các phần tử sinh của nhóm tuần hoàn

🎲

Số giả ngẫu nhiên

Các bộ tạo đồng dư tuyến tính sử dụng các tính chất của căn nguyên thủy

📡

Mã sửa lỗi

Mã Reed-Solomon và BCH sử dụng các phần tử sinh của trường hữu hạn

🧮

Lý thuyết số

Phép tính chỉ số, thặng dư bậc hai và các bài toán logarit rời rạc

Các khái niệm và Công thức chính

Khái niệm	Công thức / Định nghĩa	Mô tả
Căn nguyên thủy	\(\text{ord}_n(g) = \varphi(n)\)	Một số nguyên g có bậc mod n bằng hàm số phi Euler
Hàm số phi Euler	\(\varphi(n) = n \prod_{p\|n}\left(1 - \frac{1}{p}\right)\)	Số lượng các số nguyên trong khoảng [1, n] nguyên tố cùng nhau với n
Tiêu chuẩn tồn tại	\(n \in \{1, 2, 4, p^k, 2p^k\}\)	Căn nguyên thủy chỉ tồn tại cho các dạng này (p là số nguyên tố lẻ)
Số lượng căn	\(\varphi(\varphi(n))\)	Số lượng căn nguyên thủy khi chúng tồn tại
Kiểm tra Căn nguyên thủy	\(g^{\varphi(n)/p} \not\equiv 1 \pmod{n}\) cho mọi số nguyên tố \(p \| \varphi(n)\)	Điều kiện đủ: chỉ cần kiểm tra cho các ước nguyên tố của φ(n)
Tạo tất cả các căn	\(g^k \bmod n\) trong đó \(\gcd(k, \varphi(n)) = 1\)	Sau khi tìm thấy một căn g, tất cả các căn khác sẽ theo sau

Hiểu về Căn nguyên thủy

Một căn nguyên thủy theo mô-đun n là một số nguyên g sao cho tập hợp \(\{g^1 \bmod n, g^2 \bmod n, \ldots, g^{\varphi(n)} \bmod n\}\) bằng tập hợp tất cả các số nguyên từ 1 đến n−1 nguyên tố cùng nhau với n. Trong thuật ngữ lý thuyết nhóm, g là một phần tử sinh của nhóm nhân tuần hoàn \((\mathbb{Z}/n\mathbb{Z})^*\). Ví dụ, 3 là một căn nguyên thủy mod 7 vì các lũy thừa 3¹=3, 3²=2, 3³=6, 3⁴=4, 3⁵=5, 3⁶=1 (mod 7) tạo ra mọi phần tử của tập {1, 2, 3, 4, 5, 6}.

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

Một kết quả kinh điển trong lý thuyết số (được chứng minh bởi Gauss) khẳng định rằng căn nguyên thủy theo mô-đun n tồn tại khi và chỉ khi n là một trong các giá trị: 1, 2, 4, p^k, hoặc 2p^k, trong đó p là số nguyên tố lẻ và k ≥ 1. Đối với các giá trị khác của n, nhóm \((\mathbb{Z}/n\mathbb{Z})^*\) không tuần hoàn — nó phân rã thành tích trực tiếp của các nhóm tuần hoàn theo Định lý số dư Trung Hoa — vì vậy không có phần tử đơn lẻ nào có thể sinh ra toàn bộ nhóm. Ví dụ, \((\mathbb{Z}/8\mathbb{Z})^* \cong \mathbb{Z}/2 \times \mathbb{Z}/2\) không có căn nguyên thủy.

Cách tìm Căn nguyên thủy hiệu quả

Thuật toán tiêu chuẩn hoạt động theo hai giai đoạn. Giai đoạn 1: tìm căn nguyên thủy nhỏ nhất bằng cách thử dần. Với mỗi ứng viên g bắt đầu từ 2, tính \(g^{\varphi(n)/p} \bmod n\) cho mọi ước nguyên tố p của \(\varphi(n)\). Nếu không có giá trị nào bằng 1, thì g là một căn nguyên thủy. Trong thực tế, căn nguyên thủy nhỏ nhất thường khá nhỏ — người ta phỏng đoán nó là \(O(n^\epsilon)\) cho bất kỳ \(\epsilon > 0\). Giai đoạn 2: sau khi biết một căn nguyên thủy g, tất cả các căn nguyên thủy khác là \(g^k \bmod n\) trong đó \(\gcd(k, \varphi(n)) = 1\), cho ra tổng cộng đúng \(\varphi(\varphi(n))\) căn nguyên thủy.

Cách sử dụng Máy tính Căn nguyên thủy

Nhập mô-đun n: Nhập một số nguyên dương vào trường nhập liệu, hoặc nhấp vào một trong các nút ví dụ nhanh để tự động điền giá trị.
Nhấp Tìm Căn nguyên thủy: Nhấn nút để tính toán tất cả các căn nguyên thủy theo mô-đun n.
Xem lại kết quả: Xem số lượng, danh sách đầy đủ các căn nguyên thủy, hàm số phi Euler, bậc của nhóm và liệu căn nguyên thủy có tồn tại cho n của bạn hay không.
Khám phá hình ảnh trực quan: Với n ≤ 100, bánh xe nhóm tuần hoàn tương tác cho thấy cách mỗi căn nguyên thủy sinh ra toàn bộ nhóm thông qua các lũy thừa của nó. Nhấp vào bất kỳ thẻ căn nào để xem chu kỳ của nó được hoạt ảnh hóa trên bánh xe.
Nghiên cứu bảng lũy thừa: Lưới hiển thị g^k mod n cho k = 1, 2, …, φ(n), với các căn nguyên thủy và phần tử đơn vị được làm nổi bật bằng các màu sắc riêng biệt.

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

Căn nguyên thủy đóng một vai trò trung tâm trong mật mã học hiện đại. Trong trao đổi khóa Diffie-Hellman, hai bên thống nhất một số nguyên tố lớn p và một căn nguyên thủy g mod p, sau đó trao đổi các khóa công khai g^a mod p và g^b mod p. Bí mật chung g^ab mod p là bất khả thi về mặt tính toán để một kẻ nghe lén có thể xác định, vì việc tính toán logarit rời rạc trong các nhóm tuần hoàn lớn được tin là rất khó. Tương tự, mã hóa ElGamal và Thuật toán Chữ ký số (DSA) đều dựa trên độ khó của bài toán logarit rời rạc trong các nhóm được sinh ra bởi các căn nguyên thủy.

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

Căn nguyên thủy theo mô-đun n là gì?

Căn nguyên thủy theo mô-đun n là một số nguyên g sao cho các lũy thừa g¹, g², …, g^φ(n) theo mô-đun n tạo ra mọi số nguyên nguyên tố cùng nhau với n đúng một lần. Tương đương với việc g có bậc nhân bằng φ(n), nghĩa là g sinh ra toàn bộ nhóm nhân (Z/nZ)*.

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 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 là một số nguyên dương. Ví dụ, n = 7 (số nguyên tố), n = 9 (3²) và n = 14 (2 × 7) đều có căn nguyên thủy, nhưng n = 8, n = 12 và n = 15 thì không.

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

Nếu n có căn nguyên thủy, thì số lượng căn nguyên thủy theo mô-đun n bằng φ(φ(n)), trong đó φ là hàm số phi của Euler. Ví dụ, n = 7 có φ(φ(7)) = φ(6) = 2 căn nguyên thủy, đó là 3 và 5.

Làm thế nào để tìm căn nguyên thủy?

Để tìm các căn nguyên thủy của n: đầu tiên tính φ(n) và phân tích nó thành thừa số nguyên tố. Sau đó, với mỗi ứng viên g nguyên tố cùng nhau với n, hãy kiểm tra xem g^(φ(n)/p) không đồng dư với 1 mod n cho mọi ước nguyên tố p của φ(n). Nếu tất cả các kiểm tra đều đạt, g là một căn nguyên thủy. Tất cả các căn khác có thể được tìm thấy dưới dạng g^k mod n trong đó gcd(k, φ(n)) = 1.

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 của trao đổi khóa Diffie-Hellman, mã hóa ElGamal và các thuật toán chữ ký số. Chúng đảm bảo rằng bài toán logarit rời rạc là khó, vốn là cơ sở bảo mật cho các giao thức mật mã này. Một căn nguyên thủy tạo ra tất cả các phần tử của nhóm, tối đa hóa không gian tìm kiếm cho những kẻ tấn công.

Tham khảo nội dung, trang hoặc công cụ này như sau:

"Máy Tính Căn Nguyên Thủy" tại https://MiniWebtool.com/vi/may-tinh-can-nguyen-thuy/ từ MiniWebtool, https://MiniWebtool.com/

bởi đội ngũ miniwebtool. Cập nhật: 2026-04-16

Bạn cũng có thể thử AI Giải Toán GPT của chúng tôi để giải quyết các vấn đề toán học của bạn thông qua câu hỏi và trả lời bằng ngôn ngữ tự nhiên.

Các công cụ liên quan khác:

Máy tính Định lý Số dư Trung Quốc

Máy tính Hàm Phi Euler

Máy Tính Lũy Thừa ModularMới

Máy tính Nghịch đảo Nhân theo Mô-đun

Máy tính Phân tích Thừa số Nguyên tốNổi bật

Máy Tính Căn Nguyên Thủy

Giới thiệu về Máy Tính Căn Nguyên Thủy

Ứng dụng của Căn nguyên thủy

Các khái niệm và Công thức chính

Hiểu về Căn nguyên thủy

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

Cách tìm Căn nguyên thủy hiệu quả

Cách sử dụng Máy tính Căn nguyên thủy

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

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

Các công cụ liên quan khác:

Phép toán toán học nâng cao:

Công cụ nổi bật: