สองตัวอย่าง: การแยกตัวประกอบและ GCD

คอมพิวเตอร์คลาสสิกในปัจจุบันทำงานได้เร็วมาก และดูเหมือนความเร็วจะเพิ่มขึ้นเรื่อยๆ ด้วยเหตุนี้ บางคนอาจคิดว่าคอมพิวเตอร์เร็วพอที่จะแก้ปัญหาการคำนวณได้ทุกอย่าง

แต่ความเชื่อนั้นผิด ปัญหาการคำนวณบางอย่างซับซ้อนโดยธรรมชาติจนแม้จะมีอัลกอริทึมสำหรับแก้ปัญหาเหล่านั้น คอมพิวเตอร์บนโลกทุกวันนี้ก็ไม่มีตัวไหนเร็วพอที่จะรันอัลกอริทึมเหล่านั้นจนจบได้ภายในช่วงชีวิตของมนุษย์คนหนึ่ง หรือแม้แต่ภายในช่วงอายุของโลกด้วยซ้ำ

เพื่ออธิบายเพิ่มเติม ขอแนะนำปัญหา การแยกตัวประกอบจำนวนเต็ม

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

อินพุต: จำนวนเต็ม $N\geq 2$
เอาต์พุต: การแยกตัวประกอบเฉพาะของ $N$

การแยกตัวประกอบเฉพาะ ของ $N$ หมายถึงรายการของตัวประกอบเฉพาะของ $N$ และกำลังที่ต้องยกเพื่อให้ได้ $N$ เมื่อคูณกัน ตัวอย่างเช่น ตัวประกอบเฉพาะของ $12$ คือ $2$ และ $3$ และเพื่อให้ได้ $12$ เราต้องคูณ $2$ ยกกำลัง $2$ กับ $3$ ยกกำลัง $1$

$$12 = 2^2 \cdot 3$$

ไม่ว่าจะเรียงลำดับตัวประกอบเฉพาะอย่างไร มีการแยกตัวประกอบเฉพาะเพียงหนึ่งแบบสำหรับจำนวนเต็มบวก $N\geq 2$ แต่ละตัว ซึ่งเป็นข้อเท็จจริงที่รู้จักกันในชื่อ ทฤษฎีบทพื้นฐานของเลขคณิต

การสาธิตโค้ด Python ง่ายๆ สักสองสามอย่างจะช่วยอธิบายการแยกตัวประกอบจำนวนเต็มและแนวคิดที่เกี่ยวข้องได้ดีขึ้น โดยต้องมีการ import ดังนี้ก่อน

# Added by doQumentation — required packages for this notebook
!pip install -q sympy

import math
from sympy.ntheory import factorint

ฟังก์ชัน factorint จากแพ็คเกจคณิตศาสตร์เชิงสัญลักษณ์ SymPy ของ Python แก้ปัญหาการแยกตัวประกอบจำนวนเต็มสำหรับค่า $N$ ที่เราต้องการ ตัวอย่างเช่น เราสามารถหาการแยกตัวประกอบเฉพาะของ 12 ซึ่งได้ผลตรงกับที่แยกไว้ข้างต้น

N = 12
print(factorint(N))

{2: 2, 3: 1}

การแยกตัวประกอบตัวเลขเล็กๆ อย่าง $12$ นั้นง่ายมาก แต่เมื่อตัวเลข $N$ ที่ต้องการแยกตัวประกอบมีขนาดใหญ่ขึ้น ปัญหาก็ยากขึ้นตามไปด้วย ตัวอย่างเช่น การรัน factorint บนตัวเลขที่ใหญ่กว่ามากจะทำให้เห็นความล่าช้าเล็กน้อยแต่สังเกตได้บนคอมพิวเตอร์ส่วนตัวทั่วไป

N = 3402823669209384634633740743176823109843098343
print(factorint(N))

{3: 2, 74519450661011221: 1, 5073729280707932631243580787: 1}

สำหรับค่า $N$ ที่ใหญ่ยิ่งกว่านั้น สิ่งต่างๆ กลายเป็นเรื่องที่เป็นไปไม่ได้เลย อย่างน้อยก็เท่าที่เรารู้ ตัวอย่างเช่น RSA Factoring Challenge ซึ่ง RSA Laboratories จัดขึ้นระหว่างปี 1991 ถึง 2007 ได้เสนอรางวัลเงินสด $100,000 สำหรับการแยกตัวประกอบของตัวเลขต่อไปนี้ ซึ่งมี 309 หลักทศนิยม (หรือ 1024 บิตเมื่อเขียนในรูปเลขฐานสอง) รางวัลสำหรับตัวเลขนี้ไม่เคยถูกรับและตัวประกอบเฉพาะของมันยังคงไม่เป็นที่รู้จัก

RSA1024 = 135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563
print(RSA1024)

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

ไม่ต้องเสียเวลารัน factorint กับ RSA1024 หรอก เพราะมันจะไม่เสร็จภายในช่วงชีวิตของเรา

