Fő tartalom
Számítástudomány
Tantárgy/kurzus: Számítástudomány > 2. témakör
7. lecke: Véletlen algoritmusok- Véletlen algoritmusok (bevezetés)
- Feltételes valószínűség vizuális magyarázata
- Találd ki, melyik érme volt!
- Véletlen prímteszt (bemelegítő)
- 9. szint: Próbálkozásos osztás és véletlen osztás összehasonlítása
- Kis Fermat-tétel
- Fermat-prímteszt
- 10. szint: Fermat-prímteszt
© 2023 Khan AcademyFelhasználási feltételekAdatkezelési tájékoztatóSüti figyelmeztetés
Fermat-prímteszt
Miért és hogyan működik – gyors bemutatás. Készítette: Brit Cruise.
Szeretnél részt venni a beszélgetésben?
Még nincs hozzászólás.
Videóátirat
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?