เครื่องคิดเลขฟังก์ชันโทเชียนต์ออยเลอร์

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

ฟังก์ชันโทเชียนต์ของออยเลอร์คืออะไร?

ฟังก์ชันโทเชียนต์ของออยเลอร์ φ(n) หรือที่รู้จักกันในชื่อ ฟังก์ชันฟีของออยเลอร์ คือการนับจำนวนของจำนวนเต็มบวกตั้งแต่ 1 ถึง n ที่เป็น จำนวนเฉพาะสัมพัทธ์ (coprime) กับ n จำนวนสองจำนวนจะเป็นจำนวนเฉพาะสัมพัทธ์กันเมื่อตัวหารร่วมมาก (ห.ร.ม.) ของทั้งสองเท่ากับ 1

ตัวอย่างเช่น φ(12) = 4 เพราะมีตัวเลขสี่จำนวน ได้แก่ 1, 5, 7 และ 11 ที่เป็นจำนวนเฉพาะสัมพัทธ์กับ 12 ในบรรดาจำนวนเต็มตั้งแต่ 1 ถึง 12

สูตรผลคูณ

วิธีที่มีประสิทธิภาพที่สุดในการคำนวณ φ(n) คือการใช้ การแยกตัวประกอบเฉพาะ ของ n หาก \(n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}\) ดังนั้น:

หมายความว่าเราคูณ n ด้วย \((1 - 1/p)\) สำหรับแต่ละตัวประกอบเฉพาะ ที่แตกต่างกัน p ของ n เลขชี้กำลังจะไม่สำคัญ สิ่งที่สำคัญคือจำนวนเฉพาะที่แตกต่างกันเท่านั้น

คุณสมบัติหลัก

ทฤษฎีบทของออยเลอร์

ทฤษฎีบทของออยเลอร์ เป็นผลลัพธ์สำคัญที่ทำให้ฟังก์ชันโทเชียนต์มีความสำคัญอย่างยิ่งในวิทยาการรหัสลับ:

นี่คือการขยายความทั่วไปของ ทฤษฎีบทเล็กของแฟร์มาต์ (ซึ่งเป็นกรณีพิเศษเมื่อ n เป็นจำนวนเฉพาะ) โดยเป็นรากฐานทางคณิตศาสตร์ของการเข้ารหัส RSA

วิธีใช้งานเครื่องคิดเลขนี้

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

ความเชื่อมโยงกับการเข้ารหัส RSA

ใน วิทยาการรหัสลับ RSA ฟังก์ชันโทเชียนต์ของออยเลอร์มีบทบาทสำคัญ:

1. เลือกจำนวนเฉพาะขนาดใหญ่สองจำนวน p และ q คำนวณ n = p × q
2. คำนวณ φ(n) = (p−1)(q−1)
3. เลือกเลขชี้กำลังสาธารณะ e โดยที่ ห.ร.ม.(e, φ(n)) = 1
4. คำนวณเลขชี้กำลังส่วนตัว d โดยที่ e × d ≡ 1 (mod φ(n))

ความปลอดภัยของ RSA ขึ้นอยู่กับความยากในการคำนวณ φ(n) โดยไม่ทราบการแยกตัวประกอบของ n หากผู้โจมตีสามารถคำนวณ φ(n) ได้อย่างมีประสิทธิภาพ พวกเขาก็สามารถถอดรหัส RSA ได้

ค่าทั่วไปของ φ(n)

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

ฟังก์ชันโทเชียนต์ของออยเลอร์คืออะไร?

ฟังก์ชันโทเชียนต์ของออยเลอร์ φ(n) หรือเรียกอีกอย่างว่าฟังก์ชันฟีของออยเลอร์ คือการนับจำนวนของจำนวนเต็มบวกตั้งแต่ 1 ถึง n ที่เป็นจำนวนเฉพาะสัมพัทธ์ (coprime) กับ n จำนวนสองจำนวนจะเป็นจำนวนเฉพาะสัมพัทธ์กันเมื่อตัวหารร่วมมาก (ห.ร.ม.) ของทั้งสองคือ 1 ตัวอย่างเช่น φ(12) = 4 เพราะมีเพียง 1, 5, 7 และ 11 เท่านั้นที่เป็นจำนวนเฉพาะสัมพัทธ์กับ 12

คำนวณฟังก์ชันโทเชียนต์ของออยเลอร์ได้อย่างไร?

