เครื่องคำนวณรากดั้งเดิม

ค้นหารากดั้งเดิมทั้งหมดของมอดุโล n ที่กำหนด — ตัวสร้างของกลุ่มการคูณ (Z/nZ)* ป้อนจำนวนเต็มบวกใดๆ เพื่อรับรากดั้งเดิม, ฟังก์ชันโทเชียนต์ของออยเลอร์ (Euler's totient), การแสดงภาพกลุ่มวัฏจักร และการตรวจสอบทีละขั้นตอนพร้อมตารางเลขยกกำลัง

Embed เครื่องคำนวณรากดั้งเดิม Widget

เกี่ยวกับ เครื่องคำนวณรากดั้งเดิม

เครื่องคำนวณรากดั้งเดิมนี้จะค้นหารากดั้งเดิมทั้งหมดของมอดุลัส n ที่กำหนด — ซึ่งคือจำนวนเต็ม g ที่มีเลขยกกำลัง \(g^1, g^2, \ldots, g^{\varphi(n)}\) สามารถสร้างสมาชิกทุกตัวของกลุ่มการคูณ \((\mathbb{Z}/n\mathbb{Z})^*\) ได้ ป้อนจำนวนเต็มบวกเพื่อดูรากดั้งเดิมทั้งหมดทันที, ค่าโทเชียนต์ของออยเลอร์ \(\varphi(n)\), ภาพจำลองกลุ่มวัฏจักรแบบโต้ตอบ, ตารางเลขยกกำลัง และการตรวจสอบทีละขั้นตอนของรากดั้งเดิมที่น้อยที่สุด

การประยุกต์ใช้งานของรากดั้งเดิม

🔐

Diffie-Hellman

โปรโตคอลแลกเปลี่ยนคีย์ที่ใช้รากดั้งเดิมเป็นตัวสร้าง

🔏

การเข้ารหัส ElGamal

ระบบรหัสลับแบบกุญแจสาธารณะที่อิงตามลอการิทึมแบบไม่ต่อเนื่อง

✍

ลายเซ็นดิจิทัล

DSA และลายเซ็น Schnorr อาศัยตัวสร้างของกลุ่มวัฏจักร

🎲

ตัวเลขสุ่มเทียม

ตัวสร้างความสอดคล้องเชิงเส้นใช้คุณสมบัติของรากดั้งเดิม

📡

รหัสแก้ไขข้อผิดพลาด

รหัส Reed-Solomon และ BCH ใช้ตัวสร้างของฟีลด์จำกัด

🧮

ทฤษฎีจำนวน

การคำนวณดัชนี, ส่วนตกค้างกำลังสอง และปัญหาลอการิทึมแบบไม่ต่อเนื่อง

แนวคิดหลักและสูตร

แนวคิด	สูตร / คำนิยาม	คำอธิบาย
รากดั้งเดิม	\(\text{ord}_n(g) = \varphi(n)\)	จำนวนเต็ม g ที่มีอันดับ mod n เท่ากับโทเชียนต์ของออยเลอร์
โทเชียนต์ของออยเลอร์	\(\varphi(n) = n \prod_{p\|n}\left(1 - \frac{1}{p}\right)\)	จำนวนของจำนวนเต็มใน [1, n] ที่เป็นจำนวนเฉพาะสัมพัทธ์กับ n
เกณฑ์การมีอยู่	\(n \in \{1, 2, 4, p^k, 2p^k\}\)	รากดั้งเดิมมีอยู่สำหรับรูปแบบเหล่านี้เท่านั้น (p เป็นจำนวนเฉพาะคี่)
จำนวนราก	\(\varphi(\varphi(n))\)	จำนวนรากดั้งเดิมเมื่อมีอยู่
การทดสอบรากดั้งเดิม	\(g^{\varphi(n)/p} \not\equiv 1 \pmod{n}\) สำหรับทุกจำนวนเฉพาะ \(p \| \varphi(n)\)	เงื่อนไขที่เพียงพอ: ตรวจสอบเฉพาะตัวประกอบเฉพาะของ φ(n)
การสร้างรากทั้งหมด	\(g^k \bmod n\) โดยที่ \(\gcd(k, \varphi(n)) = 1\)	เมื่อพบราก g หนึ่งตัวแล้ว รากอื่นๆ ที่เหลือจะตามมา

ทำความเข้าใจเกี่ยวกับรากดั้งเดิม

รากดั้งเดิมมอดุลัส n คือจำนวนเต็ม g ที่ทำให้เซต \(\{g^1 \bmod n, g^2 \bmod n, \ldots, g^{\varphi(n)} \bmod n\}\) เท่ากับเซตของจำนวนเต็มทั้งหมดตั้งแต่ 1 ถึง n−1 ที่เป็นจำนวนเฉพาะสัมพัทธ์กับ n ในทางทฤษฎีกลุ่ม g คือ ตัวสร้าง (generator) ของกลุ่มการคูณวัฏจักร \((\mathbb{Z}/n\mathbb{Z})^*\) ตัวอย่างเช่น 3 เป็นรากดั้งเดิม mod 7 เพราะเลขยกกำลัง 3¹=3, 3²=2, 3³=6, 3⁴=4, 3⁵=5, 3⁶=1 (mod 7) ให้สมาชิกทุกตัวใน {1, 2, 3, 4, 5, 6}

รากดั้งเดิมมีอยู่เมื่อใด?

ผลลัพธ์คลาสสิกในทฤษฎีจำนวน (พิสูจน์โดย Gauss) ระบุว่ารากดั้งเดิมมอดุลัส n จะมีอยู่ก็ต่อเมื่อ n เป็นหนึ่งใน: 1, 2, 4, p^k, หรือ 2p^k โดยที่ p เป็นจำนวนเฉพาะคี่ และ k ≥ 1 สำหรับค่า n อื่นๆ กลุ่ม \((\mathbb{Z}/n\mathbb{Z})^*\) จะไม่เป็นกลุ่มวัฏจักร — มันจะแยกย่อยเป็นผลคูณตรงของกลุ่มวัฏจักรตามทฤษฎีบทเศษเหลือของจีน — ดังนั้นจึงไม่มีสมาชิกตัวใดตัวหนึ่งที่สามารถสร้างกลุ่มทั้งหมดได้ ตัวอย่างเช่น \((\mathbb{Z}/8\mathbb{Z})^* \cong \mathbb{Z}/2 \times \mathbb{Z}/2\) ไม่มีรากดั้งเดิม

วิธีหารากดั้งเดิมอย่างมีประสิทธิภาพ

อัลกอริทึมมาตรฐานทำงานในสองขั้นตอน ขั้นตอนที่ 1: ค้นหารากดั้งเดิมที่น้อยที่สุดโดยการทดลอง สำหรับตัวเลือก g แต่ละตัวเริ่มจาก 2 ให้คำนวณ \(g^{\varphi(n)/p} \bmod n\) สำหรับทุกตัวประกอบเฉพาะ p ของ \(\varphi(n)\) หากไม่มีค่าใดเท่ากับ 1 แสดงว่า g เป็นรากดั้งเดิม ในทางปฏิบัติ รากดั้งเดิมที่น้อยที่สุดมักจะมีค่าไม่มาก — มีการคาดการณ์ว่าจะเป็น \(O(n^\epsilon)\) สำหรับ \(\epsilon > 0\) ใดๆ ขั้นตอนที่ 2: เมื่อทราบรากดั้งเดิม g หนึ่งตัวแล้ว รากดั้งเดิมอื่นๆ ทั้งหมดคือ \(g^k \bmod n\) โดยที่ \(\gcd(k, \varphi(n)) = 1\) ซึ่งจะให้รากดั้งเดิมรวมทั้งหมด \(\varphi(\varphi(n))\) จำนวนพอดี

วิธีใช้งานเครื่องคำนวณรากดั้งเดิม

กรอกค่ามอดุลัส n: พิมพ์จำนวนเต็มบวกในช่องป้อนข้อมูล หรือคลิกปุ่มตัวอย่างด่วนเพื่อเติมค่าโดยอัตโนมัติ
คลิก ค้นหารากดั้งเดิม: กดปุ่มเพื่อคำนวณรากดั้งเดิมทั้งหมดมอดุลัส n
ตรวจสอบผลลัพธ์: ดูจำนวน, รายการรากดั้งเดิมที่สมบูรณ์, โทเชียนต์ของออยเลอร์, อันดับของกลุ่ม และตรวจสอบว่า n ของคุณมีรากดั้งเดิมหรือไม่
สำรวจภาพจำลอง: สำหรับ n ≤ 100 วงล้อกลุ่มวัฏจักรแบบโต้ตอบจะแสดงให้เห็นว่ารากดั้งเดิมแต่ละตัวสร้างกลุ่มทั้งหมดผ่านเลขยกกำลังได้อย่างไร คลิกที่ชิปรากใดก็ได้เพื่อดูภาพเคลื่อนไหวของวงจรบนวงล้อ
ศึกษาตารางเลขยกกำลัง: ตารางจะแสดง g^k mod n สำหรับ k = 1, 2, …, φ(n) โดยมีการเน้นสีที่แตกต่างกันสำหรับรากดั้งเดิมและสมาชิกเอกลักษณ์

รากดั้งเดิมในวิทยาการรหัสลับ

รากดั้งเดิมมีบทบาทสำคัญในวิทยาการรหัสลับสมัยใหม่ ใน การแลกเปลี่ยนคีย์ Diffie-Hellman สองฝ่ายจะตกลงกันที่จำนวนเฉพาะขนาดใหญ่ p และรากดั้งเดิม g mod p จากนั้นแลกเปลี่ยนกุญแจสาธารณะ g^a mod p และ g^b mod p ความลับที่ใช้ร่วมกัน g^ab mod p นั้นเป็นเรื่องที่ยากเกินกว่าที่ผู้ลักลอบดักฟังจะคำนวณได้ เนื่องจากการคำนวณลอการิทึมแบบไม่ต่อเนื่องในกลุ่มวัฏจักรขนาดใหญ่นั้นเชื่อกันว่าทำได้ยาก ในทำนองเดียวกัน การเข้ารหัส ElGamal และ อัลกอริทึมลายเซ็นดิจิทัล (DSA) ต่างก็อาศัยความยากของปัญหาลอการิทึมแบบไม่ต่อเนื่องในกลุ่มที่สร้างโดยรากดั้งเดิม

คำถามที่พบบ่อย (FAQ)

รากดั้งเดิมมอดุลัส n คืออะไร?

รากดั้งเดิมมอดุลัส n คือจำนวนเต็ม g ที่ทำให้เลขยกกำลัง g¹, g², …, g^φ(n) มอดุลัส n ให้ค่าจำนวนเต็มทุกตัวที่เป็นจำนวนเฉพาะสัมพัทธ์กับ n เพียงครั้งเดียวพอดี หรือกล่าวอีกนัยหนึ่ง g มีอันดับการคูณเท่ากับ φ(n) ซึ่งหมายความว่า g สามารถสร้างกลุ่มการคูณ (Z/nZ)* ได้ทั้งหมด

ค่า n ใดบ้างที่มีรากดั้งเดิม?

รากดั้งเดิมจะมีอยู่ก็ต่อเมื่อ n เป็น 1, 2, 4, p^k, หรือ 2p^k โดยที่ p เป็นจำนวนเฉพาะคี่ และ k เป็นจำนวนเต็มบวก ตัวอย่างเช่น n = 7 (จำนวนเฉพาะ), n = 9 (3²) และ n = 14 (2 × 7) ล้วนมีรากดั้งเดิม แต่ n = 8, n = 12 และ n = 15 ไม่มี

n หนึ่งตัวมีรากดั้งเดิมกี่จำนวน?

ถ้า n มีรากดั้งเดิม จำนวนของรากดั้งเดิมมอดุลัส n จะเท่ากับ φ(φ(n)) โดยที่ φ คือฟังก์ชันโทเชียนต์ของออยเลอร์ ตัวอย่างเช่น n = 7 มี φ(φ(7)) = φ(6) = 2 รากดั้งเดิม ซึ่งก็คือ 3 และ 5

จะค้นหารากดั้งเดิมได้อย่างไร?

การหารากดั้งเดิมของ n: ขั้นแรกให้คำนวณ φ(n) และแยกตัวประกอบของมัน จากนั้นสำหรับตัวเลือก g แต่ละตัวที่เป็นจำนวนเฉพาะสัมพัทธ์กับ n ให้ตรวจสอบว่า g^(φ(n)/p) ไม่สมภาคกับ 1 mod n สำหรับทุกตัวประกอบเฉพาะ p ของ φ(n) หากผ่านการตรวจสอบทั้งหมด g จะเป็นรากดั้งเดิม ส่วนรากอื่นๆ สามารถหาได้จาก g^k mod n โดยที่ gcd(k, φ(n)) = 1

ทำไมรากดั้งเดิมจึงสำคัญในด้านวิทยาการรหัสลับ?

รากดั้งเดิมเป็นพื้นฐานของการแลกเปลี่ยนคีย์ Diffie-Hellman, การเข้ารหัส ElGamal และอัลกอริทึมลายเซ็นดิจิทัล สิ่งเหล่านี้ช่วยรับประกันว่าปัญหาลอการิทึมแบบไม่ต่อเนื่องนั้นทำได้ยาก ซึ่งเป็นพื้นฐานความปลอดภัยสำหรับโปรโตคอลรหัสลับเหล่านี้ รากดั้งเดิมจะสร้างสมาชิกทั้งหมดของกลุ่ม ทำให้พื้นที่การค้นหาสำหรับผู้โจมตีมีขนาดใหญ่ที่สุด

อ้างอิงเนื้อหา หน้าหรือเครื่องมือนี้ว่า:

"เครื่องคำนวณรากดั้งเดิม" ที่ https://MiniWebtool.com/th/เครื่องคำนวณรากดั้งเดิม/ จาก MiniWebtool, https://MiniWebtool.com/

โดยทีมงาน miniwebtool อัปเดตเมื่อ: 2026-04-16

คุณสามารถลองใช้ AI แก้ปัญหาคณิตศาสตร์ GPT ของเรา เพื่อแก้ไขปัญหาทางคณิตศาสตร์ของคุณผ่านคำถามและคำตอบด้วยภาษาธรรมชาติ.