Primitive Root (รากฐานพื้นฐาน) ในทฤษฎีจำนวนและקריפโตกราฟี
Primitive Root modulo n (รากฐานพื้นฐานโมดולอ n) คือจำนวนเต็ม g ที่มีคุณสมบัติว่า: ยกกำลังของ g (g1, g2, ..., gφ(n)) จะได้ผลลัพธ์ครบทุกจำนวนที่ควรต้นกับ n (coprime) ภายใต้ modulo n ทุกค่าโดยไม่ซ้ำกัน
นิยามทางคณิตศาสตร์อย่างเป็นทางการ
ให้ n เป็นจำนวนเต็มบวก และ φ(n) เป็นฟังก์ชันออยเลอร์ (Euler's Totient Function) จำนวนเต็ม g เรียกว่า Primitive Root modulo n ก็ต่อเมื่อ:
- gcd(g, n) = 1 (g และ n ควรต้นกัน)
- ออเดอร์ของ g modulo n เท่ากับ φ(n) กล่าวคือ gφ(n) ≡ 1 (mod n) และไม่มี k < φ(n) ใดทำให้ gk ≡ 1 (mod n)
ตัวอย่าง Primitive Root
| Modulo (n) | φ(n) | Primitive Roots |
|---|---|---|
| 3 | 2 | 2 |
| 5 | 4 | 2, 3 |
| 7 | 6 | 3, 5 |
| 11 | 10 | 2, 6, 7, 8 |
| 13 | 12 | 2, 6, 7, 11 |
| 17 | 16 | 3, 5, 6, 7, 10, 11, 12, 14 |
| 23 | 22 | 5, 7, 10, 11, 14, 15, 17, 19, 20, 21 |
| 29 | 28 | 2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27 |
| 31 | 30 | 3, 11, 12, 13, 17, 21, 22, 24 |
วิธีหา Primitive Root
- คำนวณ φ(n) (ถ้า n เป็นเฉพาะ φ(n) = n-1)
- แยกตัวประกอบเฉพาะของ φ(n) ได้ p1, p2, ..., pk
- ทดสอบจำนวน g = 2, 3, 4, ... จนกว่าจะเจอ โดยตรวจสอบว่า:
g^(φ(n)/p_i) ≢ 1 (mod n) สำหรับทุก i = 1..kถ้าผ่านทุกเงื่อนไข g นั้นคือ Primitive Root
ความสำคัญใน Cryptography (การเข้ารหัส)
- Diffie-Hellman Key Exchange: ใช้ Primitive Root ของจำนวนเฉพาะใหญ่ (p) เป็นฐาน (generator) สำหรับแลกเปลี่ยนกุญแจ
- ElGamal Encryption: ใช้ Primitive Root ในการเข้ารหัสแบบ Public Key
- DSA (Digital Signature Algorithm): ต้องการ Primitive Root สำหรับการสร้างลายเซ็นดิจิทัล
- SSL/TLS: ใช้ในกลไก Key Exchange บางรูปแบบ (DHE cipher suites)
ข้อสังเกต
- Primitive Root มีอยู่ก็ต่อเมื่อ n = 1, 2, 4, pk, 2pk โดยที่ p เป็นจำนวนเฉพาะคี่
- สำหรับจำนวนเฉพาะ p จะมี Primitive Root ทั้งหมด φ(p-1) ตัว
- ในทางปฏิบัติ ใช้ Safe Prime (p = 2q+1 โดย q เป็นเฉพาะ) เพื่อให้ได้ subgroup ขนาดใหญ่และปลอดภัย
