เครื่องคำนวณฟังก์ชันออยเลอร์โทเชียนต์

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

ฟังก์ชันโทเชียนต์ของออยเลอร์ φ(n) นับว่ามีจำนวนเต็มตั้งแต่ 1 ถึง n กี่ตัวที่ไม่มีตัวประกอบร่วมกับ n และคำนวณจากการแยกตัวประกอบเฉพาะของ n เป็น φ(n) = n × ∏(1 − 1/p) เหนือจำนวนเฉพาะ p ที่แตกต่างกันแต่ละตัวที่หาร n ลงตัว สำหรับจำนวนเฉพาะ p เอง φ(p) = p − 1 เพราะจำนวนเต็มบวกทุกตัวที่น้อยกว่าเป็นจำนวนเฉพาะสัมพัทธ์กับมันโดยอัตโนมัติ

ฟังก์ชันโทเชียนต์เป็นกลไกทางคณิตศาสตร์เบื้องหลังการเข้ารหัส RSA: การสร้างกุญแจคูณจำนวนเฉพาะขนาดใหญ่สองตัว p และ q ได้ n = pq จากนั้นใช้ φ(n) = (p−1)(q−1) เพื่อคำนวณคู่เลขชี้กำลังสาธารณะ/ส่วนตัวที่ใช้ได้ นอกจากนี้ยังเป็นพื้นฐานของทฤษฎีบทของออยเลอร์ในทฤษฎีจำนวน ใช้หาอินเวอร์สมอดูลาร์และลดเลขชี้กำลังขนาดใหญ่ในการคำนวณด้านการเข้ารหัสและการแข่งขันเขียนโปรแกรม