เครื่องคำนวณอัลกอริทึมยูคลิดขยาย

เครื่องคำนวณอัลกอริทึมยูคลิดขยาย ใช้สำหรับคำนวณหาตัวหารร่วมมาก (ห.ร.ม.) ของจำนวนเต็มสองจำนวน และหาค่าสัมประสิทธิ์ของเบซู ซึ่งเป็นจำนวนเต็ม s และ t ที่สอดคล้องกับ gcd(a, b) = s·a + t·b นอกจากการคำนวณ ห.ร.ม. แล้ว เครื่องมือนี้ยังแสดงตารางการหารทีละขั้นตอนแบบเคลื่อนไหว การแทนที่ย้อนกลับ และการคำนวณตัวผกผันมอดุลาร์ ซึ่งเหมาะอย่างยิ่งสำหรับวิชาทฤษฎีจำนวน การศึกษาวิทยาการรหัสลับ และการโปรแกรมเชิงแข่งขัน

อัลกอริทึมยูคลิดขยายคืออะไร?

อัลกอริทึมยูคลิดขยาย (Extended Euclidean Algorithm หรือ EEA) เป็นส่วนขยายของอัลกอริทึมยูคลิดแบบคลาสสิก ในขณะที่อัลกอริทึมพื้นฐานหา ห.ร.ม. (a, b) โดยการหารต่อเนื่อง รุ่นที่ขยายนี้จะติดตามลำดับจำนวนเต็มสองลำดับพร้อมกันเพื่อบันทึกว่าเศษเหลือแต่ละตัวสามารถแสดงในรูปการรวมเชิงเส้นของค่าเริ่มต้นได้อย่างไร

วิธีการทำงานของอัลกอริทึม

EEA จะรักษาค่าสามคู่ — (r, s, t) — ผ่านแต่ละขั้นตอนการหาร:

1. เริ่มต้น: r₀ = |a|, r₁ = |b|, s₀ = 1, s₁ = 0, t₀ = 0, t₁ = 1
2. แต่ละขั้นตอน: คำนวณผลหาร q = ⌊rₙ₋₁ / rₙ⌋ จากนั้นอัปเดต rₙ₊₁ = rₙ₋₁ − q·rₙ, sₙ₊₁ = sₙ₋₁ − q·sₙ, tₙ₊₁ = tₙ₋₁ − q·tₙ
3. หยุดเมื่อเศษเหลือ = 0; เศษเหลือก่อนหน้าคือ gcd(a, b)
4. ค่า s และ t ที่สอดคล้องกันคือสัมประสิทธิ์ของเบซู

ตัวอย่างทีละขั้นตอน: gcd(252, 105)

ผลลัพธ์: gcd(252, 105) = 21 พร้อมเอกลักษณ์ของเบซู: 21 = (−2) × 252 + 5 × 105 (s = −2, t = 5) ลองใช้เครื่องคำนวณด้านบนเพื่อหาค่าสัมประสิทธิ์ที่แน่นอนสำหรับตัวเลขอื่นได้

การประยุกต์ใช้งานของอัลกอริทึมยูคลิดขยาย

1. ตัวผกผันมอดุลาร์ (วิทยาการรหัสลับ)

การประยุกต์ใช้ที่สำคัญที่สุดคือการคำนวณตัวผกผันมอดุลาร์ (Modular Inverse) ถ้า gcd(a, m) = 1 สัมประสิทธิ์ของเบซู s จะสอดคล้องกับ:

ตัวผกผันมอดุลาร์มีความจำเป็นใน การเข้ารหัส RSA (การคำนวณเลขชี้กำลังกุญแจส่วนตัว d), การแลกเปลี่ยนกุญแจ Diffie-Hellman และวิทยาการรหัสลับแบบเส้นโค้งวงรี

2. การแก้สมการไดโอแฟนไทน์เชิงเส้น

สมการ ax + by = c จะมีคำตอบเป็นจำนวนเต็มก็ต่อเมื่อ gcd(a, b) หาร c ลงตัว หากเป็นเช่นนั้น คำตอบเฉพาะอย่างหนึ่งคือ x₀ = s·(c/d), y₀ = t·(c/d) โดยที่ d = gcd(a, b) และ s, t คือสัมประสิทธิ์ของเบซู

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

