Quote:
Originally Posted by Princ
a Valezius-sejtésről  |
Na akkor vettem a fáradtságot és beírtam googlebe, hogy prímtesztelés.
Az alapvető módszer az osztók keresése gyök n-ig, de ez iszonyat lassú. De szerencsére pár számelméleti eredmény felhasználásával lehet jobbat gyártani.
Ez nem sejtés, hanem tény
Quote:
A számok prímségének tesztelésére valószínűségi és determinisztikus tesztek állnak a rendelkezésünkre.
A valószínűségi tesztek (pl. Miller-Rabin teszt, Lucas prímteszt, Solovay-Strassen prímteszt) gyorsak, de nem döntik el teljes biztonsággal, hogy az input prím-e. Azonban a tévedés valószínűsége a teszt többszöri végrehajtásával – ha mindig pozitív a válasz – tetszőleges küszöbérték alá csökkenthető. Így ezek a módszerek kriptográfiai célokra – például RSA kulcsgenerálásra – megfelelőek.
A determinisztikus módszerek közül a legegyszerűbb eljárás, ha a számot sorban elosztjuk a gyökénél nem nagyobb természetes számokkal. Így biztos választ kapunk a szám prímségére vonatkozóan, azonban ez a módszer nagy számok esetében nagyon lassú (a szükséges lépésszám a szám hosszának exponenciális függvénye), ezért a gyakoratban nem is alkalmazzák. Léteznek ennél jobb algoritmusok is erre a célra, a jelenleg (2003) ismert legjobb determinisztikus módszer az Atkin-Morain teszt.
|
Az más kérdés, hogy Red le tudja-e programozni ezeket
Én biztos, hogy nem tudnám.