Khái niệm Primitive Root (Gốc nguyên thủy)
Cho số nguyên dương n và số nguyên g. g được gọi là nguyên gốc modulo n (primitive root modulo n) nếu bậc nhân của g modulo n bằng φ(n) – hàm Euler Totient của n.
Tức là: Tập hợp các lũy thừa {g¹ mod n, g² mod n, ..., g^φ(n) mod n} bao gồm tất cả các số nguyên dương nhỏ hơn n và nguyên tố cùng nhau với n (hệ 잉 dư giảm modulo n).
Điều kiện tồn tại
Primitive root modulo n tồn tại chỉ khi n thuộc một trong các dạng:
- n = 2
- n = 4
- n = pᵏ (p là số nguyên tố lẻ, k ≥ 1)
- n = 2pᵏ (p là số nguyên tố lẻ, k ≥ 1)
Ví dụ: n = 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, 22, 23, 25, 26, 27, 29... KHÔNG có primitive root cho n = 8, 12, 15, 16, 20, 21, 24, 28, 30...
Cách tìm Primitive Root (n là số nguyên tố p)
- Tính φ(p) = p - 1
- Phân tích thừa số nguyên tố của p - 1 = q₁^e₁ × q₂^e₂ × ... × qₖ^eₖ
- Với mỗi ứng viên g = 2, 3, 4, ... kiểm tra:
g^((p-1)/qᵢ) ≢ 1 (mod p) với mọi i = 1..k - Nếu thỏa mãn mọi điều kiện → g là primitive root modulo p
- Tất cả primitive root: gᵏ mod p với mọi k thỏa mãn gcd(k, p-1) = 1. Số lượng: φ(p-1)
Ví dụ minh họa
Primitive root modulo 11
- p = 11, φ(11) = 10 = 2 × 5
- Kiểm tra g = 2: 2⁵ = 32 ≡ 10 ≢ 1 (mod 11), 2² = 4 ≢ 1 (mod 11) → 2 là primitive root
- Các primitive root khác: 2ᵏ mod 11 với k ∈ {1,3,7,9} → {2, 8, 7, 6}
- Kiểm tra: 2¹=2, 2²=4, 2³=8, 2⁴=5, 2⁵=10, 2⁶=9, 2⁷=7, 2⁸=3, 2⁹=6, 2¹⁰=1 → đủ 1..10
Primitive root modulo 13
- p = 13, φ(13) = 12 = 2² × 3
- Kiểm tra g = 2: 2⁶ = 64 ≡ 12 ≢ 1, 2⁴ = 16 ≡ 3 ≢ 1 → 2 là primitive root
- Tất cả: 2ᵏ mod 13, gcd(k,12)=1 → k ∈ {1,5,7,11} → {2, 6, 11, 7}
Primitive root modulo 17
- p = 17, φ(17) = 16 = 2⁴
- Primitive root: 3, 5, 6, 7, 10, 11, 12, 14 (tổng 8 = φ(16) cái)
Ứng dụng trong An ninh mạng (Cryptography)
1. Diffie-Hellman Key Exchange
- Công khai: Số nguyên tố lớn p, primitive root g
- Alice chọn bí mật a, gửi A = gᵃ mod p
- Bob chọn bí mật b, gửi B = gᵇ mod p
- Khóa chung: K = Bᵃ = gᵃᵇ = Aᵇ mod p
- An toàn nhờ Discrete Logarithm Problem (DLP) khó giải
2. ElGamal Encryption / Digital Signature
- Cùng cấu trúc DH, thêm bước mã hóa/ký số
- Yêu cầu g là primitive root modulo p
3. DSA (Digital Signature Algorithm)
- Sử dụng subgroup của Zₚ*阶 q (q | p-1), g có bậc q
- g = h^((p-1)/q) mod p với h là primitive root modulo p
4. TLS/SSL (Ephemeral Diffie-Hellman - DHE/ECDHE)
- Các nhóm DH chuẩn (RFC 7919): ffdhe2048, ffdhe3072, ffdhe4096, ffdhe6144, ffdhe8192
- Mỗi nhóm định nghĩa p và g (generator của subgroup lớn)
- ECDHE dùng điểm trên đường cong elliptic (không dùng primitive root modulo p)
Bảng tra nhanh Primitive Root cho các số nguyên tố nhỏ
| p | φ(p)=p-1 | Số lượng (φ(p-1)) | Primitive Roots |
|---|---|---|---|
| 3 | 2 | 1 | 2 |
| 5 | 4 | 2 | 2, 3 |
| 7 | 6 | 2 | 3, 5 |
| 11 | 10 | 4 | 2, 6, 7, 8 |
| 13 | 12 | 4 | 2, 6, 7, 11 |
| 17 | 16 | 8 | 3, 5, 6, 7, 10, 11, 12, 14 |
| 19 | 18 | 6 | 2, 3, 10, 13, 14, 15 |
| 23 | 22 | 10 | 5, 7, 10, 11, 14, 15, 17, 19, 20, 21 |
| 29 | 28 | 12 | 2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27 |
| 31 | 30 | 8 | 3, 11, 12, 13, 17, 21, 22, 24 |
Lưu ý bảo mật
- Không tự tạo nhóm DH – dùng RFC 7919 groups (ffdhe2048 trở lên)
- Tránh nhóm nhỏ (≤ 1024-bit) – dễ bị Logjam attack
- Ưu tiên ECDHE (X25519, P-256, P-384) thay vì DHE – nhanh hơn, key nhỏ hơn, an toàn tương đương
- Kiểm tra g thực sự là generator của subgroup lớn – tránh small subgroup attack
Tóm lại: Primitive root là generator của nhóm nhân modulo p. Nó là nền tảng của Diffie-Hellman, ElGamal, DSA. Trong thực hành TLS hiện đại, dùng nhóm chuẩn RFC 7919 hoặc đường cong elliptic (ECDHE) thay vì tự chọn p, g.