Dva příklady: faktorizace a NSD

Klasické počítače, které dnes existují, jsou neuvěřitelně rychlé a jejich rychlost se zdá stále rostoucí. Z tohoto důvodu by někdo mohl být nakloněn věřit, že počítače jsou tak rychlé, že žádný výpočetní problém není mimo jejich dosah.

Tato víra je mylná. Některé výpočetní problémy jsou tak ze své podstaty složité, že ačkoli existují algoritmy k jejich řešení, žádný počítač na planetě Zemi dnes není dostatečně rychlý, aby tyto algoritmy dokončil ani na středně velkých vstupech během lidského života — nebo dokonce během existence samotné Země.

Abychom to vysvětlili podrobněji, představíme problém faktorizace celých čísel.

Integer factorization

Vstup: celé číslo $N\geq 2$
Výstup: prvočíselný rozklad čísla $N$

Prvočíselným rozkladem čísla $N$ myslíme seznam prvočíselných dělitelů $N$ a mocnin, na které musí být umocněny, aby jejich součinem vzniklo $N$. Například prvočíselní dělitelé čísla $12$ jsou $2$ a $3,$ a abychom získali $12,$ musíme vzít součin $2$ na druhou mocninu a $3$ na první mocninu.

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

Až na pořadí prvočíselných dělitelů existuje pro každé kladné celé číslo $N\geq 2$ pouze jeden prvočíselný rozklad, což je fakt známý jako základní věta aritmetiky.

Několik jednoduchých ukázek kódu v Pythonu bude užitečných pro další vysvětlení faktorizace celých čísel a dalších konceptů, které se vztahují k této diskuzi. Pro tyto ukázky jsou zapotřebí následující importy.

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

import math
from sympy.ntheory import factorint

Funkce factorint z balíčku symbolické matematiky SymPy pro Python řeší problém faktorizace celých čísel pro jakýkoli vstup $N$, který zvolíme. Například můžeme získat prvočíselný rozklad čísla 12, který přirozeně odpovídá výše uvedenému rozkladu.

N = 12
print(factorint(N))

{2: 2, 3: 1}

Faktorizace malých čísel jako $12$ je snadná, ale když se číslo $N$ k faktorizaci zvětšuje, problém se stává obtížnějším. Například spuštění factorint na výrazně větším čísle způsobí na typickém osobním počítači krátké, ale znatelné zpoždění.

N = 3402823669209384634633740743176823109843098343
print(factorint(N))

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

Pro ještě větší hodnoty $N$ se věci stávají nemožně obtížnými, alespoň pokud víme. Například RSA Factoring Challenge, kterou provozovaly RSA Laboratories od roku 1991 do roku 2007, nabízela odměnu 100 000 dolarů za faktorizaci následujícího čísla, které má 309 desetinných číslic (neboli 1024 bitů v binárním zápisu). Odměna za toto číslo nebyla nikdy vybrána a jeho prvočíselní dělitelé zůstávají neznámí.

RSA1024 = 135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563
print(RSA1024)

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

Nemá smysl spouštět factorint na RSA1024, nedokončilo by se to za naše životy.

Nejrychlejší známý algoritmus pro faktorizaci velkých celých čísel je známý jako síto číselného tělesa (number field sieve). Jako příklad použití tohoto algoritmu bylo číslo RSA250 z RSA challenge, které má 250 desetinných číslic (neboli 829 bitů v binárním zápisu), faktorizováno pomocí síta číselného tělesa v roce 2020. Výpočet vyžadoval tisíce CPU-jádro-roků, distribuovaných mezi desítky tisíc strojů po celém světě. Zde si můžeme vážit tohoto úsilí kontrolou řešení.

RSA250 = 2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937

p = 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367
q = 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711

print(RSA250 == p * q)

True

Bezpečnost kryptosystému RSA s veřejným klíčem je založena na výpočetní obtížnosti faktorizace celých čísel, v tom smyslu, že efektivní algoritmus pro faktorizaci celých čísel by jej prolomil.

Nyní se podívejme na související, ale velmi odlišný problém, kterým je výpočet největšího společného dělitele (NSD) dvou celých čísel.

Greatest common divisor (GCD)

Vstup: nezáporná celá čísla $N$ a $M,$ z nichž alespoň jedno je kladné
Výstup: největší společný dělitel čísel $N$ a $M$

Největší společný dělitel dvou čísel je největší celé číslo, které beze zbytku dělí obě z nich.

Tento problém je snadné vyřešit pomocí počítače — má přibližně stejnou výpočetní náročnost jako vynásobení obou vstupních čísel. Funkce gcd z modulu Python math vypočítá největšího společného dělitele čísel, která jsou podstatně větší než RSA1024, v mžiku oka. (Ve skutečnosti je RSA1024 NSD dvou čísel v tomto příkladu.)

N = 4636759690183918349682239573236686632636353319755818421393667064929987310592347460711767784882455889983961546491666129915628431549982893638464243493812487979530329460863532041588297885958272943021122033997933550246447236884738870576045537199814804920281890355275625050796526864093092006894744790739778376848205654332434378295899591539239698896074
M = 5056714874804877864225164843977749374751021379176083540426461360945653967249306494545888621353613218518084414930846655066495767441010526886803458300440345782982127522212209489410315422285463057656809702949608368597012967321172325810519806487247195259818074918082416290513738155834341957254558278151385588990304622183174568167973121179585331770773

print(math.gcd(N, M))

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

To je možné, protože máme velmi efektivní algoritmy pro výpočet NSD, z nichž nejznámější je Euklidův algoritmus, objevený před více než 2 000 lety.

Mohl by existovat rychlý algoritmus pro faktorizaci celých čísel, který jsme prostě ještě neobjevili, umožňující faktorizovat velká čísla jako RSA1024 v mžiku oka? Odpověď zní ano. Ačkoli bychom mohli očekávat, že efektivní algoritmus pro faktorizaci tak jednoduchý a elegantní jako Euklidův algoritmus pro výpočet NSD by už byl objeven, nic nevylučuje existenci velmi rychlého klasického algoritmu pro faktorizaci celých čísel, kromě toho, že se nám ho dosud nepodařilo najít. Mohl by být objeven zítra — ale nezadržuj dech. Generace matematiků a informatiků hledaly a faktorizace čísel jako RSA1024 zůstává mimo náš dosah.