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

จำนวนเฉพาะและการแยกตัวประกอบ

เรียนรู้ว่าเหตุใดจำนวนเฉพาะจึงเป็นรากฐานของการเข้ารหัสด้วยกุญแจสาธารณะ

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

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

จำนวนเฉพาะหารลงตัวด้วย 1 และตัวมันเองเท่านั้น จำนวนเหล่านี้เปรียบเสมือนอะตอมของการคูณ และเป็นรากฐานของ RSA, Diffie-Hellman และระบบการเข้ารหัสอื่น ๆ อีกมากมาย

คำจำกัดความและตัวอย่าง

จำนวนเฉพาะ: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ... จำนวนหนึ่งจะเป็นจำนวนเฉพาะหากตัวหารบวกเพียงตัวเดียวของมันคือ 1 และตัวมันเอง ตามข้อตกลง 1 ไม่ใช่จำนวนเฉพาะ

ทฤษฎีบทมูลฐานของเลขคณิต

จำนวนเต็มทุกจำนวนที่มากกว่า 1 สามารถแยกตัวประกอบเป็นจำนวนเฉพาะได้ด้วยวิธีเดียวเท่านั้น (ไม่นับลำดับ) 60 = 2² × 3 × 5 ความเป็นเอกลักษณ์นี้เองที่ทำให้การเข้ารหัสที่อาศัยการแยกตัวประกอบทำงานได้

การหารทดลอง

def is_prime(n): if n < 2: return False for i in range(2, int(n**0.5)+1): if n % i == 0: return False return True ตรวจสอบถึงเพียง √n ก็พอ — หากไม่พบตัวประกอบที่น้อยกว่า √n แสดงว่า n เป็นจำนวนเฉพาะ

ตะแกรงของ Eratosthenes

หาจำนวนเฉพาะทั้งหมดที่ไม่เกิน N: เริ่มจากรายการจำนวน 2..N ขีดฆ่าพหุคูณของ 2 จากนั้นขีดฆ่าพหุคูณของ 3, 5 และอื่น ๆ จำนวนที่เหลือคือจำนวนเฉพาะ ทำงานด้วยความซับซ้อน O(N log log N)

การทดสอบความเป็นจำนวนเฉพาะ: Miller-Rabin

สำหรับจำนวนขนาดใหญ่ (2048 บิต) การหารทดลองช้าเกินไป Miller-Rabin เป็นการทดสอบเชิงความน่าจะเป็น: เรียกใช้ 40 ครั้ง แล้วความน่าจะเป็นที่จะเกิดข้อผิดพลาดจะน้อยกว่า 4^(-40)

การแยกตัวประกอบจำนวนเต็ม

เมื่อกำหนด n = p × q การค้นหา p และ q คือปัญหาการแยกตัวประกอบจำนวนเต็ม หาก n มีขนาด 2048 บิต อัลกอริทึมที่ดีที่สุดที่รู้จักต้องใช้การดำเนินการ 2^112 ครั้ง ซึ่งปัจจุบันทำได้ยากเกินไป

เหตุใด RSA จึงใช้จำนวนเฉพาะขนาดใหญ่สองจำนวน

มอดูลัสของ RSA คือ n = p × q การรู้ค่า n แต่ไม่รู้ p,q ทำให้คำนวณกุญแจส่วนตัวได้ยาก ความปลอดภัยทั้งหมดอาศัยความยากของการแยกตัวประกอบ n

การสร้างจำนวนเฉพาะขนาดใหญ่

from sympy import randprime p = randprime(2**1023, 2**1024) # random 1024-bit prime แนวทาง: สร้างจำนวนคี่แบบสุ่ม ทดสอบด้วย Miller-Rabin แล้วทำซ้ำจนกว่าจะได้จำนวนเฉพาะ

จำนวนเฉพาะปลอดภัยและจำนวนเฉพาะเข้มแข็ง

จำนวนเฉพาะปลอดภัยคือ p = 2q+1 โดย q ก็เป็นจำนวนเฉพาะด้วย จำนวนเฉพาะปลอดภัยช่วยต้านทานการโจมตีบางประเภทต่อ DH บางครั้ง RSA ใช้จำนวนเฉพาะเข้มแข็งเพื่อป้องกันการโจมตีของ Pollard แบบ p-1

ช่องว่างระหว่างจำนวนเฉพาะและความไม่มีที่สิ้นสุด

Euclid พิสูจน์ว่ามีจำนวนเฉพาะอยู่เป็นอนันต์ในปี 300 BCE ข้อคาดการณ์จำนวนเฉพาะคู่ (มีจำนวนเฉพาะ p, p+2 อยู่เป็นอนันต์) ยังพิสูจน์ไม่ได้ เราจะไม่มีวันขาดจำนวนเฉพาะสำหรับการเข้ารหัส

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

เหตุใด RSA จึงใช้จำนวนเฉพาะขนาดใหญ่

ทบทวน

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

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

บทเรียน “จำนวนเฉพาะและการแยกตัวประกอบ” ฟรีหรือไม่

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

คุณจะเรียนรู้อะไรในบทเรียน “จำนวนเฉพาะและการแยกตัวประกอบ”

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

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

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

บทเรียน “จำนวนเฉพาะและการแยกตัวประกอบ” ใช้เวลานานแค่ไหน

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

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

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

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

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