การคำนวณ φ(n): (1) หาการแยกตัวประกอบเฉพาะของ n (2) ใช้สูตรผลคูณ: φ(n) = n × ∏(1 − 1/p) สำหรับแต่ละตัวประกอบเฉพาะ p ที่แตกต่างกันของ n ตัวอย่างเช่น φ(12) = 12 × (1−1/2) × (1−1/3) = 12 × 1/2 × 2/3 = 4 สำหรับจำนวนเฉพาะ p, φ(p) = p−1 สำหรับกำลังของจำนวนเฉพาะ p^k, φ(p^k) = p^k − p^(k−1)

ทำไมฟังก์ชันโทเชียนต์ของออยเลอร์จึงสำคัญในการเข้ารหัส RSA?

ในการเข้ารหัส RSA โมดูลัส n = p × q คือผลคูณของจำนวนเฉพาะขนาดใหญ่สองจำนวน ค่าโทเชียนต์ φ(n) = (p−1)(q−1) ใช้เพื่อคำนวณรหัสส่วนตัว: เลขชี้กำลังการถอดรหัส d ต้องสอดคล้องกับ e × d ≡ 1 (mod φ(n)) โดยที่ e คือเลขชี้กำลังการเข้ารหัสสาธารณะ หากไม่ทราบ φ(n) — ซึ่งต้องอาศัยการแยกตัวประกอบ n — การคำนวณ d จะเป็นสิ่งที่เป็นไปไม่ได้ในเชิงคำนวณ

ทฤษฎีบทของออยเลอร์คืออะไรและเกี่ยวข้องกับฟังก์ชันโทเชียนต์อย่างไร?

ทฤษฎีบทของออยเลอร์ระบุว่าหาก a และ n เป็นจำนวนเฉพาะสัมพัทธ์กันแล้ว a^φ(n) ≡ 1 (mod n) นี่คือการขยายความทั่วไปของทฤษฎีบทเล็กของแฟร์มาต์ (ซึ่งใช้เมื่อ n เป็นจำนวนเฉพาะ) เป็นพื้นฐานสำคัญในเลขคณิตมอดุลาร์และวิทยาการรหัสลับ โดยเป็นรากฐานทางคณิตศาสตร์สำหรับการเข้ารหัส RSA และการยกกำลังมอดุลาร์อย่างมีประสิทธิภาพ

คุณสมบัติหลักของฟังก์ชันโทเชียนต์ของออยเลอร์มีอะไรบ้าง?

คุณสมบัติหลัก ได้แก่: (1) φ(1) = 1 (2) สำหรับจำนวนเฉพาะ p: φ(p) = p−1 (3) สำหรับกำลังของจำนวนเฉพาะ p^k: φ(p^k) = p^(k−1)(p−1) (4) คุณสมบัติการคูณ: ถ้า ห.ร.ม.(m,n) = 1 แล้ว φ(m×n) = φ(m)×φ(n) (5) ผลรวมเหนือตัวหาร: Σ φ(d) = n สำหรับตัวหาร d ทั้งหมดของ n (6) φ(n) จะเป็นเลขคู่เสมอสำหรับ n > 2

การที่เลขสองจำนวนเป็นจำนวนเฉพาะสัมพัทธ์กันหมายความว่าอย่างไร?

จำนวนเต็ม a และ b จะเป็นจำนวนเฉพาะสัมพัทธ์กัน (หรือเรียกอีกอย่างว่า relative prime) หากตัวหารร่วมมากของทั้งสองคือ 1 หมายความว่าทั้งสองไม่มีตัวประกอบเฉพาะร่วมกัน ตัวอย่างเช่น 8 และ 15 เป็นจำนวนเฉพาะสัมพัทธ์กันเพราะ ห.ร.ม.(8,15) = 1 แม้ว่าทั้งสองจะไม่ใช่จำนวนเฉพาะก็ตาม ฟังก์ชันโทเชียนต์ φ(n) จะนับว่ามีจำนวนเต็มกี่จำนวนตั้งแต่ 1 ถึง n ที่เป็นจำนวนเฉพาะสัมพัทธ์กับ n

แหล่งข้อมูลเพิ่มเติม

• Euler's Totient Function - Wikipedia
• RSA Cryptosystem - Wikipedia
• Euler's Theorem - Wikipedia