Faktorizace je procesem, při kterém se snažíme rozložit určité zadané číslo na dvě prvočísla. Jedná se o úlohu, jež lze řešit pouze hrubou silou, tj. výčtem možností. V zásadě prostě zkoušíme dělit stále většími a většími čísly tak dlouho, až se trefíme. Faktorizace přitom není nějakou samoúčelnou matematickou hříčkou, nýbrž technologií, která se prakticky využívá v současné kryptografii. Vynásobit dvě prvočísla mezi sebou je i v případě značně velkých čísel (a konec konců, i díky internetovým distribuovaným projektům se daří objevovat stále větší a větší prvočísla) poměrně snadné, naopak provést v reálném čase rozklad je mnohdy už mimo možnosti současné výpočetní techniky. Právě na této asymetrii mezi zašifrováním a dešifrováním stojí část současné kryptografie (oboru, kterým se autor tohoto článku nijak speciálně nezabývá – omlouvám se, pokud jsem se v tomto odstavci dopustil nějaké nepřesnosti).
Výpočetně náročné úlohy typu faktorizace jsou, především ve vazbě na lámání šifer, také příčinou, proč se vůbec uvažuje o dosti problematické konstrukci nových zařízení, jako jsou kvantové či DNA počítače. Kvantové počítače disponují pro tyto účely zcela odlišnou logikou (více stavů v jednom okamžiku), která jim umožňuje snižovat úroveň složitosti exponenciálně rostoucích problémů. (Mimochodem: zajímavou otázkou je, co se vlastně s nepolynomiálním problémem na kvantovém počítači stane – stane se z něj polynomiální, nebo celý výraz pouze „spadne pod odmocninu“? V tomto ohledu si můžete přečíst celou řadu navzájem si protiřečících informací. Nicméně otázku řešení teorie kolem NP problémů opět přenechávám povolanějším.)
DNA počítač nenabízí žádná kouzla tohoto typu, různé „principy superpozice“ apod. a stále pracuje podle zákonů klasické fyziky. Není pravda (i když i to se lze občas dočíst) že by jeho použití nějak souviselo v třídou výpočetní obtížnosti problému, nicméně disponuje obrovským paralelismem. V obyčejné zkumavce dokážete současně zrealizovat obrovské množství reakcí – jde prostě o jakýsi paralelní superpočítač.
Princip DNA počítačů byl původně v polovině 90. let předveden na řešení „úlohy obchodního cestujícího“. V tomto článku se pokusíme realizovat faktorizaci. Půjde přitom o pouhý myšlenkový experiment, autor neprovedl žádné laboratorní pokusy – a ani je prozatím neplánuje :-).
Základní princip DNA počítačů spočívá v párování vláken – jde tedy o totéž, co činí z deoxyribonukleové kyseliny i nositelku dědičnosti v živých organismech. Tzv. komplementarita bází znamená, že komplementární, zrcadlové řetězce DNA vydrží vedle sebe (viz populární dvojšroubovice). Díky jednoznačnosti přepisu bází lze dosáhnout i přenosu informace. S DNA přitom v rámci „počítače“ manipulujeme tak, že molekuly různě mícháme a oddělujeme od sebe především na základě různých fyzikálních vlastností. Pokud je např. pokus modelován tak, že správné řešení bude odpovídat spárování řetězců, dvojvláknovou molekulu – naše řešení – oddělíme ze směsi např. na základě toho, že je těžší než molekuly jednovláknové.
V každém „dvojvláknu“ musí proti sobě stát buď adenin a thymin, nebo guanin a cytosin. Všechny tyto dusíkaté báze označujeme jednopísmennými zkratkami. Komplementární řetězce pak mohou vypadat např. takto:
---A-C-G-A-T-T--- ---T-G-C-T-A-A---
Zájemce o podrobnější výklad lze odkázat na článek Biochemické základy DNA počítačů.
Řešení problému obchodního cestujícího, na němž byl princip DNA počítačů v polovině 90. let poprvé demonstrován, je popsáno např. opět na Science Worldu.
Pozor: DNA počítač je zatím v zásadě jednoúčelový, tj. nestačí nám vyřešit problém vývojovým diagramem, ale potřebujeme vždy vymyslet i konkrétní chemickou implementaci. Jaký bude algoritmus pro faktorizaci?
Obrovské číslo, jehož faktorizaci provádíme, si znázorníme jedním řetězcem DNA složeným ze stejných nukleotidů. Řekněme, že půjde o veledlouhý sled adeninových bází. Protože v DNA počítačích jde především o paralelismus, kdy vedle sebe vstoupí do reakce velké množství molekul, připravíme si takovýchto řetězců více.
Nyní si připravíme dělitele. Pro začátek je dobré si úlohu zjednodušit tak, že alespoň jeden z dělitelů nebude jistě větší než odmocnina z faktorizovaného čísla. Tedy nám stačí připravit si řetězce až do INT(SQR X). Řetězce budou opět jednovláknové, tvořené tentokrát komplementární bází – pokud jsme předtím použili adenin, vezmeme nyní tymin.
Nyní už je řešení úlohy v podstatě jasné: Původní řetězec necháme postupně reagovat s děliteli. Při tom se bude tvořit komplementární vlákno. Jak nahlédnete, celočíselné dělení bude znamenat, že oba řetězce se zcela překryjí (tj. např. pět tříbázových řetězců zcela pokryje původní 15bázový řetězec). Pokud však dělení neproběhne beze zbytku, bude jeden z řetězců přebývat… buď takto:
...A-A-A-A (původní řetězec) ...T-T-T (komplementární řetězec)
nebo např. takto:
...A-A-A-A (původní řetězec) ...T-T-T-T-T-T (komplementární řetězec)
V obou případech však dostaneme řetězce s „volnými“ bázemi. Pokud ke směsi přidáme např. magnetický (železem označený) adenin a magnetický tymin, řetězce s volnými bázemi se nám zarovnají – řetězce „správné“ už rovné jsou a železo tedy nevstřebají. Magnetem pak oddělíme „balast“, správné řešení je nemagnetické. Nemagnetické jsou i původní jednořetězcové báze, ty však také „zmagnetujeme“ přidáním bází komplementárních.
DNA počítače samozřejmě fungují pouze statisticky, předpokládáme však, že pokud přidáme molekuly ve velkých objemech, vytvoří reakce alespoň nějaké správné řešení. Výsledek budeme muset ověřit klasickým výpočtem, každopádně však získáme silně podezřelého kandidáta.
Co dál?
Pokud tento článek čtenáře zaujme, bude následovat další pokračování, kde se jednak pokusím vypořádat se s námitkami proti popsanému řešení, jednak uvést námitky vlastní (které jsou pro praktickou využitelnost postupu v tuto chvíli popravdě řečeno dosti zásadní :-(). Algoritmus samozřejmě nabízí mnoho příležitostí k upgradu, zde je popsána pouze nepříliš sofistikovaná logika (nechtěl jsem úvodní článek zatěžovat biochemickými složitostmi).
Kromě kritiky popsaného algoritmu samozřejmě uvítám i další návrhy, jak faktorizaci na DNA počítači provést. Může jít jak o zlepšení popsaného postupu, tak i o postup zcela odlišný.
Pokud se zajímáte o další hypotetické experimenty na DNA počítači a vymýšlení příslušných algoritmů, mohu nabídnout ještě pokus o simulaci „Výběru automobilů pomocí DNA počítače“. Jde o experiment, který právě provádí tvůrce prvního DNA počítače Leonard Adleman. Svůj postup však zatím nezveřejnil, proto může být zajímavé přemýšlet o tom, „jak to asi může dělat“.
ČLÁNKY DO MAILU