|
|
![Hódító / Queosia forum](v6/forum_head.png) |
Hódító / Queosia forum
http://queosia.com
http://hodito.hu
|
|
Chat Általános chat-be torkollott témák... :) |
![Old](v6/statusicon/post_old.gif)
11-23-2010, 06:45
|
Banned
|
|
Join Date: Apr 2008
Location: Beregszász
Posts: 617
Activity: 0%
Longevity: 88%
|
|
Ti miről beszéltek?
|
![Old](v6/statusicon/post_old.gif)
11-23-2010, 07:53
|
![Princ's Avatar](image.php?s=b5f8066157cff10b07b5cf47ff15f063&u=456&dateline=1206616067) |
Member
|
|
Join Date: Feb 2006
Location: Budapest
Posts: 1,087
Activity: 0%
Longevity: 99%
|
|
Quote:
Originally Posted by Sami
Ti miről beszéltek?
|
a Valezius-sejtésről ![Smile](images/smilies/smile.gif) ![Smile](images/smilies/smile.gif)
__________________
|
![Old](v6/statusicon/post_old.gif)
11-23-2010, 11:11
|
![Dew's Avatar](image.php?s=b5f8066157cff10b07b5cf47ff15f063&u=3876&dateline=1289947175) |
Member
|
|
Join Date: Oct 2008
Location: Budapest
Posts: 556
Activity: 0%
Longevity: 85%
|
|
Quote:
Originally Posted by Sami
Ti miről beszéltek?
|
prím számok lilstázásához keresik a legjobb algoritmust...
Quote:
Originally Posted by Princ
a Valezius-sejtésről ![Smile](images/smilies/smile.gif) ![Smile](images/smilies/smile.gif)
|
![Big Grin](images/smilies/biggrin.gif)
|
![Old](v6/statusicon/post_old.gif)
11-23-2010, 13:56
|
Senior Member
|
|
Join Date: Oct 2006
Location: Veresegyház
Posts: 3,662
Activity: 0%
Longevity: 95%
|
|
Quote:
Originally Posted by Princ
a Valezius-sejtésről ![Smile](images/smilies/smile.gif) ![Smile](images/smilies/smile.gif)
|
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 ![Smile](images/smilies/smile.gif) Én biztos, hogy nem tudnám.
Last edited by Valezius; 11-23-2010 at 13:58..
|
The Following 3 Users Say Thank You to Valezius For This Useful Post:
|
|
![Old](v6/statusicon/post_old.gif)
11-23-2010, 14:12
|
Senior Member
|
|
Join Date: Jan 2006
Posts: 5,907
Activity: 0%
Longevity: 99%
|
|
Quote:
Originally Posted by Valezius
Na akkor vettem a fáradtságot és beírtam googlebe, hogy prímtesztelés.
|
Hogy mit vettel? ![Smile](images/smilies/smile.gif)
__________________
Remedy
|
![Old](v6/statusicon/post_old.gif)
11-23-2010, 18:34
|
![Andrew's Avatar](image.php?s=b5f8066157cff10b07b5cf47ff15f063&u=1616&dateline=1200680803) |
Member
|
|
Join Date: Dec 2006
Location: Tatabánya/Szeged
Posts: 2,796
Activity: 0%
Longevity: 95%
|
|
Quote:
Originally Posted by Valezius
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
Az más kérdés, hogy Red le tudja-e programozni ezeket ![Smile](images/smilies/smile.gif) Én biztos, hogy nem tudnám.
|
A determinisztikus módszernél elég csak az addig megismert prímszámainkkal elosztanunk? ![Embarrassment](images/smilies/redface.gif)
Last edited by Andrew; 11-23-2010 at 18:36..
|
![Old](v6/statusicon/post_old.gif)
11-23-2010, 18:42
|
Administrator
|
|
Join Date: Jan 2006
Posts: 25,199
Activity: 3%
Longevity: 100%
|
|
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.
![Big Grin](images/smilies/biggrin.gif)
|
The Following User Says Thank You to Ati For This Useful Post:
|
|
![Old](v6/statusicon/post_old.gif)
11-23-2010, 18:44
|
Member
|
|
Join Date: Apr 2007
Location: Budapest
Posts: 2,382
Activity: 0%
Longevity: 93%
|
|
Quote:
Originally Posted by Ati
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.
![Big Grin](images/smilies/biggrin.gif)
|
3. lépés: várjunk pár évet. ![Smile](images/smilies/smile.gif)
//Mármint ha nem csak egy fix számról szeretnénk eldönteni, hogy prím-e, hanem keresni új számokat...//
Last edited by Dus; 11-23-2010 at 18:47..
|
![Old](v6/statusicon/post_old.gif)
11-23-2010, 20:00
|
![Redback's Avatar](image.php?s=b5f8066157cff10b07b5cf47ff15f063&u=2421&dateline=1270410028) |
Member
|
|
Join Date: Jun 2007
Location: Nyíregyháza
Posts: 2,975
Activity: 0%
Longevity: 92%
|
|
Rájöttem, inkább nem akarok tudni a prímszámokat ![Big Grin](images/smilies/biggrin.gif) 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 ![Smile](images/smilies/smile.gif) de persze még nem kevés utánajárás kell ehhez ![Smile](images/smilies/smile.gif)
__________________
Redológia (#455305) [1/A] [SZK]
Non omnis moriar (#701164) [3/G]
|
![Old](v6/statusicon/post_old.gif)
11-23-2010, 20:05
|
Senior Member
|
|
Join Date: Oct 2006
Location: Veresegyház
Posts: 3,662
Activity: 0%
Longevity: 95%
|
|
Quote:
Originally Posted by Andrew
A determinisztikus módszernél elég csak az addig megismert prímszámainkkal elosztanunk? ![Embarrassment](images/smilies/redface.gif)
|
Ja, csak ahhoz tárolni is kell az addig megismert prímszámokat.
|
Currently Active Users Viewing This Thread: 4 (0 members and 4 guests)
|
|
Posting Rules
|
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off
|
|
|
Similar Threads
|
Thread |
Thread Starter |
Forum |
Replies |
Last Post |
Ne OFF-oljunk máshol.
|
Pool |
Chat |
536 |
06-20-2010 13:06 |
All times are GMT +1. The time now is 08:07.
![](v6/bg_foot.png) |
|
|
|
|
|
|