Hódító / Queosia forum - Ne OFF-oljunk máshol II.

Hódító / Queosia forum (http://forum.hodito.hu/index.php)

- Chat (http://forum.hodito.hu/forumdisplay.php?f=49)

- - Ne OFF-oljunk máshol II. (http://forum.hodito.hu/showthread.php?t=4261)

Ti miről beszéltek?

Quote:

Originally Posted by Sami (Post 271426)

Ti miről beszéltek?

a Valezius-sejtésről :):)

Quote:

Originally Posted by Sami (Post 271426)

Ti miről beszéltek?

prím számok lilstázásához keresik a legjobb algoritmust... :)

Quote:

Originally Posted by Princ (Post 271427)

a Valezius-sejtésről :):)

:D :D

Quote:

Originally Posted by Princ (Post 271427)

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.

Quote:

Originally Posted by Valezius (Post 271447)

Na akkor vettem a fáradtságot és beírtam googlebe, hogy prímtesztelés.

Hogy mit vettel? :)

Quote:

Originally Posted by Valezius (Post 271447)

A determinisztikus módszernél elég csak az addig megismert prímszámainkkal elosztanunk? :o

1. lépés: vegyük fel egy tömbbe az összes ismeret prímszámot.
2. lépés: a kérdéses szám eleme az előző tömbnek? Ha igen, akkor prímszám, egyébként nem.

:D

Quote:

Originally Posted by Ati (Post 271461)

1. lépés: vegyük fel egy tömbbe az összes ismeret prímszámot.
2. lépés: a kérdéses szám eleme az előző tömbnek? Ha igen, akkor prímszám, egyébként nem.

:D

3. lépés: várjunk pár évet. :)
//Mármint ha nem csak egy fix számról szeretnénk eldönteni, hogy prím-e, hanem keresni új számokat...//

Rájöttem, inkább nem akarok tudni a prímszámokat :D 1mrd-ig futtatom, utána hagyom a fenébe. Majd némileg több matektudással visszatérek rá :)

A következő projekt egy viszonylag feltörhetetlen, de viszonylag gyors txt kódoló. Egyetlen módszer van elvileg, ami az eredeti kulcs nélkül feltörhetetlen, a xor-ozás :) de persze még nem kevés utánajárás kell ehhez :)

Quote:

Originally Posted by Andrew (Post 271460)

A determinisztikus módszernél elég csak az addig megismert prímszámainkkal elosztanunk? :o

Ja, csak ahhoz tárolni is kell az addig megismert prímszámokat.