อัลกอริทึมที่เร็วที่สุดที่รู้จักสำหรับการแยกตัวประกอบจำนวนเต็มขนาดใหญ่เรียกว่า number field sieve ตัวอย่างการใช้งานอัลกอริทึมนี้ ตัวเลข RSA challenge ชื่อ RSA250 ซึ่งมี 250 หลักทศนิยม (หรือ 829 บิตในรูปเลขฐานสอง) ถูกแยกตัวประกอบด้วย number field sieve ในปี 2020 การคำนวณนั้นต้องใช้เวลา CPU core-years หลายพันปี กระจายอยู่บนเครื่องหลายหมื่นเครื่องทั่วโลก เราสามารถชื่นชมความพยายามนั้นได้โดยตรวจสอบผลลัพธ์

RSA250 = 2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937

p = 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367
q = 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711

print(RSA250 == p * q)

True

ความปลอดภัยของระบบเข้ารหัสกุญแจสาธารณะ RSA ขึ้นอยู่กับความยากทางการคำนวณของการแยกตัวประกอบจำนวนเต็ม ในแง่ที่ว่าอัลกอริทึมที่มีประสิทธิภาพสำหรับการแยกตัวประกอบจำนวนเต็มจะทำลายระบบนั้นได้

ต่อไปมาพิจารณาปัญหาที่เกี่ยวข้องแต่แตกต่างออกไปมาก นั่นคือการหาตัวหารร่วมมาก (greatest common divisor หรือ GCD) ของจำนวนเต็มสองตัว

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

อินพุต: จำนวนเต็มไม่เป็นลบ $N$ และ $M$ โดยอย่างน้อยหนึ่งในนั้นต้องเป็นบวก
เอาต์พุต: ตัวหารร่วมมากของ $N$ และ $M$

ตัวหารร่วมมากของตัวเลขสองตัวคือจำนวนเต็มที่มากที่สุดที่หารทั้งสองตัวได้ลงตัว

ปัญหานี้แก้ได้ง่ายด้วยคอมพิวเตอร์ โดยมีต้นทุนการคำนวณประมาณเท่ากับการคูณตัวเลขสองตัวเข้าด้วยกัน ฟังก์ชัน gcd จากโมดูล math ของ Python คำนวณ GCD ของตัวเลขที่ใหญ่กว่า RSA1024 มากได้ในพริบตา (ที่จริงแล้ว RSA1024 คือ GCD ของตัวเลขสองตัวในตัวอย่างนี้)

N = 4636759690183918349682239573236686632636353319755818421393667064929987310592347460711767784882455889983961546491666129915628431549982893638464243493812487979530329460863532041588297885958272943021122033997933550246447236884738870576045537199814804920281890355275625050796526864093092006894744790739778376848205654332434378295899591539239698896074
M = 5056714874804877864225164843977749374751021379176083540426461360945653967249306494545888621353613218518084414930846655066495767441010526886803458300440345782982127522212209489410315422285463057656809702949608368597012967321172325810519806487247195259818074918082416290513738155834341957254558278151385588990304622183174568167973121179585331770773

print(math.gcd(N, M))

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

สิ่งนี้เป็นไปได้เพราะเรามีอัลกอริทึมที่มีประสิทธิภาพสูงสำหรับการหา GCD โดยที่รู้จักกันดีที่สุดคือ อัลกอริทึมของออยเลอร์ (Euclid's algorithm) ที่ค้นพบมาเมื่อกว่า 2,000 ปีก่อน

อาจจะมีอัลกอริทึมที่เร็วสำหรับการแยกตัวประกอบจำนวนเต็มที่เรายังไม่ค้นพบ ซึ่งอนุญาตให้แยกตัวประกอบตัวเลขขนาดใหญ่อย่าง RSA1024 ได้ในพริบตาหรือเปล่า? คำตอบคือใช่ แม้เราอาจคาดว่าอัลกอริทึมที่มีประสิทธิภาพสำหรับการแยกตัวประกอบที่เรียบง่ายและสวยงามเหมือนอัลกอริทึมของออยเลอร์สำหรับการหา GCD น่าจะถูกค้นพบไปนานแล้ว แต่ไม่มีอะไรที่ตัดความเป็นไปได้ของอัลกอริทึมคลาสสิกที่เร็วมากสำหรับการแยกตัวประกอบจำนวนเต็มออกไป นอกจากความจริงที่ว่าเราล้มเหลวในการค้นหามันจนถึงตอนนี้ อาจถูกค้นพบพรุ่งนี้ก็ได้ แต่อย่าเพิ่งรอ นักคณิตศาสตร์และนักวิทยาศาสตร์คอมพิวเตอร์หลายรุ่นได้ค้นหา และการแยกตัวประกอบตัวเลขอย่าง RSA1024 ยังคงอยู่เกินความสามารถของเรา