Fermat-prímteszt

Az a célunk, hogy létrehozzunk egy utasítássort, amivel bizonyítani tudjuk, hogy egy adott bemeneti egész összetett, ellenkező esetben nagy pontossággal kimondhassuk róla, hogy prímszám. Ezt most már meg tudjuk tenni. Azonban hatékonynak is kell lenni. Ez azt jelenti, hogy bármely számítógépen gyorsan ki kell tudni számolni, és ha nő a bemenet értéke, ami az esetünkben a megadott N egész szám, akkor is gyorsan lefut. Mostanra a legmélyebb szinten megtanultuk, hogy egy olyan ismert tulajdonságot kell alapul venni, amivel minden prím rendelkezik, de csak nagyon kevés ilyen összetett szám található. Az előző videóban vizuálisan bemutattuk a kis Fermat-tételt, amiből egy nagyon érdekes szabály adódik. Adott egy P prímszám és egy másik tetszőleges A szám, ahol A kisebb, mint P. Tudjuk, P osztója A a P-ediken mínusz A-nak. Ezt úgy jelöljük, hogy A a P-ediken egyenlő A mod P. Általában ezt így fogod látni. Mivel A-nak és P-nek nincs közös osztója, hiszen P prímszám, használhatjuk az egyszerűsítés szabályát, ezért az egyenlettel ilyen formában is találkozhatsz: A a P-1-edik hatványon egyenlő 1-gyel modulo P, de ne feledd, egyszerűsíteni csak azért lehet, mert A-nak és P-nek a legnagyobb közös osztója 1. Összeállítottunk egy demót, ami bemutatja ezt az egyenletet működés közben, hogy jobban megbarátkozzunk vele. Figyeld meg, hogy ha megadunk egy P prímszámot, az eredmény mindig 1 lesz, függetlenül attól, hogy milyen A-t választok. Ha P-nek összetett számot választok, azt látjuk, hogy az eredmény általában nem 1, és ha az egyenlet bármikor 1-től eltérő eredményt ad, a szám biztosan összetett. Bizonyítékunk van arra, hogy a választott szám nem lehet prím. Ennek a tesztnek pont ez a lényege, és mielőtt mélyebben belemennénk, lépjünk egyet vissza, és készítsük el a teszt vázát az előbb bemutatott minta alapján. Így indul a teszt: adva van egy egész bemenet. Jelöljük P-vel. Ezután generálunk egy A véletlen számot, ami kisebb, mint P. Most megnézzük: A és P legnagyobb közös osztója 1? Ha nem, ha A és P legnagyobb közös osztója nagyobb, mint 1, akkor van közös osztójuk, és bebizonyítottuk, hogy P összetett, mert van osztója. Megállhatunk, és kiléphetünk, az algoritmus összetettet ad vissza. De ha igaz, akkor jön a kulcskérdés, A a P-1-dik hatványon modulo P értéke 1? Ha nem, bizonyítottuk, hogy P összetett. Megállhatunk, közölhetjük, hogy P összetett. Ha igen, ha az egyenlet eredménye 1, akkor prímnek kell lennie, igaz? Megírtam a programkódot, bal oldalt van a Fermat teszt, jobbra a meglevő próbálkozásos osztás, amit azért tettem oda, mert arról tudjuk, hogy mindig jó eredményt ad. Első látásra úgy tűnik, minden jól működik. De találtam egy problémás esetet. Beírtam 511-et, és most a Fermat teszt prímet ad, a próbálkozásos osztás összetett eredményt ad. 511 a teszt alapján prímszám, de valójában nem az. Térjünk vissza az egyenlethez, és nézzük meg, mi történt. Ez az úgynevezett álprím eset. Ez egy összetett szám, de vannak olyan A-k, amiknél 1-et ad eredményül. Ez bizony hibás. Azokat az A-kat, amik összetett számokra 1-et adnak, becsapós számoknak fogjuk hívni, mert becsapnak, hogy azt higgyük, a szám prím, de ha választunk egy másik A-t, akkor számos bizonyíték található az összetettségre. Vissza kell lépni a ciklusba az oszthatósági teszt esetén használt logika szerint, ahol egyszerűen megismételjük néhányszor a vizsgálatot, minden alkalommal egy új A-t generálva, és bízva abban, hogy nem fogunk mindig becsapós számot választani. Bizonyítható, hogy a becsapós számok számossága osztója azon halmaz számosságának, amiből választunk. Ebből következik, hogy maximum a választások fele, azaz a választható számok fele lehet becsapós. Mivel A-t véletlenszerűen választjuk, annak a valószínűsége, hogy bizonyítékot találjunk az összetettségre, az eredeti célunk szerint, legalább 1/2. t iteráció után annak a valószínűsége, hogy nem találunk bizonyítékot összetett szám esetén: maximum 1/2 a t-edik hatványon. 20 próbálkozás után annak a valószínűsége, hogy tévesen prímszámot mondunk, valamivel meghaladja az egy milliomodot. [Pontosabban majdnem egy milliomod.] Ez az az eset, amikor folyamatosan pechesek vagyunk, és a generált véletlen A-k minden esetben becsapósak. Ha ezt meg tudod érteni, nagyon hatékony eszköz lesz a kezedben. Itt láthatod a tesztet működés közben, ahol megnöveltük a próbálkozások számát. Úgy tűnik, tökéletesen működik, és figyeld meg, hogy a legrosszabb esetben, amikor az algoritmusnak prímszámot adunk meg, akkor kell a legtöbbet dolgoznia. A Fermat teszt sokkal hatékonyabb, mint a próbálkozásos osztás. Különösen azért, mert a lépések száma nem sokszorozódik meg a bemenet értékének növekedésével, és ez a fő különbség. Beállítjuk a próbálkozások számát, és ennyi elég is. Nem kell törődnünk avval, hogy az algoritmus több millió iterációt hajt végre, mint a korábbi teszteknél. Ez színtiszta alkalmazott matematika. Fogunk egy összefüggést, amit valaki felfedezett, és ezt felhasználva rengeteg számítási ciklust tudunk megspórolni. De van ebben a rendszerben egy apró hiányosság, vagy hiba. Meg tudod találni?