หลักการ:
Extended Euclidean Algorithm ไม่เพียงคำนวณ gcd(a, m) ของจำนวนเต็ม a และ m แต่ยังหาค่า x และ y ที่ทำให้ ax + my = gcd(a, m)。
นี่คือการประยุกต์ใช้ Bézout's Identity
ขั้นตอนวิธี:
- Euclidean Algorithm:ใช้การหารแบบยุคลิดคำนวณ gcd(a, m) บันทึกผลหารและเศษในแต่ละขั้น
- Back-substitution:เริ่มจากขั้นสุดท้ายย้อนกลับ แทนค่าเศษแต่ละตัวเป็นผลรวมเชิงเส้นของ a และ m
- หาสัมประสิทธิ์:ได้สัมประสิทธิ์ x และ y ที่ทำให้ ax + my = gcd(a, m)
Modular Inverse:
เมื่อ gcd(a, m) = 1 (a และ m coprime) จะมี inverse การคูณของ a ใน modulo m เขียนแทนด้วย a-1 mod m โดย x คือ modular inverse ซึ่งทำให้ a × x ≡ 1 (mod m)。
ถ้า x เป็นลบ ต้องปรับเป็นบวก: x' = x mod m
การประยุกต์ใช้งาน:
- วิทยาการเข้ารหัส:ใน RSA algorithm ใช้หา private key ต้องใช้ modular inverse
- ทฤษฎีจำนวน:แก้สมการเชิงเส้น ax ≡ b (mod m)
- คณิตศาสตร์เชิงการจัด:คำนวณ modulo ของจำนวนเชิงซ้อน (Lucas theorem ฯลฯ)
- การเขียนโปรแกรมแข่งขัน:คำนวณ modular inverse อย่างรวดเร็ว หลีกเลี่ยงปัญหาความแม่นยำจากการหาร
ความซับซ้อนด้านเวลา:
O(log min(a, m)) เท่ากับ Euclidean Algorithm