Összefoglaló (hogyan tovább?)

Gratulálok. Elérkeztünk egy útelágazáshoz a leckénkben. Bevezettünk néhány új gondolatot, úgyhogy fontos, hogy mielőtt továbblépünk, vizsgáljuk meg a különböző lehetőségeket. Mi volt a célja ennek a leckének? Megtanultuk, mi az RSA titkosítási eljárás. Az RSA két dolgon alapul. Először, hogy a prímtényezőkre bontás nehéz. Ha két nagy prímet, P1-et és P2-t összeszorzunk, és megadom N-et, akkor bízhatom abban, hogy hosszú idő kell a prímszámok megtalálásához, akár az egész életednél is hosszabb. Másodsorban az RSA-hoz az is kell, hogy a két prímszám generálása könnyű legyen, azaz gyorsan tudjak generálni nagy prímszámot. Térjünk vissza az első feladatra. A prímtényezőkre bontás nehézségére. A prímtényezőkre bontás a nehéz, vagy maguk a prímszámok teszik nehézzé a problémát? Ahhoz, hogy ezt megválaszoljuk, egy alapproblémával kezdjük. Ha adva van X, akkor X prím, vagy összetett? Ez a prímteszt. Végül eljutottunk odáig, hogy készítettünk néhány megoldást. Ennek során rájöttünk, hogy a probléma kiszámítása sok számítási erőforrást igényel. Azaz a feladatnak nincs azonnali megoldása. A bemeneti szám növekedésével a szükséges idő vagy az algoritmus lépéseinek száma szintén megnövekedett. A növekedés mértékét most már jobban megértjük, mert meg tudjuk becsülni a keresési tér méretét a prímszám tétellel. A problémát egy grafikonnal írhatjuk le, ahol a függőleges tengelyen ábrázoljuk az algoritmus lépéseinek számát, amit vehetsz úgy, hogy ez az idő. Az X tengelyen a bemenet mérete szerepel, és ahogy nőtt a bemenet mérete, úgy nőtt az idő is. A problémát az jelentette, hogy a görbe alakja elfogadhatatlan. Mert az esetünkben, amikor N elérte a 20 számjegyet, akkor a legrosszabb esetben már nem tudtuk megoldani a feladatot. Több száz számjegyű bemenetnél egyértelmű, hogy az algoritmusunk működésképtelen. Ebben az esetben összeomlik. Gyakorlatilag lehetetlen nagy bemenet esetén megvizsgálni a jelenlegi stratégiával, hogy az prímszám-e. Térjünk vissza az első pontra, a prímtényezőkre bontásra. Jelenlegi tudásunk alapján a prímtényezőkre bontásnak nehezebbnek kell lennie a prímtesztnél. Más szóval több lépés kell egy szám prímtényezőinek megkereséséhez, mint ahhoz, hogy kiderítsük, az prímszám-e, mert valamilyen N szám prímtényezőkre bontásához az összeset meg kell találni, míg a prímteszt esetében elég egy osztót megtalálni. Erre jó példa, hogy volt olyan felhasználó, aki a prímtesztet prímtényezőkre bontás algoritmusává alakította úgy, hogy az első osztó megkeresése után visszatért a ciklusba. Tulajdonképpen a prímteszt a prímtényezős felosztás algoritmusának szubrutinja. Ha visszatérünk ehhez a grafikonhoz, a prímtényezőkre bontás algoritmusa ilyen lenne. Ahogy növekszik a bemenet, a prímtényezőkre bontás algoritmusa a prímteszt vonal fölött haladna. Ne feledd, hogy minden helyzetben ott van a számítási korlát, azaz a lehetséges lépések száma, ami az adott helyzetben meglévő számítási kapacitástól és rendelkezésre álló időtől függ. Ezt elképzelheted egy vízszintes vonalként, ami egy korlát a grafikonon. Minden, ami a vonal fölé esik elérhetetlen, azaz nem megoldható. Ebben a leckében a korlát a marsjáró fedélzeti számítógépe, ami meglehetősen lassú, ezért nem tudunk prímtesztet futtatni még 20 számjegyű számokra se, de még ha 1000 gépen futtatnánk egy évig, azzal is csak annyit érnénk el, hogy a vízszintes határvonalat feljebb tolnánk. Ez lehetővé tenné, hogy a tesztet nagyobb számokra futtassuk, de mindig beleütköznénk valamilyen korlátba, ahol, ha elég nagy a bemenet, a feladatot nem tudnánk megoldani. Ez számos érdekes gondolatot vet fel. Itt most kiemelek kettőt, amikről részletesebben beszélni fogok. Először is, mindez ideig nem részleteztem a növekedési görbéket. Bár hasznos lenne, ha bármilyen adott algoritmus esetén, függetlenül a megoldandó feladattól vagy a géptől, amin futni fog, meg tudnánk rajzolni a növekedési görbét a grafikonon az algoritmus leírása alapján. Ha ezt meg tudnánk csinálni, kategorizálni tudnánk a növekedés alakja szerint, attól függően, hogy milyen nehéz a feladat megoldása. Így megérthetnénk az algoritmust futás előtt, ezt érdemes lenne végiggondolni. Odaadhatnád az algoritmusodat egy darab papíron, megnézném, és meg tudnám mondani: „Tudom, hogy az algoritmus a bemenet elvárt méretére nem megoldható.” Ez elvezet a komplexitás időfüggvényéről szóló fejezethez, ami egy nagyon fontos és szükséges fogalom és eszköz. Ha azt mondják, hogy a futási idő polinomiális, vagy exponenciális, akkor evvel a komplexitás időfüggvényére utalnak. Többeteknek eszébe jutott: „A gyakorlatban hogyan generáljuk azokat a véletlen prímeket?” Ez a második szempont az RSA-val kapcsolatban. Gyorsan vegyük végig. Egy több száz számjegyből álló prímszám generálásához az alábbi utasításokat kell végrehajtanod: generálj egy véletlen számot, ellenőrizd, hogy prímszám-e. ha prímszám, megvagyunk. Ha nem, addig próbálkozz, amíg nem találsz egyet. Ebben a háromlépéses eljárásban a legfontosabb a második lépés, a prímteszt. Ha ezt nem tudjuk elvégezni, akkor a dolog nem működik. Ezt manapság hogyan csinálják? A megoldás alapja, hogy a problémát ravaszul módosították, valamint, ami még fontosabb, a véletlenszerűség. Ez elvezet a véletlen algoritmusokról szóló másik fejezethez. Végül még annyit, ha maradt még megválaszolatlan kérdésed, oszd meg velünk a Kérdések szekcióban, hogy újabb fejezeteket indíthassunk. Például felfedezhetünk további matematikai összefüggéseket a jelenlegi próbálkozásos osztáson alapuló prímteszt felgyorsításához. Mi minden jár még a fejedben? Kérlek, oszd meg velünk!