Shrnutí (co bude dál?)

Blahopřeji! Dosáhli jsme místa, kde se naše lekce dělí. Bylo uvedeno několik různých myšlenek a je potřeba, abychom se v nich zorientovali, než budeme pokračovat dál různými směry. Jaká byla motivace této lekce? Naučili jsme se něco o šifrování RSA a RSA záviselo na dvou věcech: 1) že rozklad na prvočísla je složitý. Takže když vynásobím dvě velká prvočísla: P1 a P2, která dají N, mohu se cítit bezpečně, protože vím, že vám zabere dlouhou dobu na tato prvočísla přijít, možná víc než celý život. 2) RSA vyžaduje, aby ta velká prvočísla, která jsem vygeneroval, byla jednoduchá - tím myslím, že jsem mohl rychle vygenerovat velké prvočíslo. Pojďme se vrátit k prvnímu problému: složitost rozkladu na prvočísla. Čím to je, že rozklad - nebo jen prvočísla samotná - dělají řešení tak složité? Abychom na to přišli, začali jsme s jádrem problému. Mějme x. Je x prvočíslo, nebo ne? - to je zkouška prvočíselnosti. Skončili jsme u sestavení několika řešení tohoto problému. A v průběhu jsme si uvědomili, že tento problém je výpočetně náročný. Že neexistuje jeho okamžité řešení. Jak se zvětšovalo vstupní číslo, množství času nebo počet kroků pro to, aby algoritmus našel řešení, také rostlo. A jak moc rostlo chápeme teď lépe - protože rozsah hledání dokážeme předpovídat za použití prvočíselné věty. Nicméně, o skutečném problému se dá přemýšlet jako o grafu, kde na ose y máme počet kroků, kolik náš algoritmus potřebuje. (Nebo si to můžete představit prostě jako čas.) a na ose x je velikost vstupu. A jak se zvětšila velikost vstupu, rostl i čas. No a potíž, kterou jsme měli, je, že tvar této křivky je nepřijatelný. Protože v našem případě, jakmile N dosáhne 20 číslic, už nemůžeme najít řešení - v tom nejhorším případě. Pokud na náš algoritmus vrhneme vstup o stovkách číslic, asi se všichni shodneme, že nebude fungovat. V našem případě by spadnul. Takže je prakticky nemožné zjistit, jestli je velké číslo prvočíslem, za použití našich současných metod. Pojďme se teď vrátit k prvnímu bodu - rozkladu na prvočísla. Uvědomte si - na základě toho, co jsme si vysvětlili v této lekci - že rozklad musí být náročnější než zkouška prvočíselnosti. Znamená to, že je potřeba udělat více kroků při hledání prvočíselného rozkladu nějakého čísla, než při pouhém oznámení, jestli je číslo prvočíslem. Připomeňte si, že rozklad vyžaduje, abychom našli všechny primární činitele nějakého vstupu N. Zatímco zkouška prvočíselnosti jenom vyžaduje, abychom našlli jednoho dělitele. Hezkou připomínkou je, že někteří uživatelé skutečně přetvořili tyto testy prvočíselnosti na algoritmy pro prvočíselný rozklad prostým opakováním po nalezení prvního dělitele. Takže zkouška prvočíselnosti je určitým druhem podprogramu uvnitř hlavního algoritmu rozkladu. Když se vrátíme k tomuhle grafu, rozkládací algoritmus by byl něco takového. Jak vstup roste, náš algoritmus by byl nad touto čárou zkoušky prvočíselnosti. A uvědomte si, že v jakékoliv situaci, máme vždycky výpočetní limit - to je počet nejmenších kroků, které dokážeme spočítat - což závisí na našem výpočetním výkonu v dané situaci - a množství času, který máme. Můžete si to představit jako vodorovnou čáru - nebo práh - na tomto grafu. Cokoliv nad čárou je mimo dosah - nemožné schůdně vyřešit. A v této lekci nás omezoval Roverův palubní počítač, který byl celkem pomalý - a to je důvod, proč jsme nemohli provádět zkoušky prvočíselnosti ani na číslech s 20 číslicemi. Nicméně, i kdybychom měli, řekněme, tisíc počítačů běžících rok, jednoduše by to posunulo tuto vodorovnou čáru nahoru k jinému prahu. Což by nám umožnilo spouštět testy na větších číslech. Ale jak vidíte, vždy bychom narazili na nějaký limit kde už je vstup dost velký na to, abychom nemohli problém vyřešit. Tahle informace vede k mnoha zajímavým otázkám. Já nicméně určím dvě, které budu prozkoumávat dál. Za prvé - dosud jsem nebyl úplně přesný ohledně těch křivek růstu. Přesto by se hodilo, kdyby - Představte si, že pro jakýkoliv algoritmus, který mi dáte - bez ohledu na to, co se snaží vyřešit - a dokonce bez ohledu na to, na jakém stroji běží - bychom mohli nakreslit odpovídající křivku růstu jednoduše tak, že se podíváme na popis daného algoritmu. Kdybychom tohle mohli udělat, dokázali bychom identifikovat kategorie nebo určité tvary růstu - které nám říkají, jak náročné bude daný problém vyřešit. A tímto způsobem bychom mohli pochopit algoritmus ještě před tím, než jsme ho vůbec spustili. Je velmi důležité se nad tím zamyslet. Mohli byste mi předat svůj algoritmus - napsaný na kousku papíru - a já bych se na něj mohl podívat a říct: "Hm, já vím, že tenhle algoritmus není řešitelný s velikostí vstupu, která je potřeba." A to nás vede k lekci o časové složitosti - neskutečně důležitý konceptuální nástroj, který budeme potřebovat. A pokud jste někdy zaslechli: "Tohle běží v polynomiálním čase nebo exponenciálním čase," tohle jsou pojmy, které vycházejí z časové složitosti. Dál, mnoho z vás přemýšlí: "Jak tedy generujeme tahle náhodná prvočísla ve skutečnosti?" - druhá myšlenka ohledně RSA, kterou jsem zmiňoval. Pojďme si ji jenom v rychlosti projít. Pro vygenerování velkého náhodného prvočísla, které tvoří stovky číslic, potřebujeme následovat tento postup: Vygenerovat náhodné číslo. Vyzkoušet, jestli je prvočíslem. Pokud ano, máme hotovo. Pokud ne, zkusit znovu, dokud se nenarazí na prvočíslo. V této tříkrokové proceduře je nejdůležitější druhý krok: Vyzkoušet, jestli je prvočíslem. Pokud tento krok nemůžeme vykonat, postup nebude fungovat. Takže jak to funguje dnes? Je to založeno na drobné úpravě definice problému - a, co je důležitější, na využití nahodilosti. A to nás vede k další lekci o náhodných algoritmech. A nyní, konečně, pokud máte nějaké další otázky pošlete je prosím tady dolů a můžeme naplánovat další lekce. Napříkad je tu trocha hlubší matematiky, kterou musíme ještě objevit, abychom zrychlili existující zkoušky prvočíselnosti. Co jiného váš ještě napadá? Prosím, podělte se dole.