var SectionTitles=new Array( "Faktorizace na DNA poΦφtaΦi" , " V ka₧dΘm "dvojvlßknu" musφ proti sob∞ s" , " Co dßl?" );
var SectionURLs=new Array( "178" , "178#Title1" , "178#Title2" );
var BrothersNames = new Array("Hacking bez tajmenstvφ : (skoro) teroristickß p°φruΦka ! ;-)","Jen ty XP nezr∙caj","NovΘ chyby v PHP","Hackujeme pomocφ krabice od chips∙ a blikßnφ diod...","BookTip : Elektronick² podpis","Faktorizace na DNA poΦφtaΦi","XML: co je a k Φemu slou₧φ?","X kam se podφvßÜ","Memy: infekΦnφ informace","");
var BrothersIDs = new Array("112","128","147","160","172","178","219","228","229","");
//=====INFO======
ItemName='Article178';
InIFrame='No';
TableNum=2;
ItemID=178;
ArticleType='1';
Action='articles'
ItemTitle='Faktorizace na DNA poΦφtaΦi';
ItemComment='Faktorizace na DNA poΦφtaΦi';
TabName='Articles'
Parent1Title='Ostatnφ' ;
Parent2Title='Domßcφ strßnka' ;
Parent1ID='18' ;
Parent2ID='1' ;
ParentTitle='Ostatnφ' ;
AuthorName='Pavel Houser' ;
AuthorDesc='Autor je _259A_25E9fredaktorem serveru Scienceworld.cz' ;
ArticleHead('Faktorizace na DNA poΦφtaΦi', 'Pavel Houser', 'pavel_houser_40idg.cz', '22.4.2002', '02:00:00', '╚lßnek');
Intro('DNA poΦφtaΦe podobn∞ jako poΦφtaΦe kvantovΘ by 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? Problematika mo₧nΘho provedenφ faktorizace na DNA poΦφtaΦi p°iÜla p°itom autorovi tohoto Φlßnku jako natolik zajφmavß, ₧e text nabφdl k \"otiÜt∞nφ\" vφce server∙m - Φist∞ z toho d∙vodu, aby takto obdr₧el co nejvφce komentß°∙ od Φtenß°∙.');
Faktorizace je proces, p°i kterΘm se sna₧φme rozlo₧it urΦitΘ zadanΘ Φφslo na dv∞ prvoΦφsla. Jednß se o ·lohu, je₧ m∙₧eme °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).
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
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.)
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
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Φ.
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
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 :-).
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
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Θ.
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
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:
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
<PRE>---A-C-G-A-T-T---
---T-G-C-T-A-A---</PRE>
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
Zßjemce o podrobn∞jÜφ v²klad lze odkßzat na Φlßnek BiochemickΘ zßklady DNA poΦφtaΦ∙ (<a href=../www.scienceworld.cz/sw.nsf/page/2FE7C13863FC7C0FC1256A0F003A32B2>zde</a>). ╪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ßn nap°. op∞t na Science Worldu zde (<a href=../www.scienceworld.cz/sw.nsf/tisk/FC76F44DC014D172C1256A420056B4A6>zde</a>).
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
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?
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
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.
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
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, nynφ vezmeme tymin.
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
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°. 5 t°φbazov²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...
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, alespo≥ n∞jakΘ sprßvnΘ °eÜenφ reakce vytvo°φ. 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.
Pokud tento Φlßnek Φtenß°e zaujme, bude nßsledovat dalÜφ pokraΦovßnφ, kde se jednak pokusφm vypo°ßdat 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 popsanß pouze nep°φliÜ sofistikovanß logika (necht∞l jsem ·vodnφ Φlßnek zat∞₧ovat biochemick²mi slo₧itostmi).
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
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" (<a href=../www.scienceworld.cz/sw.nsf/page/CDA2FCC083DB772CC1256B9D003C85CB>zde</a>). 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".
</DIV></FONT></b></i>
<FONT Size=2><DIV Align=Justify Class=Paragraph>
</DIV></FONT></b></i>
</DIV>
<SCRIPT>
TextEnd('')
</SCRIPT><OL Class=None Type=Disc></OL><SCRIPT>
nie('<br>');AdditionalTablesBegin();
YesNoVoting('Vφce informacφ o DNA poΦφtaΦφch?',24,2,16, 1);
