Dua contoh: pemfaktoran dan GCD

Komputer klasik yang wujud hari ini adalah sangat laju, dan kecepatannya seolah-olah sentiasa meningkat. Atas sebab ini, sesetengah orang mungkin cenderung percaya bahawa komputer begitu pantas sehingga tiada masalah pengiraan yang di luar jangkauan mereka.

Kepercayaan ini adalah salah. Sesetengah masalah pengiraan begitu kompleks secara dasarnya sehingga, walaupun terdapat algoritma untuk menyelesaikannya, tiada komputer di planet Bumi hari ini yang cukup pantas untuk menjalankan algoritma-algoritma ini hingga selesai ke atas input yang sederhana besarnya dalam masa hayat seorang manusia — malah dalam masa hayat Bumi itu sendiri.

Untuk menjelaskan lebih lanjut, mari kita perkenalkan masalah pemfaktoran integer.

Pemfaktoran integer

Input: integer $N\geq 2$
Output: pemfaktoran perdana bagi $N$

Yang dimaksudkan dengan pemfaktoran perdana bagi $N$ ialah senarai faktor perdana bagi $N$ dan kuasa-kuasa yang mesti dinaikkan untuk memperoleh $N$ melalui pendaraban. Sebagai contoh, faktor perdana bagi $12$ adalah $2$ dan $3,$ dan untuk memperoleh $12$ kita mesti mengambil hasil darab $2$ kepada kuasa $2$ dan $3$ kepada kuasa $1.$

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

Sehingga pengurutan faktor perdana, hanya ada satu pemfaktoran perdana untuk setiap integer positif $N\geq 2,$ yang merupakan fakta yang dikenali sebagai teorem asas aritmetik.

Beberapa demonstrasi kod mudah dalam Python akan berguna untuk menjelaskan lebih lanjut pemfaktoran integer dan konsep lain yang berkaitan dengan perbincangan ini. Import berikut diperlukan untuk demonstrasi-demonstrasi ini.

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

import math
from sympy.ntheory import factorint

Fungsi factorint daripada pakej matematik simbolik SymPy untuk Python menyelesaikan masalah pemfaktoran integer untuk apa jua input $N$ yang kita pilih. Sebagai contoh, kita boleh memperoleh pemfaktoran perdana untuk 12, yang secara semula jadi bersetuju dengan pemfaktoran di atas.

N = 12
print(factorint(N))

{2: 2, 3: 1}

Memfaktor nombor kecil seperti $12$ adalah mudah, tetapi apabila nombor $N$ yang hendak difaktorkan menjadi lebih besar, masalah ini menjadi lebih sukar. Sebagai contoh, menjalankan factorint pada nombor yang jauh lebih besar menyebabkan kelewatan singkat tetapi ketara pada komputer peribadi biasa.

N = 3402823669209384634633740743176823109843098343
print(factorint(N))

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

Untuk nilai $N$ yang lebih besar lagi, semuanya menjadi mustahil sulit, sekurang-kurangnya setakat yang kita tahu. Sebagai contoh, Cabaran Pemfaktoran RSA, yang dikendalikan oleh RSA Laboratories dari 1991 hingga 2007, menawarkan hadiah tunai sebanyak $100,000 untuk memfaktor nombor berikut, yang mempunyai 309 digit perpuluhan (atau 1024 bit apabila ditulis dalam perduaan). Hadiah untuk nombor ini tidak pernah dikutip dan faktor perdananya masih tidak diketahui.

RSA1024 = 135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563
print(RSA1024)

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

Kita tidak perlu bersusah payah menjalankan factorint pada RSA1024, ia tidak akan selesai dalam masa hayat kita.

Algoritma terpantas yang diketahui untuk memfaktor integer besar dikenali sebagai ayak medan nombor. Sebagai contoh penggunaan algoritma ini, nombor cabaran RSA RSA250, yang mempunyai 250 digit perpuluhan (atau 829 bit apabila ditulis dalam perduaan), telah difaktorkan menggunakan ayak medan nombor pada tahun 2020. Pengiraan itu memerlukan ribuan tahun-teras CPU, diedarkan merentas puluhan ribu mesin di seluruh dunia. Di sini kita boleh menghargai usaha ini dengan menyemak penyelesaiannya.

RSA250 = 2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937

p = 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367
q = 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711

print(RSA250 == p * q)

True

Keselamatan sistem kriptografi kunci awam RSA adalah berdasarkan kesukaran pengiraan pemfaktoran integer, dalam erti kata bahawa algoritma yang cekap untuk pemfaktoran integer akan memecahkannya.

Seterusnya mari kita pertimbangkan masalah yang berkaitan tetapi sangat berbeza, iaitu mengira pembahagi sepunya terbesar (atau GCD) bagi dua integer.

Pembahagi sepunya terbesar (GCD)

Input: integer bukan negatif $N$ dan $M,$ sekurang-kurangnya satu daripadanya adalah positif
Output: pembahagi sepunya terbesar bagi $N$ dan $M$

Pembahagi sepunya terbesar bagi dua nombor ialah integer terbesar yang membahagi kedua-duanya dengan tepat.

Masalah ini mudah diselesaikan dengan komputer — ia mempunyai kos pengiraan yang lebih kurang sama dengan mendarabkan dua nombor input bersama-sama. Fungsi gcd daripada modul Python math mengira pembahagi sepunya terbesar bagi nombor yang jauh lebih besar daripada RSA1024 dalam sekelip mata. (Sebenarnya, RSA1024 adalah GCD bagi dua nombor dalam contoh ini.)

N = 4636759690183918349682239573236686632636353319755818421393667064929987310592347460711767784882455889983961546491666129915628431549982893638464243493812487979530329460863532041588297885958272943021122033997933550246447236884738870576045537199814804920281890355275625050796526864093092006894744790739778376848205654332434378295899591539239698896074
M = 5056714874804877864225164843977749374751021379176083540426461360945653967249306494545888621353613218518084414930846655066495767441010526886803458300440345782982127522212209489410315422285463057656809702949608368597012967321172325810519806487247195259818074918082416290513738155834341957254558278151385588990304622183174568167973121179585331770773

print(math.gcd(N, M))

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

Ini mungkin kerana kita mempunyai algoritma yang sangat cekap untuk mengira GCD, yang paling terkenal ialah algoritma Euclid, yang ditemui lebih 2,000 tahun lalu.

Adakah mungkin terdapat algoritma pantas untuk pemfaktoran integer yang belum kita temui, yang membolehkan nombor besar seperti RSA1024 difaktorkan dalam sekelip mata? Jawapannya adalah ya. Walaupun kita mungkin menjangkakan bahawa algoritma pemfaktoran yang cekap semudah dan seelegan algoritma Euclid untuk mengira GCD sudah pasti ditemui sekarang, tiada yang menolak kewujudan algoritma klasik yang sangat cepat untuk pemfaktoran integer, selain daripada fakta bahawa kita gagal menemuinya setakat ini. Seseorang boleh menemuinya esok — tetapi jangan tunggu terlalu lama. Generasi ahli matematik dan saintis komputer telah mencari, dan memfaktor nombor seperti RSA1024 masih di luar kemampuan kita.