Dwa przykłady: faktoryzacja i NWD

Klasyczne komputery, które istnieją dziś, są niesamowicie szybkie, a ich prędkość zdaje się nieustannie rosnąć. Z tego powodu niektórzy mogą być skłonni sądzić, że komputery są tak szybkie, że żaden problem obliczeniowy nie jest poza ich zasięgiem.

To przekonanie jest błędne. Niektóre problemy obliczeniowe są z natury tak złożone, że choć istnieją algorytmy pozwalające je rozwiązać, żaden komputer na Ziemi nie jest dziś wystarczająco szybki, by uruchomić te algorytmy do końca nawet dla umiarkowanie dużych danych wejściowych — ani w ciągu ludzkiego życia, ani nawet w ciągu całego życia Ziemi.

Żeby wyjaśnić to dokładniej, wprowadźmy problem faktoryzacji liczb całkowitych.

Faktoryzacja liczb całkowitych

Dane wejściowe: liczba całkowita $N\geq 2$
Dane wyjściowe: rozkład na czynniki pierwsze liczby $N$

Przez rozkład na czynniki pierwsze liczby $N$ rozumiemy listę czynników pierwszych $N$ wraz z potęgami, do których należy je podnieść, aby przez mnożenie uzyskać $N$. Na przykład czynnikami pierwszymi liczby $12$ są $2$ i $3,$ a aby uzyskać $12,$ należy wziąć iloczyn $2$ do potęgi $2$ i $3$ do potęgi $1.$

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

Pomijając kolejność czynników pierwszych, każda dodatnia liczba całkowita $N\geq 2$ ma dokładnie jeden rozkład na czynniki pierwsze — fakt ten znany jest jako zasadnicze twierdzenie arytmetyki.

Kilka prostych demonstracji kodu w Pythonie przyda się do dalszego wyjaśniania faktoryzacji liczb całkowitych i innych pojęć związanych z tym omówieniem. Do tych demonstracji potrzebne są następujące importy.

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

import math
from sympy.ntheory import factorint

Funkcja factorint z pakietu SymPy do symbolicznych obliczeń matematycznych dla Pythona rozwiązuje problem faktoryzacji liczb całkowitych dla dowolnego wybranego przez nas $N$. Na przykład możemy uzyskać rozkład na czynniki pierwsze liczby 12, który naturalnie zgadza się z powyższą faktoryzacją.

N = 12
print(factorint(N))

{2: 2, 3: 1}

Faktoryzacja małych liczb, takich jak $12,$ jest łatwa, ale gdy faktoryzowana liczba $N$ rośnie, problem staje się trudniejszy. Na przykład uruchomienie factorint na znacznie większej liczbie powoduje krótkie, ale zauważalne opóźnienie na typowym komputerze osobistym.

N = 3402823669209384634633740743176823109843098343
print(factorint(N))

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

Dla jeszcze większych wartości $N$ sprawy stają się niemożliwie trudne — przynajmniej o ile nam wiadomo. Na przykład RSA Factoring Challenge, prowadzone przez RSA Laboratories w latach 1991–2007, oferowało nagrodę pieniężną w wysokości 100 000 dolarów za sfaktoryzowanie poniższej liczby, która ma 309 cyfr dziesiętnych (czyli 1024 bity w zapisie binarnym). Nagroda za tę liczbę nigdy nie została odebrana, a jej czynniki pierwsze pozostają nieznane.

RSA1024 = 135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563
print(RSA1024)

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

Nie ma sensu uruchamiać factorint na RSA1024 — nie skończyłoby się to za naszego życia.

Najszybszy znany algorytm faktoryzacji dużych liczb całkowitych nosi nazwę sita ciał liczbowych. Jako przykład zastosowania tego algorytmu: liczba wyzwania RSA250, mająca 250 cyfr dziesiętnych (czyli 829 bitów w zapisie binarnym), została sfaktoryzowana przy użyciu sita ciał liczbowych w 2020 roku. Obliczenia wymagały tysięcy lat rdzeniowych CPU, rozłożonych na dziesiątki tysięcy maszyn na całym świecie. Tutaj możemy docenić ten wysiłek, weryfikując rozwiązanie.

RSA250 = 2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937

p = 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367
q = 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711

print(RSA250 == p * q)

True

Bezpieczeństwo kryptosystemu klucza publicznego RSA opiera się na obliczeniowej trudności faktoryzacji liczb całkowitych, w tym sensie że efektywny algorytm faktoryzacji liczb całkowitych złamałby go.

Teraz rozważmy pokrewny, ale zupełnie inny problem — obliczanie największego wspólnego dzielnika (NWD, ang. GCD) dwóch liczb całkowitych.

Największy wspólny dzielnik (NWD)

Dane wejściowe: nieujemne liczby całkowite $N$ i $M,$ z których co najmniej jedna jest dodatnia
Dane wyjściowe: największy wspólny dzielnik $N$ i $M$

Największy wspólny dzielnik dwóch liczb to największa liczba całkowita, która dzieli je obie bez reszty.

Ten problem jest łatwy do rozwiązania za pomocą komputera — jego koszt obliczeniowy jest w przybliżeniu taki sam jak mnożenie dwóch liczb wejściowych. Funkcja gcd z modułu math Pythona oblicza największy wspólny dzielnik liczb znacznie większych niż RSA1024 w mgnieniu oka. (W rzeczywistości RSA1024 jest NWD dwóch liczb w tym przykładzie.)

N = 4636759690183918349682239573236686632636353319755818421393667064929987310592347460711767784882455889983961546491666129915628431549982893638464243493812487979530329460863532041588297885958272943021122033997933550246447236884738870576045537199814804920281890355275625050796526864093092006894744790739778376848205654332434378295899591539239698896074
M = 5056714874804877864225164843977749374751021379176083540426461360945653967249306494545888621353613218518084414930846655066495767441010526886803458300440345782982127522212209489410315422285463057656809702949608368597012967321172325810519806487247195259818074918082416290513738155834341957254558278151385588990304622183174568167973121179585331770773

print(math.gcd(N, M))

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

Jest to możliwe, ponieważ dysponujemy bardzo wydajnymi algorytmami obliczania NWD, z których najbardziej znany jest algorytm Euclida, odkryty ponad 2000 lat temu.

Czy mógłby istnieć szybki algorytm faktoryzacji liczb całkowitych, którego po prostu jeszcze nie odkryliśmy, pozwalający na sfaktoryzowanie dużych liczb, takich jak RSA1024, w mgnieniu oka? Odpowiedź brzmi: tak. Choć mogłoby się wydawać, że wydajny algorytm faktoryzacji, tak prosty i elegancki jak algorytm Euclida do obliczania NWD, zostałby już odkryty, nic nie wyklucza istnienia bardzo szybkiego klasycznego algorytmu faktoryzacji liczb całkowitych — poza tym, że dotychczas go nie znaleźliśmy. Ktoś mógłby go odkryć jutro — ale nie wstrzymuj oddechu. Pokolenia matematyków i informatyków szukały, a faktoryzacja liczb takich jak RSA1024 pozostaje poza naszym zasięgiem.