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

ยินดีต้อนรับสู่ เครื่องคำนวณรากดั้งเดิม เครื่องมือออนไลน์ฟรีที่มีประสิทธิภาพสำหรับค้นหารากดั้งเดิมทั้งหมดมอดูโลจำนวนเต็มบวก n ใดๆ เครื่องคำนวณนี้แสดงการตรวจสอบทีละขั้นตอน ตารางเลขยกกำลัง และการแสดงภาพกลุ่มวัฏจักรแบบแอนิเมชันเพื่อช่วยให้คุณเข้าใจว่ารากดั้งเดิมสร้างกลุ่มการคูณได้อย่างไร ไม่ว่าคุณกำลังศึกษาทฤษฎีจำนวน เตรียมตัวสอบวิชาวิทยาการรหัสลับ หรือทำงานกับเลขคณิตมอดูโลในการเขียนโปรแกรมแข่งขัน เครื่องมือนี้ให้ผลลัพธ์ที่แม่นยำและรวดเร็วพร้อมความรู้ทางการศึกษา

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

รากดั้งเดิมมอดูโล n คือจำนวนเต็ม g ที่มีเลขยกกำลังสร้างจำนวนเต็มทั้งหมดที่เป็นจำนวนเฉพาะสัมพัทธ์กับ n ในเชิงรูปแบบ g เป็นรากดั้งเดิม mod n หากอันดับการคูณของ g มอดูโล n เท่ากับโทเชียนต์ของออยเลอร์ \(\varphi(n)\) ซึ่งหมายความว่าเซต

ประกอบด้วยจำนวนเต็ม \(\varphi(n)\) ทั้งหมดตั้งแต่ 1 ถึง n-1 ที่เป็นจำนวนเฉพาะสัมพัทธ์กับ n รากดั้งเดิมคือ ตัวกำเนิดของกลุ่มวัฏจักร \((\mathbb{Z}/n\mathbb{Z})^*\) นั่นเอง

ตัวอย่างสั้นๆ

พิจารณา n = 7 เนื่องจาก 7 เป็นจำนวนเฉพาะ \(\varphi(7) = 6\) ลองตรวจสอบว่า g = 3 เป็นรากดั้งเดิมหรือไม่:

• 3¹ mod 7 = 3
• 3² mod 7 = 2
• 3³ mod 7 = 6
• 3⁴ mod 7 = 4
• 3⁵ mod 7 = 5
• 3⁶ mod 7 = 1

ผลลัพธ์คือ {3, 2, 6, 4, 5, 1} = {1, 2, 3, 4, 5, 6} ซึ่งเป็นจำนวนเต็มทั้งหมดที่เป็นจำนวนเฉพาะสัมพัทธ์กับ 7 ดังนั้น 3 คือรากดั้งเดิมมอดูโล 7

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

รากดั้งเดิมมอดูโล n จะมีอยู่ ก็ต่อเมื่อ n อยู่ในรูปแบบใดรูปแบบหนึ่งดังนี้:

• n = 1, 2 หรือ 4
• n = p^k โดยที่ p เป็นจำนวนเฉพาะคี่ และ k ≥ 1
• n = 2p^k โดยที่ p เป็นจำนวนเฉพาะคี่ และ k ≥ 1

ตัวอย่างเช่น มีรากดั้งเดิมสำหรับ 7, 9, 11, 13, 14, 18, 23, 25, 27, 46 แต่ ไม่มี สำหรับ 8, 12, 15, 16, 20, 21, 24

วิธีหารากดั้งเดิม

1. ป้อนค่ามอดุลัส: พิมพ์จำนวนเต็มบวก n (ตั้งแต่ 2 ถึง 100,000) ลงในช่องป้อนข้อมูล
2. คำนวณ: คลิก "ค้นหารากดั้งเดิม" หรือกด Enter
3. ดูรากทั้งหมด: ดูรายการรากดั้งเดิมที่สมบูรณ์ พร้อมกับโทเชียนต์ของออยเลอร์และสถิติต่างๆ
4. ศึกษาตารางเลขยกกำลัง: ตรวจสอบว่ารากดั้งเดิมที่เล็กที่สุดสร้างส่วนตกค้างที่เป็นจำนวนเฉพาะสัมพัทธ์ทั้งหมดได้อย่างไร
5. ดูภาพกลุ่มวัฏจักร: สำหรับมอดุลัสขนาดเล็ก สามารถดูวงล้อแอนิเมชันที่แสดงโครงสร้างวัฏจักร

n มีรากดั้งเดิมจำนวนเท่าใด?

หากมีรากดั้งเดิมมอดูโล n จำนวนรากจะเท่ากับ:

ตัวอย่างเช่น สำหรับ n = 13: \(\varphi(13) = 12\) และ \(\varphi(12) = 4\) ดังนั้นจะมีรากดั้งเดิมทั้งหมด 4 ตัว มอดูโล 13 (ได้แก่ 2, 6, 7, 11)

