ทฤษฎีบทของออยเลอร์ (Euler's Theorem) ในความปลอดภัยข้อมูล

ทฤษฎีบทของออยเลอร์ (Euler's Theorem)

การขยายของ Fermat's Little Theorem สำหรับ Modulus ที่ไม่ใช่ Prime

ข้อความทฤษฎีบท

ถ้า a และ n เป็นจำนวนเต็มที่ หารร่วมมากได้ 1 (gcd(a,n)=1) แล้ว:

a^φ(n) ≡ 1 (mod n)

โดย φ(n) = Euler's Totient Function = จำนวนจำนวนเต็มบวก ≤ n ที่หารร่วมกับ n ได้ 1

การพิสูจน์ (Sketch)

1. ให้ R = {x₁, x₂, ..., x_φ(n)} = ชุดตัวเลข < n ที่ gcd(xᵢ,n)=1
2. คูณทุกตัวด้วย a (mod n): S = {a·x₁, a·x₂, ..., a·x_φ(n)} mod n
3. เพราะ gcd(a,n)=1 และ gcd(xᵢ,n)=1 → gcd(a·xᵢ,n)=1 → S เป็น Permutation ของ R
4. คูณทุกตัว: ∏(a·xᵢ) ≡ ∏xᵢ (mod n)
5. a^φ(n) · ∏xᵢ ≡ ∏xᵢ (mod n)
6. ตัด ∏xᵢ (gcd(∏xᵢ, n)=1) → a^φ(n) ≡ 1 (mod n)

Euler's Totient Function φ(n)

กฎการคำนวณ

• φ(1) = 0
• φ(p) = p-1 (p เป็นเฉพาะ)
• φ(m×n) = φ(m) × φ(n) ถ้า gcd(m,n)=1 (Multiplicative)
• φ(pᵉ) = pᵉ - pᵉ⁻¹ = pᵉ⁻¹(p-1) (p เฉพาะ)

สูตรทั่วไป

ถ้า n = p₁ᵉ¹ × p₂ᵉ² × ... × pₖᵉᵏ (Factorization)

φ(n) = (p₁ᵉ¹ - p₁ᵉ¹⁻¹) × (p₂ᵉ² - p₂ᵉ²⁻¹) × ... × (pₖᵉᵏ - pₖᵉᵏ⁻¹)

= n × ∏(1 - 1/pᵢ)

การประยุกต์ใน Cryptography

1. RSA Key Generation

• n = p × q (p,q Primes)
• φ(n) = (p-1)(q-1)
• เลือก e: gcd(e, φ(n)) = 1
• คำนวณ d ≡ e⁻¹ (mod φ(n)) ← ใช้ Extended Euclidean Algorithm
• Public Key: (n, e), Private Key: (n, d) หรือ (p, q, d)

2. การถอดรหัส RSA

Cᵈ ≡ Mᵉᵈ ≡ Mᵏφ⁽ⁿ⁾⁺¹ ≡ M (mod n) (โดย Euler's Theorem)

3. CRT (Chinese Remainder Theorem) Optimization

• คำนวณ M mod p และ M mod q แยกกัน → เร็วขึ้น 4 เท่า
• ต้องการ p, q (เก็บใน Private Key)

ความสำคัญ

Euler's Theorem เป็น พื้นฐานทางคณิตศาสตร์ของ RSA และระบบ Public-Key หลายระบบ ทำให้สามารถคำนวณ Modular Inverse และยกกำลัง Modulo ได้อย่างถูกต้อง