Véletlen prímteszt (bemelegítő)

Először építsük fel az új típusú véletlen algoritmus elméleti működésének modelljét, ami fogad egy N bemenetet, és ha N prímszám, akkor az algoritmus 100%-os biztonsággal prímet ad vissza. Soha nem fogja azt mondani, hogy összetett. Viszont ha N összetett, van rá egy minimális „e” esély, hogy ezt is prímnek jelöli meg. Különben 1 mínusz ez a kicsi hiba a valószínűsége, hogy helyesen összetettnek fogja-e minősíteni N-et. Induljunk valami egyszerűvel. Vegyük az egész számokat egy adott határig. Válasszunk ki egy egész számot, jelöljük N-nel. Megadjuk ezt az N-et a gépnek. Korábban a próbálkozásos algoritmus módszernél iterációval végigvettük az összes értéket 1-től négyzetgyök N-ig, és megnéztük, hogy a szám osztója-e N-nek. Ideális esetben időspórolás miatt csak a prímszámokat vizsgáltuk. Ha A osztója N-nek, akkor tudjuk, hogy N összetett szám, mert bizonyítékot találtunk rá. Ha nem, akkor nem vagyunk benne biztosak. Visszatérünk, megnöveljük A-t, és újra tesztelünk. Ha kimerítettük az összes lehetséges tesztet, akkor kimondhatjuk: igen, N prímszám, nem találtunk osztót. Most pedig legyünk lusták. Mi lenne, ha csak néhány, véletlenül kiválasztott egészet vennénk, és azokkal végeznénk el az oszthatósági próbát? Ezt tekinthetjük véletlen tesztnek. Tudjuk azt, hogy egy tetszőleges N szám, ha összetett, van valahol elszórva osztója. Legalább egy osztója lesz. Egyes összetett számoknak sok osztója van. Szóval választunk egy véletlen A számot 1 és négyzetgyök N között. Ennyi. Aztán ellenőrizzük, hogy A osztója-e N-nek. Mint korábban is, ha A osztója N-nek, akkor biztosan tudjuk, N összetett, bizonyítékunk van rá. Ha nem, nem jutottunk sokkal előbbre, lehet akár prím is. A biztonság kedvéért generálhatunk még néhány véletlen A-t, és folytathatjuk a tesztelést. 100 vagy 1000 iteráció után megállhatunk és kimondhatjuk: „Valamilyen valószínűséggel feltehetőleg prímszám”. Mondjuk 99,9%-os valószínűséggel. Ez hasonlít az előző feltételes valószínűséges játékhoz. A legegyszerűbb helyzetben megpróbáltuk megbecsülni, hogy az érme normális vagy dupla oldalú. Ebben az esetben az írás olyan, mint az osztó megkeresése. Ez a normális érme bizonyítéka. A fej az az eset, amikor lehet, hogy új dobást, azaz egy új iterációt kérünk. Ebben az esetben úgy 5 fej után 90%-nál biztosabbak vagyunk, úgyhogy megállhatunk azt mondván: – Azt gondolom, az érme kétoldalas. Itt a program, ami összehasonlítja a régi, próbálkozásos osztást használó módszert ezzel az új, véletlen osztásos teszttel. Az eddigi leggyorsabb próbálkozásos osztás algoritmust használtam fel, amit Dino készített. A program fejlécében megtalálod a linket. Az elején ott a numTrials változó, ami a véletlen találgatások számát tárolja. Kezdjük egy kis számmal, mondjuk 3-mal. Figyeld meg, hogy kis bemenet esetén is, ha a bemenet prímszám, a véletlen osztásos algoritmus mindig prímszámot eredményez. Ha a bemenet összetett, a véletlen osztás tévedhet, és hibásan prímként azonosítja. Ezen javíthatunk úgy, hogy megnöveljük a próbálkozások számát, ekkor a hiba valószínűsége csökkenni fog. Láthatjuk, hogy most a két kimenet nagyjából megegyezik. Ahogy a bemenet értékét növelem, a hiba újból megnő. Ennek megfelelően növelnem kell a próbálkozások számát. Ekkor az eredmények megint szépen összecsengenek. Azonosnak tűnnek. Hatalmas bemeneti értékkel több ezer véletlen teszt kell a pontossághoz. Így nem igazán javítottuk a szükséges lépésszámot. Még mindig jobbnak tűnik a próbálkozásos osztás algoritmusa. Ennek az az oka, hogy az osztás tesztnek nagyon magas a hibaszázaléka, de már közelebb jutottunk. Megtaláltuk a helyes utat. Más tesztre van szükségünk. Olyan egyenlet kell, ami gyorsan kiszámolható, amivel bizonyíthatjuk, hogy a szám összetett. Nem csak a bemeneti N értéket kell fogadnia, hanem egy véletlen A egészet is, és el kell végeznie valamilyen véletlen tesztet.