EEA ถูกใช้ในการพิสูจน์เชิงสร้างสรรค์และการคำนวณทฤษฎีบทเศษเหลือของจีน (Chinese Remainder Theorem) — เพื่อหาค่า x ที่ทำให้ x ≡ a₁ (mod m₁) และ x ≡ a₂ (mod m₂) — โดยการคำนวณตัวผกผันมอดุลาร์ของตัวมอดุลัส

4. การลดรูปเศษส่วนและ ค.ร.น.

gcd(a, b) = 1 ยืนยันว่า a/b อยู่ในรูปเศษส่วนอย่างต่ำแล้ว และ ค.ร.น. คือ lcm(a, b) = |a·b| / gcd(a, b)

สัมประสิทธิ์ของเบซูไม่ได้มีเพียงชุดเดียว

สัมประสิทธิ์ของเบซู s และ t ไม่ได้เป็นค่าเฉพาะเจาะจงชุดเดียว หาก (s, t) เป็นคำตอบหนึ่ง แล้ว (s + k·(b/d), t − k·(a/d)) ก็เป็นคำตอบสำหรับจำนวนเต็ม k ใดๆ เช่นกัน โดยที่ d = gcd(a, b) โดยทั่วไป EEA จะคืนค่าคำตอบที่ |s| ≤ |b/d| และ |t| ≤ |a/d|

ความซับซ้อนของเวลา

อัลกอริทึมยูคลิดขยายทำงานใน O(log min(a, b)) รอบการหาร — เช่นเดียวกับอัลกอริทึมยูคลิดพื้นฐาน ตามทฤษฎีบทของลาเม (Lamé's theorem) จำนวนขั้นตอนจะไม่เกิน 5 เท่าของจำนวนหลักทศนิยมของตัวเลขที่น้อยกว่า ทำให้มีประสิทธิภาพสูงแม้ใช้กับจำนวนเต็มขนาดใหญ่ในงานด้านรหัสลับ

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

อัลกอริทึมยูคลิดขยายคืออะไร?

อัลกอริทึมยูคลิดขยายคือส่วนขยายของอัลกอริทึม ห.ร.ม. ของยูคลิด เพื่อคำนวณหาค่าสัมประสิทธิ์ของเบซู s และ t ที่สอดคล้องกับ gcd(a, b) = s·a + t·b โดยจะติดตามว่าเศษเหลือแต่ละตัวสามารถเขียนในรูปการรวมเชิงเส้นของ a และ b ได้อย่างไรตลอดกระบวนการหาร

สัมประสิทธิ์ของเบซูคืออะไร?

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

ฉันจะหาตัวผกผันมอดุลาร์โดยใช้อัลกอริทึมยูคลิดขยายได้อย่างไร?

หาก gcd(a, b) = 1 (a และ b เป็นจำนวนเฉพาะสัมพัทธ์กัน) สัมประสิทธิ์ของเบซู s จะสอดคล้องกับ s·a ≡ 1 (mod b) ตัวผกผันมอดุลาร์ของ a mod b คือ s mod b (ปรับให้เป็นค่าบวก) เครื่องคำนวณนี้จะแสดงค่าดังกล่าวให้เห็นโดยตรงในผลลัพธ์

ตัวผกผันมอดุลาร์จะไม่มีคำตอบเมื่อใด?

ตัวผกผันมอดุลาร์ของ a modulo m จะมีอยู่ก็ต่อเมื่อ gcd(a, m) = 1 หาก gcd(a, m) > 1 จะไม่มีจำนวนเต็ม x ใดที่สอดคล้องกับ a·x ≡ 1 (mod m)

ความซับซ้อนของเวลาของอัลกอริทึมยูคลิดขยายคืออะไร?

การหาร O(log min(a, b)) ครั้ง เช่นเดียวกับอัลกอริทึมยูคลิดพื้นฐาน ตามทฤษฎีบทของลาเม จำนวนขั้นตอนจะถูกจำกัดไว้ที่ไม่เกิน 5 เท่าของจำนวนหลักของค่าที่น้อยกว่า ทำให้ทำงานได้รวดเร็วมาก

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

• Extended Euclidean Algorithm - Wikipedia
• Bézout's Identity - Wikipedia
• Modular Multiplicative Inverse - Wikipedia