Dua contoh: faktorisasi dan GCD

Komputer klasik yang ada saat ini sangat cepat, dan kecepatannya tampaknya terus meningkat. Karena alasan ini, beberapa orang mungkin cenderung percaya bahwa komputer begitu cepat sehingga tidak ada masalah komputasi yang berada di luar jangkauannya.

Kepercayaan itu salah. Beberapa masalah komputasi sangat rumit secara inheren sehingga, meskipun ada algoritma untuk menyelesaikannya, tidak ada komputer di planet Bumi saat ini yang cukup cepat untuk menjalankan algoritma-algoritma ini hingga selesai bahkan pada input berukuran sedang dalam seumur hidup manusia — atau bahkan dalam seumur hidup Bumi itu sendiri.

Untuk menjelaskan lebih lanjut, mari perkenalkan masalah faktorisasi bilangan bulat.

Integer factorization

Input: sebuah bilangan bulat $N\geq 2$
Output: faktorisasi prima dari $N$

Dengan faktorisasi prima dari $N$ yang kita maksudkan adalah daftar faktor prima dari $N$ beserta pangkat masing-masing faktor tersebut agar hasil kalinya sama dengan $N$. Misalnya, faktor prima dari $12$ adalah $2$ dan $3$, dan untuk mendapatkan $12$ kita harus mengambil hasil kali $2$ pangkat $2$ dan $3$ pangkat $1$.

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

Tanpa memperhatikan urutan faktor primanya, hanya ada satu faktorisasi prima untuk setiap bilangan bulat positif $N\geq 2$, yang merupakan fakta yang dikenal sebagai teorema dasar aritmatika.

Beberapa demonstrasi kode sederhana dalam Python akan sangat membantu untuk menjelaskan lebih lanjut faktorisasi bilangan bulat dan konsep-konsep lain yang berkaitan dengan diskusi ini. Impor berikut diperlukan untuk demonstrasi-demonstrasi ini.

# Added by doQumentation — installs the packages this notebook needs if they are missing
import importlib.util

_needed = {"sympy": "sympy"}
_missing = [pip for module, pip in _needed.items()
            if importlib.util.find_spec(module) is None]
# One at a time, so a package that fails to install does not block the others
for _pip in _missing:
    %pip install -q {_pip}
if not _missing:
    print("\u2713 All required packages are installed")

import math
from sympy.ntheory import factorint

Fungsi factorint dari paket matematika simbolis SymPy untuk Python menyelesaikan masalah faktorisasi bilangan bulat untuk input $N$ apa pun yang kita pilih. Misalnya, kita bisa mendapatkan faktorisasi prima untuk 12, yang tentu saja sesuai dengan faktorisasi di atas.

N = 12
print(factorint(N))

{2: 2, 3: 1}

Memfaktorkan angka kecil seperti $12$ mudah, tapi ketika angka $N$ yang akan difaktorkan semakin besar, masalahnya menjadi lebih sulit. Misalnya, menjalankan factorint pada angka yang jauh lebih besar menyebabkan keterlambatan singkat tapi nyata pada komputer pribadi biasa.

N = 3402823669209384634633740743176823109843098343
print(factorint(N))

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

Untuk nilai $N$ yang bahkan lebih besar, hal-hal menjadi mustahil dilakukan, setidaknya sejauh yang kita tahu. Misalnya, RSA Factoring Challenge, yang dijalankan oleh RSA Laboratories dari 1991 hingga 2007, menawarkan hadiah uang tunai sebesar $100.000 untuk memfaktorkan angka berikut, yang memiliki 309 digit desimal (atau 1024 bit ketika ditulis dalam biner). Hadiah untuk angka ini tidak pernah diklaim dan faktor primanya tetap tidak diketahui.

RSA1024 = 135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563
print(RSA1024)

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

Kita tidak perlu repot menjalankan factorint pada RSA1024, itu tidak akan selesai dalam seumur hidup kita.

Algoritma tercepat yang diketahui untuk memfaktorkan bilangan bulat besar dikenal sebagai number field sieve. Sebagai contoh penggunaan algoritma ini, angka tantangan RSA250, yang memiliki 250 digit desimal (atau 829 bit ketika ditulis dalam biner), difaktorkan menggunakan number field sieve pada tahun 2020. Komputasi tersebut membutuhkan ribuan CPU core-years, didistribusikan di puluhan ribu mesin di seluruh dunia. Di sini kita bisa menghargai upaya ini dengan memeriksa solusinya.

RSA250 = 2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937

p = 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367
q = 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711

print(RSA250 == p * q)

True

Keamanan sistem kriptografi kunci publik RSA didasarkan pada kesulitan komputasi faktorisasi bilangan bulat, dalam arti bahwa algoritma yang efisien untuk faktorisasi bilangan bulat akan membobolnya.

Selanjutnya mari kita pertimbangkan masalah yang terkait tapi sangat berbeda, yaitu menghitung pembagi persekutuan terbesar (atau GCD) dari dua bilangan bulat.

Pembagi persekutuan terbesar (GCD)

Input: bilangan bulat tak-negatif $N$ dan $M$, setidaknya salah satunya positif
Output: pembagi persekutuan terbesar dari $N$ dan $M$

Pembagi persekutuan terbesar dari dua bilangan adalah bilangan bulat terbesar yang habis membagi keduanya.

Masalah ini mudah diselesaikan dengan komputer — biayanya kira-kira sama dengan mengalikan dua bilangan input bersama-sama. Fungsi gcd dari modul Python math menghitung pembagi persekutuan terbesar dari angka-angka yang jauh lebih besar dari RSA1024 dalam sekejap mata. (Faktanya, RSA1024 adalah GCD dari dua angka dalam contoh ini.)

N = 4636759690183918349682239573236686632636353319755818421393667064929987310592347460711767784882455889983961546491666129915628431549982893638464243493812487979530329460863532041588297885958272943021122033997933550246447236884738870576045537199814804920281890355275625050796526864093092006894744790739778376848205654332434378295899591539239698896074
M = 5056714874804877864225164843977749374751021379176083540426461360945653967249306494545888621353613218518084414930846655066495767441010526886803458300440345782982127522212209489410315422285463057656809702949608368597012967321172325810519806487247195259818074918082416290513738155834341957254558278151385588990304622183174568167973121179585331770773

print(math.gcd(N, M))

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

Ini dimungkinkan karena kita memiliki algoritma yang sangat efisien untuk menghitung GCD, yang paling terkenal adalah algoritma Euclid, yang ditemukan lebih dari 2.000 tahun yang lalu.

Bisakah ada algoritma cepat untuk faktorisasi bilangan bulat yang belum kita temukan, memungkinkan angka besar seperti RSA1024 difaktorkan dalam sekejap mata? Jawabannya adalah ya. Meskipun kita mungkin mengharapkan bahwa algoritma efisien untuk faktorisasi sesederhana dan seanggun algoritma Euclid untuk menghitung GCD sudah ditemukan pada saat ini, tidak ada yang menghalangi keberadaan algoritma klasik yang sangat cepat untuk faktorisasi bilangan bulat, selain fakta bahwa kita gagal menemukannya sejauh ini. Algoritma seperti itu bisa saja ditemukan besok — tapi jangan terlalu berharap. Generasi matematikawan dan ilmuwan komputer telah mencari, dan memfaktorkan angka seperti RSA1024 tetap di luar jangkauan kita.