Dalawang halimbawa: factoring at GCDs

Ang mga klasikal na computer ngayon ay napakabilis, at patuloy na tumataas ang kanilang bilis. Dahil dito, may mga taong naniniwala na kaya ng mga computer na lutasin ang kahit anong computational problem.

Maling-mali ang paniniwala na iyon. May mga computational problem na lubhang kumplikado — kahit may mga algorithm para lutasin sila, wala ni isang computer sa buong mundo ngayon ang mabilis na sapat para tapusin ang mga algorithm na ito kahit sa katamtamang laking input sa loob ng isang buhay ng tao — o maging sa loob ng buhay ng Mundo mismo.

Para mas maipaliwanag ito, ipakilala natin ang problema ng integer factorization.

Integer factorization

Input: isang integer na $N\geq 2$
Output: ang prime factorization ng $N$

Ang prime factorization ng $N$ ay ang listahan ng mga prime factor ng $N$ at ang mga kapangyarihang kailangang itaas sa kanila para makuha ang $N$ sa pamamagitan ng multiplikasyon. Halimbawa, ang mga prime factor ng $12$ ay $2$ at $3,$ at para makuha ang $12$ kailangan nating kunin ang produkto ng $2$ sa kapangyarihang $2$ at $3$ sa kapangyarihang $1.$

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

Hangga't iisa ang ayos ng mga prime factor, may iisang prime factorization lamang para sa bawat positibong integer na $N\geq 2,$ na isang katotohanan na kilala bilang fundamental theorem of arithmetic.

Ilang simpleng code demonstration sa Python ang makakatulong para mas maipaliwanag ang integer factorization at iba pang konsepto na may kaugnayan sa talakayan na ito. Ang mga sumusunod na import ay kailangan para sa mga demonstration na ito.

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

import math
from sympy.ntheory import factorint

Ang factorint function mula sa SymPy symbolic mathematics package para sa Python ay naglulutas ng integer factorization problem para sa kahit anong input na $N$ na pipiliin natin. Halimbawa, makukuha natin ang prime factorization ng 12, na natural na naaayon sa factorization sa itaas.

N = 12
print(factorint(N))

{2: 2, 3: 1}

Madaling i-factor ang maliliit na numero tulad ng $12$, ngunit kapag lumaki ang numero na $N$ na ia-factor, nagiging mas mahirap ang problema. Halimbawa, ang pagpapatakbo ng factorint sa mas malaking numero ay nagdudulot ng maikling ngunit kapansin-pansing pagkaantala sa isang karaniwang personal na computer.

N = 3402823669209384634633740743176823109843098343
print(factorint(N))

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

Para sa mas malalaking value ng $N,$ nagiging imposible ang mga bagay, kahit paano sa aming kaalaman. Halimbawa, ang RSA Factoring Challenge, na pinamahalaan ng RSA Laboratories mula 1991 hanggang 2007, nag-alok ng cash prize na $100,000 para i-factor ang sumusunod na numero, na may 309 decimal digit (o 1024 bit kapag nakasulat sa binary). Ang prize para sa numerong ito ay hindi kailanman natanggap at ang mga prime factor nito ay nananatiling hindi kilala.

RSA1024 = 135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563
print(RSA1024)

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

Hindi na natin kailangang subukang patakbuhin ang factorint sa RSA1024 — hindi ito matatapos sa loob ng ating buhay.

Ang pinakamabilis na kilalang algorithm para sa pag-factor ng malalaking integer ay kilala bilang ang number field sieve. Bilang halimbawa ng paggamit ng algorithm na ito, ang RSA challenge number na RSA250, na may 250 decimal digit (o 829 bit kapag nakasulat sa binary), ay na-factor gamit ang number field sieve noong 2020. Ang computation ay nangangailangan ng libu-libong CPU core-years, na ipinamamahagi sa dose-dosenang libong makina sa buong mundo. Dito natin mapahahalagahan ang pagsisikap na ito sa pamamagitan ng pag-check ng solusyon.

RSA250 = 2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937

p = 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367
q = 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711

print(RSA250 == p * q)

True

Ang seguridad ng RSA public-key cryptosystem ay nakabatay sa computational difficulty ng integer factoring, sa kahulugang ang isang mahusay na algorithm para sa integer factoring ay sisira dito.

Susunod, tingnan natin ang isang kaugnay ngunit napaka-ibang problema, na ang pagkompute ng greatest common divisor (o GCD) ng dalawang integer.

Greatest common divisor (GCD)

Input: mga nonnegative integer na $N$ at $M,$ at least isa sa kanila ay positibo
Output: ang greatest common divisor ng $N$ at $M$

Ang greatest common divisor ng dalawang numero ay ang pinakamalaking integer na pantay na hinahati ang kapwa.

Madaling lutasin ang problemang ito gamit ang computer — halos kapareho ang computational cost nito sa pagmamultiplika ng dalawang input number. Ang gcd function mula sa Python math module ay nagkokompute ng greatest common divisor ng mga numero na mas malaki pa kaysa sa RSA1024 sa isang kisap-mata. (Sa katunayan, ang RSA1024 ang GCD ng dalawang numero sa halimbawang ito.)

N = 4636759690183918349682239573236686632636353319755818421393667064929987310592347460711767784882455889983961546491666129915628431549982893638464243493812487979530329460863532041588297885958272943021122033997933550246447236884738870576045537199814804920281890355275625050796526864093092006894744790739778376848205654332434378295899591539239698896074
M = 5056714874804877864225164843977749374751021379176083540426461360945653967249306494545888621353613218518084414930846655066495767441010526886803458300440345782982127522212209489410315422285463057656809702949608368597012967321172325810519806487247195259818074918082416290513738155834341957254558278151385588990304622183174568167973121179585331770773

print(math.gcd(N, M))

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

Posible ito dahil mayroon tayong napaka-episyenteng mga algorithm para sa pagkompute ng GCDs, ang pinaka-kilala sa kanila ay ang Euclid's algorithm, na natuklasan mahigit 2,000 taon na ang nakaraan.

Maaari bang mayroon pang mabilis na algorithm para sa integer factorization na hindi pa natin natutuklasan, na nagbibigay-daan sa malalaking numero tulad ng RSA1024 na ma-factor sa isang kisap-mata? Ang sagot ay oo. Kahit inaasahan nating ang isang mahusay na algorithm para sa factoring na kasing simple at elegante ng Euclid's algorithm para sa pagkompute ng GCDs ay natuklasan na sana nito, wala namang nagpapawalang-bisa sa pag-iral ng isang napakabilis na klasikal na algorithm para sa integer factorization, bukod na lang sa katotohanan na hindi pa natin ito natagpuan hanggang ngayon. Maaaring matuklasan ito bukas — ngunit huwag mong inaasahan. Maraming henerasyong matematisyan at computer scientist ang naghanap, at ang pag-factor ng mga numero tulad ng RSA1024 ay nananatiling lampas sa ating kakayahan.