0Pricing
Cryptology Academy · บทเรียน

GCD ฟังก์ชันทอเทียนของออยเลอร์ และบทนำทฤษฎีจำนวน

ประยุกต์ใช้ GCD และฟังก์ชันทอเทียนของออยเลอร์กับปัญหาการเข้ารหัสจริง

GCD ฟังก์ชันทอเทียนของออยเลอร์ และบทนำทฤษฎีจำนวน เป็นบทเรียน Cryptology Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Cryptology Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Cryptology Academy มีบทเรียนทั้งหมด 4 บทเรียน

ยินดีต้อนรับ

GCD และฟังก์ชันโทเชียนของ Euler เป็นเครื่องมือสำคัญใน RSA และระบบกุญแจสาธารณะอื่น ๆ อีกมากมาย มาเรียนรู้ให้เชี่ยวชาญผ่านตัวอย่างกัน

ตัวหารร่วมมาก (GCD)

GCD(a, b) คือจำนวนเต็มที่มากที่สุดซึ่งหารทั้ง a และ b ลงตัวโดยไม่มีเศษเหลือ GCD(12, 8) = 4 หาก GCD(a, m) = 1 เราจะกล่าวว่า a และ m เป็นจำนวนที่เป็น coprime หรือเป็นจำนวนเฉพาะสัมพัทธ์กัน

อัลกอริทึมยุคลิด

GCD(a, b) = GCD(b, a mod b), กรณีฐานคือ GCD(a, 0) = a GCD(48, 18): = GCD(18, 12) = GCD(12, 6) = GCD(6, 0) = 6 Python: import math; math.gcd(48, 18) → 6

อัลกอริทึมยุคลิดแบบขยาย

เวอร์ชันแบบขยายจะค้นหาจำนวนเต็ม x, y ที่ทำให้ ax + by = GCD(a,b) เมื่อ GCD(a,m)=1 ค่า x คืออินเวอร์สแบบมอดุลาร์ของ a mod m นี่คือวิธีที่ RSA ใช้คำนวณกุญแจส่วนตัว

ฟังก์ชันโทเชียนของ Euler φ(n)

φ(n) นับจำนวนเต็มตั้งแต่ 1 ถึง n ที่เป็น coprime กับ n φ(10) = 4 เพราะ {1, 3, 7, 9} เป็น coprime กับ 10 φ(p) = p-1 สำหรับจำนวนเฉพาะ p ทุกจำนวน

โทเชียนของผลคูณ

สำหรับ RSA: n = p×q (p,q เป็นจำนวนเฉพาะ) φ(n) = φ(p)×φ(q) = (p-1)(q-1) ตัวอย่าง: p=5, q=11: φ(55) = 4×10 = 40 นี่คือเหตุผลที่การแยกตัวประกอบ n ทำลาย RSA ได้ เพราะเผยค่า φ(n)

ทฤษฎีบทของ Euler

หาก GCD(a,n)=1: a^φ(n) ≡ 1 (mod n) นี่คือพื้นฐานทางคณิตศาสตร์ของการถอดรหัส RSA: M = C^d mod n เพราะ e×d ≡ 1 (mod φ(n))

การคำนวณ d ใน RSA

เลือก e = 65537 (เลขชี้กำลังสาธารณะของ RSA ที่ใช้กันทั่วไป) คำนวณ d = e^(-1) mod φ(n) โดยใช้อัลกอริทึมยุคลิดแบบขยาย ตรวจสอบว่า e×d mod φ(n) == 1

โทเชียนใน Python

def totient(n): from math import gcd return sum(1 for i in range(1, n+1) if gcd(i, n) == 1) # Fast for n=p*q: def rsa_totient(p, q): return (p-1)*(q-1)

แลมบ์ดาของ Carmichael

RSA สมัยใหม่ใช้ฟังก์ชันแลมบ์ดาของ Carmichael λ(n) = lcm(p-1, q-1) แทน φ(n) ฟังก์ชันนี้ให้มอดูลัสที่เล็กกว่าแต่เทียบเท่ากัน PKCS#1 v2 และ NIST แนะนำให้ใช้ λ(n)

สรุปการใช้งานจริง

GCD: ตรวจสอบว่า e เป็น coprime กับ φ(n) หรือไม่ อัลกอริทึมยุคลิดแบบขยาย: คำนวณกุญแจส่วนตัว d โทเชียน: กำหนดกลุ่มเลขชี้กำลังสำหรับการยกกำลังแบบมอดุลาร์ ทั้งสามอย่างถูกใช้ในการสร้างกุญแจ RSA ทุกครั้ง

ตรวจสอบความเข้าใจ

สำหรับ RSA ที่มี p=7 และ q=11 ค่า φ(n) คือเท่าใด

ทบทวน

ยอดเยี่ยม! ตอนนี้ GCD, อัลกอริทึมยุคลิด และโทเชียนของ Euler อยู่ในชุดเครื่องมือของคุณแล้ว ต่อไปเราจะศึกษา XOR และการดำเนินการระดับบิต ซึ่งเป็นองค์ประกอบพื้นฐานของรหัสลับแบบสมมาตร

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

บทเรียน “GCD ฟังก์ชันทอเทียนของออยเลอร์ และบทนำทฤษฎีจำนวน” ฟรีหรือไม่

ใช่ — ข้อความเต็มของ “GCD ฟังก์ชันทอเทียนของออยเลอร์ และบทนำทฤษฎีจำนวน” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Cryptology Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Cryptology Academy มีบทเรียนทั้งหมด 4 บทเรียน

คุณจะเรียนรู้อะไรในบทเรียน “GCD ฟังก์ชันทอเทียนของออยเลอร์ และบทนำทฤษฎีจำนวน”

ประยุกต์ใช้ GCD และฟังก์ชันทอเทียนของออยเลอร์กับปัญหาการเข้ารหัสจริง คุณปฏิบัติ Cryptology Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน

คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Cryptology Academy หรือไม่

ไม่จำเป็นต้องมีประสบการณ์มาก่อน Cryptology Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน

บทเรียน “GCD ฟังก์ชันทอเทียนของออยเลอร์ และบทนำทฤษฎีจำนวน” ใช้เวลานานแค่ไหน

บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย

ฉันเขียนและรันโค้ดในบทเรียน Cryptology Academy นี้ได้ไหม

ได้ บทเรียน Cryptology Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ

บทเรียนทั้งหมดในหลักสูตรนี้

  1. พื้นฐานเลขฐานสองและเลขฐานสิบหก
  2. พื้นฐานเลขคณิตมอดุลาร์
  3. จำนวนเฉพาะและการแยกตัวประกอบ
  4. GCD ฟังก์ชันทอเทียนของออยเลอร์ และบทนำทฤษฎีจำนวน
← กลับไปที่ Cryptology Academy