1. สมการคอนกรูเอนซ์เชิงเส้น ax ≡ b (mod m):
- การมีอยู่ของคำตอบ:สมการมีคำตอบก็ต่อเมื่อ gcd(a, m) | b (b หารด้วย gcd(a, m) ลงตัว)
- จำนวนคำตอบ:ถ้ามีคำตอบ จะมี d = gcd(a, m) คำตอบที่แตกต่างกันใน modulo m
- วิธีการแก้:
- คำนวณ d = gcd(a, m)
- ตรวจสอบ d | b ถ้าไม่เป็นไปตามจะไม่มีคำตอบ
- หารทั้งสองข้างด้วย d: (a/d)x ≡ (b/d) (mod m/d)
- ใช้ขั้นตอนวิธี Euclid แบบขยายเพื่อหาตัวผกผันของ a/d ใน modulo m/d
- คำนวณ x₀ = a' × (b/d) mod (m/d)
- คำตอบทั่วไป: x = x₀ + k(m/d) โดย k = 0, 1, ..., d-1
2. สมการคอนกรูเอนซ์เลขชี้กำลัง a^x ≡ b (mod m) (ปัญหาลอการิทึมไม่ต่อเนื่อง):
- คำอธิบายปัญหา:กำหนด a, b, m จงหาจำนวนเต็มไม่ลบ x ที่น้อยที่สุดที่ a^x ≡ b (mod m)
- การมีอยู่ของคำตอบ:
- ถ้า gcd(a, m) = 1 และ b อยู่ในกลุ่มวัฏจักรที่ a สร้างขึ้นภายใต้ modulo m จะมีคำตอบ
- วิธีการตรวจสอบ: แจงนับยกกำลังของ a จนกว่าจะพบ b หรือครบหนึ่งรอบ
- วิธีการแก้:
- การค้นหาแบบ brute force ในช่วงเล็ก:แจงนับ x = 0, 1, 2, ... จนกว่าจะพบคำตอบหรือถึงขีดจำกัด
- อัลกอริทึม Baby-step Giant-step:ความซับซ้อน O(√m) เหมาะกับขนาดกลาง
- อัลกอริทึม Pollard's rho:เหมาะกับโมดูลัสจำนวนเฉพาะขนาดใหญ่
- คาบ:ถ้า x₀ เป็นคำตอบ แล้ว x = x₀ + kφ(m) ก็เป็นคำตอบด้วย (φ(m) คือฟังก์ชันออยเลอร์)
3. สถานการณ์การใช้งาน:
- วิทยาการเข้ารหัส:RSA, การแลกเปลี่ยนคีย์ Diffie-Hellman, การเข้ารหัส ElGamal
- ทฤษฎีจำนวน:รากดั้งเดิม, Quadratic Residue, ทฤษฎีบทเศษเหลือจีน
- การสร้างเลขสุ่ม:ตัวสร้างเลขสุ่มเชิงเส้น (LCG)
- ฟังก์ชันแฮช:การประยุกต์ใช้การดำเนินการ modulo ใน Hash Table
- การเขียนโปรแกรมแข่งขัน:เลขยกกำลังด่วน, ตัวผกผัน modulo, โจทย์ทฤษฎีจำนวน
ความซับซ้อนของอัลกอริทึม:
- สมการคอนกรูเอนซ์เชิงเส้น:O(log m) (ความซับซ้อนของขั้นตอนวิธี Euclid แบบขยาย)
- สมการคอนกรูเอนซ์เลขชี้กำลัง (Brute Force):O(n) โดย n คือขีดจำกัดการค้นหา
- สมการคอนกรูเอนซ์เลขชี้กำลัง (BSGS):O(√m) ต้องการพื้นที่เพิ่ม
ทฤษฎีบทสำคัญ:
- ทฤษฎีบทเบซู:สมการ ax + my = gcd(a, m) มีคำตอบเป็นจำนวนเต็มเสมอ
- ทฤษฎีบทเล็กของแฟร์มา:ถ้า p เป็นจำนวนเฉพาะและ gcd(a, p) = 1 แล้ว a^(p-1) ≡ 1 (mod p)
- ทฤษฎีบทออยเลอร์:ถ้า gcd(a, m) = 1 แล้ว a^φ(m) ≡ 1 (mod m)
- ทฤษฎีบทเศษเหลือจีน:สามารถแก้ระบบสมการคอนกรูเอนซ์ได้