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

Nhập một mô-đun là số nguyên dương để tìm mọi căn nguyên thủy, tính hàm totient của Euler và xem bảng lũy thừa kèm hình minh họa nhóm cyclic.

Miễn phí 3 lượt mỗi ngàyKhông cần đăng kýKết quả tức thì

Máy Tính Căn Nguyên ThủyDùng thử ngay — miễn phí ▼

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 con có cấp nguyên tố lớ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 phần tử sinh của nhóm con có cấp nguyên tố lớn q, với q là ước của p−1, 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 rất khó để kẻ nghe lén tính ra, vì việc tính logarit rời rạc trong các nhóm con tuần hoàn lớn được cho là 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 con nà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?

Trao đổi khóa Diffie-Hellman, mã hóa ElGamal và các thuật toán chữ ký số như DSA và Schnorr sử dụng phần tử sinh của các nhóm con có cấp nguyên tố lớn, với cấp q là ước của p−1. Độ an toàn của chúng dựa trên độ khó của bài toán logarit rời rạc trong các nhóm con này.

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/máy-tính-căn-nguyên-thủy/ từ MiniWebtool, https://MiniWebtool.com/

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

Có API dành cho developer: Chạy công cụ này từ ứng dụng, tự động hóa hoặc agent của bạn bằng một yêu cầu HTTP JSON. Xem tài liệu API

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)

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

Giải toán

Số và ước số

Phân số và phép chia

Lũy thừa, căn và logarit

Đại số và phương trình

Giải tích

Hình học và lượng giác

Công cụ phổ biến và mới cập nhật:

Tải tất cả trong một tệp ZIP với Pro