Hlavní navigace

Faktorizace na DNA počítači

Pavel Houser

DNA počítače by podobně jako počítače kvantové mohly pomoci tam, kde současná výpočetní technika selhává. Otázka zní: patří do této kategorie problémů také faktorizace? Lze ji realizovat na DNA počítači?

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“.

Našli jste v článku chybu?

21. 9. 2004 9:46

Tonda Jančařík (neregistrovaný)

Upřímně řečeno netuším, kde autor zaslechl, že faktorizace se dělá postupným zkoušením možných dělitelů. To tak asi na základní škole, když se má zjistit, že 26=2*13. Normální dítě začně mít problémy už třeba s 217 (není to náhodou prvočíslo? :-].
Vlastní faktorizace se dnes dělá pomocí konstrukce čísla, které modulo n dává čtverec. A to použitím "prosévání" a postupného skládání. Ale to už opouštíme "středoškolskou" matematiku.


26. 4. 2002 15:00

Emil Jerabek (neregistrovaný)

S prominutim, pan Oravce, jak jste prisel na takovy nesmysl? Ujistuju vas, ze at uz je to s NP-uplnosti faktorizace jakkoli, muzete si k tomu konzistentne primyslet jak CH, tak i jeji negaci.

Lupa.cz: Proč firmy málo chrání data? Chovají se logicky

Proč firmy málo chrání data? Chovají se logicky

Měšec.cz: Zdravotní a sociální pojištění 2017: Připlatíte

Zdravotní a sociální pojištění 2017: Připlatíte

DigiZone.cz: Recenze Westworld: zavraždit a...

Recenze Westworld: zavraždit a...

Vitalia.cz: Nestlé vyvinulo nový typ „netloustnoucího“ cukru

Nestlé vyvinulo nový typ „netloustnoucího“ cukru

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

120na80.cz: Pánové, pečujte o svoje přirození a prostatu

Pánové, pečujte o svoje přirození a prostatu

Vitalia.cz: 9 největších mýtů o mase

9 největších mýtů o mase

Vitalia.cz: Spor o mortadelu: podle Lidlu falšovaná nebyla

Spor o mortadelu: podle Lidlu falšovaná nebyla

Lupa.cz: Teletext je „internetem hipsterů“

Teletext je „internetem hipsterů“

Vitalia.cz: Paštiky plné masa ho zatím neuživí

Paštiky plné masa ho zatím neuživí

Podnikatel.cz: 1. den EET? Problémy s pokladnami

1. den EET? Problémy s pokladnami

Vitalia.cz: Jmenuje se Janina a žije bez cukru

Jmenuje se Janina a žije bez cukru

Vitalia.cz: Když přijdete o oko, přijdete na rok o řidičák

Když přijdete o oko, přijdete na rok o řidičák

Vitalia.cz: „Připluly“ z Německa a možná obsahují jed

„Připluly“ z Německa a možná obsahují jed

Podnikatel.cz: EET: Totálně nezvládli metodologii projektu

EET: Totálně nezvládli metodologii projektu

Podnikatel.cz: Snížení DPH na 15 % se netýká všech

Snížení DPH na 15 % se netýká všech

Podnikatel.cz: Udávání kvůli EET začalo

Udávání kvůli EET začalo

Lupa.cz: Propustili je z Avastu, už po nich sahá ESET

Propustili je z Avastu, už po nich sahá ESET

Lupa.cz: Co se dá měřit přes Internet věcí

Co se dá měřit přes Internet věcí

Vitalia.cz: Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky