ความสมภาคและเลขคณิตมอดุลาร์

เลขคณิตมอดุลาร์ศึกษาจำนวนเต็มภายใต้การหารด้วยตัวหารคงที่ (มอดุโล) โดยเปลี่ยนจำนวนเต็มให้เป็นริงจำกัด Z/nZ และเป็นเครื่องมือคำนวณที่ยืดหยุ่นที่สุดของทฤษฎีจำนวน

Definition

จำนวนเต็มสองจำนวนจะสมภาคกันมอดุโล n ถ้าผลต่างของจำนวนทั้งสองหารด้วย n ลงตัว เลขคณิตมอดุลาร์คือเลขคณิตของชั้นส่วนตกค้างที่เกิดขึ้น ซึ่งประกอบกันเป็นริงสลับที่ Z/nZ

Scope

หัวข้อนี้ครอบคลุมความสัมพันธ์สมภาคและชั้นส่วนตกค้าง, เลขคณิตใน Z/nZ, ความสมภาคเชิงเส้นและพหุนาม, ทฤษฎีบทเศษเหลือของจีน, ทฤษฎีบทเล็กของแฟร์มาต์และทฤษฎีบทของออยเลอร์, โครงสร้างของกรุปหน่วย, รากปฐมฐาน และอันดับของสมาชิก เป็นภาษาที่ใช้ในการอธิบายทฤษฎีจำนวนเบื้องต้นและเชิงคำนวณส่วนใหญ่

Core questions

• ความสมภาคเชิงเส้น ax สมภาคกับ b mod n มีผลเฉลยเมื่อใด และมีจำนวนเท่าใด?
• ทฤษฎีบทเศษเหลือของจีนแยก Z/nZ ออกเป็นผลคูณเหนือมอดุโลกำลังเฉพาะได้อย่างไร?
• เหตุใดทฤษฎีบทเล็กของแฟร์มาต์และทฤษฎีบทของออยเลอร์จึงเป็นจริง และกล่าวถึงอันดับของหน่วยอย่างไร?
• รากปฐมฐานมีอยู่สำหรับมอดุโลใดบ้าง ทำให้กรุปหน่วยเป็นวัฏจักร?

Key theories

ทฤษฎีบทเศษเหลือของจีน

หากมอดุโลเป็นจำนวนเฉพาะสัมพัทธ์กันเป็นคู่ๆ ระบบของความสมภาคพร้อมกันจะมีผลเฉลยเดียวมอดุโลผลคูณ หรือเทียบเท่า Z/nZ จะสมสัณฐานกับผลคูณของ Z เหนือตัวประกอบกำลังเฉพาะ

ทฤษฎีบทเล็กของแฟร์มาต์และทฤษฎีบทของออยเลอร์

สำหรับ a ที่เป็นจำนวนเฉพาะสัมพัทธ์กับ n, a ยกกำลังฟังก์ชันโทเทียนต์ของ n จะสมภาคกับหนึ่งมอดุโล n; กรณีจำนวนเฉพาะ (แฟร์มาต์) เป็นพื้นฐานของการทดสอบจำนวนเฉพาะ และกรณีทั่วไปเป็นพื้นฐานของ RSA

รากปฐมฐานและโครงสร้างกรุป

กรุปการคูณของหน่วยมอดุโล n เป็นวัฏจักรก็ต่อเมื่อ n เป็นหนึ่ง, สอง, สี่, กำลังของจำนวนเฉพาะคี่ หรือสองเท่าของกำลังของจำนวนเฉพาะคี่; ตัวก่อกำเนิดคือรากปฐมฐาน ซึ่งให้ลอการิทึมไม่ต่อเนื่อง

Clinical relevance

เลขคณิตมอดุลาร์เป็นกลไกการคำนวณหลักของการเข้ารหัส (RSA, Diffie-Hellman, แผนการเข้ารหัสแบบเส้นโค้งเชิงวงรี), การตรวจสอบผลรวมและตรวจจับข้อผิดพลาด (ISBN, ฟังก์ชันแฮช) และการสร้างตัวเลขสุ่มเทียม ทำให้เป็นส่วนหนึ่งของทฤษฎีจำนวนที่ถูกนำไปใช้งานอย่างแพร่หลายที่สุด

History

แม้ว่ากรณีพิเศษจะปรากฏในคณิตศาสตร์จีนและอินเดียโบราณ (ปัญหาเศษเหลือที่ตั้งชื่อตามอดีต) แต่ทฤษฎีความสมภาคอย่างเป็นระบบถูกนำเสนอโดยเกาส์ใน Disquisitiones Arithmeticae (ค.ศ. 1801) ซึ่งเขากำหนดสัญกรณ์และพิสูจน์ผลลัพธ์เชิงโครงสร้างที่สำคัญ

Key figures

• Carl Friedrich Gauss
• Pierre de Fermat
• Leonhard Euler

Seminal works

• irelandRosen1990

Frequently asked questions

สัญกรณ์ a สมภาคกับ b mod n หมายความว่าอย่างไร?

หมายความว่า n หารผลต่าง a ลบ b ลงตัว หรือเทียบเท่า a และ b ให้เศษเหลือเท่ากันเมื่อหารด้วย n

เหตุใด RSA จึงอาศัยทฤษฎีบทของออยเลอร์?

การเข้ารหัสและถอดรหัส RSA เป็นการยกกำลังมอดุลาร์ที่เมื่อประกอบกันแล้วจะคืนข้อความต้นฉบับได้อย่างแม่นยำ เนื่องจากทฤษฎีบทของออยเลอร์รับประกันว่าเลขชี้กำลังที่เกี่ยวข้องจะทำหน้าที่เป็นเอกลักษณ์มอดุโลกุญแจ