อัลกอริทึมการตรวจสอบ

วิธีตรวจสอบว่า g เป็นรากดั้งเดิมมอดูโล n อย่างมีประสิทธิภาพ:

1. คำนวณ \(\varphi(n)\) โดยใช้การแยกตัวประกอบเฉพาะของ n
2. หาตัวประกอบเฉพาะที่แตกต่างกันทั้งหมด \(p_1, p_2, \ldots, p_k\) ของ \(\varphi(n)\)
3. สำหรับตัวประกอบเฉพาะ \(p_i\) แต่ละตัว ให้ตรวจสอบว่า: \(g^{\varphi(n)/p_i} \not\equiv 1 \pmod{n}\)
4. หากผ่านการตรวจสอบทั้งหมด แสดงว่า g เป็นรากดั้งเดิม

วิธีนี้เร็วกว่าการคำนวณเลขยกกำลังทั้งหมดของ g มาก เนื่องจากเราต้องทดสอบการยกกำลังเพียง \(k\) ครั้งแทนที่จะเป็น \(\varphi(n)\) ครั้ง

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

การแลกเปลี่ยนคีย์ Diffie-Hellman

โปรโตคอล Diffie-Hellman ใช้จำนวนเฉพาะขนาดใหญ่ p และรากดั้งเดิม g มอดูโล p Alice เลือกความลับ a และส่ง \(g^a \bmod p\) ส่วน Bob เลือกความลับ b และส่ง \(g^b \bmod p\) ทั้งคู่คำนวณความลับที่ใช้ร่วมกัน \(g^{ab} \bmod p\) ความปลอดภัยขึ้นอยู่กับ ปัญหาลอการิทึมไม่ต่อเนื่อง ที่ยากต่อการคำนวณ

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

ElGamal ยังใช้รากดั้งเดิมเป็นตัวกำเนิดด้วย คีย์สาธารณะคือ \((p, g, g^x \bmod p)\) โดยที่ x เป็นความลับ ความจริงที่ว่า g สร้างองค์ประกอบทั้งหมดช่วยให้มั่นใจได้ว่าทุกข้อความสามารถถูกเข้ารหัสได้

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

DSA (Digital Signature Algorithm) และระบบที่เกี่ยวข้องใช้รากดั้งเดิมในกลุ่มย่อยของ \((\mathbb{Z}/p\mathbb{Z})^*\) เพื่อสร้างและตรวจสอบลายเซ็นดิจิทัล

ตารางอ้างอิง: รากดั้งเดิมที่เล็กที่สุด

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

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

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

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

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

n มีรากดั้งเดิมจำนวนเท่าใด?

หากมีรากดั้งเดิมมอดูโล n จำนวนของรากดั้งเดิมจะเท่ากับ \(\varphi(\varphi(n))\) โดยที่ \(\varphi\) คือฟังก์ชันโทเชียนต์ของออยเลอร์ ตัวอย่างเช่น สำหรับ n = 13 (จำนวนเฉพาะ), \(\varphi(13) = 12\) และ \(\varphi(12) = 4\) ดังนั้นจะมีรากดั้งเดิมทั้งหมด 4 ตัวมอดูโล 13

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

รากดั้งเดิมเป็นพื้นฐานของโปรโตคอลการแลกเปลี่ยนคีย์ Diffie-Hellman และระบบการเข้ารหัส ElGamal ในโปรโตคอลเหล่านี้ รากดั้งเดิม g มอดูโลจำนวนเฉพาะขนาดใหญ่ p จะถูกใช้เป็นตัวกำเนิด ความปลอดภัยขึ้นอยู่กับความยากของปัญหาลอการิทึมไม่ต่อเนื่อง: เมื่อกำหนด \(g^x \bmod p\) มาให้ จะเป็นการยากในทางคอมพิวเตอร์ที่จะหาค่า x

จะตรวจสอบได้อย่างไรว่า g เป็นรากดั้งเดิมมอดูโล n?

วิธีตรวจสอบว่า g เป็นรากดั้งเดิม mod n: (1) คำนวณ \(\varphi(n)\) (2) หาตัวประกอบเฉพาะทั้งหมด \(p_1, p_2, \ldots, p_k\) ของ \(\varphi(n)\) (3) ตรวจสอบว่า \(g^{\varphi(n)/p_i} \not\equiv 1 \pmod{n}\) สำหรับตัวประกอบเฉพาะ \(p_i\) แต่ละตัว หากผ่านการตรวจสอบทั้งหมด แสดงว่า g เป็นรากดั้งเดิม วิธีนี้เร็วกว่าการคำนวณเลขยกกำลังทั้งหมดของ g มาก

เครื่องมือที่เกี่ยวข้อง