Milyen módszerrel, algoritmussal generálhatok álprímeket? Olyan számokat, amelyek átmennek a Miller-Rabin prímteszten (pl.2-es alappal), és mégsem prímek.

@15:57

"A próbaosztás lassúsága érdekes, nem gondoltam, hogy ez a mai számítási kapacitás mellett is gond."

Az paraméterezés kérdése, a számítási kapacitás meg adott. A számokból végtelen sok van, úgy van megadva a biztonsági követlemény, hogy az RSA akkora prímekkel dolgozzon, hogy ne lehessen "értelmes" időn belül prímtényezőkre bontani, a prímszámok titkosak, a szorzatuk publikus. Ami prímteszttel ellenőrizhető, hogy összetett szám, de felbontani nem tudjuk. Ha a prímteszt azt adja, hogy összetett az biztos, ha nem akkor talán prím. Ezért kell több teszt, ha prímet ad.

Ha akkora számokkal dolgozna az RSA, hogy kiszámítható lenne értelmes időn belül a prímtényezői akkor nem adna biztonságot. Egyébként rosszul megválaszott prímekkel is kiszámítható hiába elég nagyok azok. Például ha közel vannak egymáshoz, hiszen akkor a szorzat négyzet gyöke körül kell keresni és megvan.

"De akkor jól értem, hogy az, hogy ál-prím szám, az nem egy matematikai fogalom?!"

Az egy matematikai fogalom, gyűjtőfogalom. Konkrétan itt a Miller-Rabin prímteszt 2-es alapra adott álprímjeiről van szó.

"Az mindenesetre igen érdekes, és micsoda ötlet/elme lehet a mögött, amikor csak "tippelnek" ezek a tesztelő algoritmusok!"

A prímszám definícióján túlmutatóan bizonyos tulajdonságokkal rendelkeznek a prímszámok, valami van még bennük ami prímszerű. Ilyen prímszerű tulajdonságaik nem csak prímszámoknak vannak. A BPSW prímtesztnek egyetlen ismert álprímje sincs, pedig van neki és kutatási terület is. Az egy Miller-Rabin teszt 2-es alapra és egy Lucas-Selfridge ötvözete. Vannak különben olyan prímteszek is melyeknek nincsennek álprímjei (és nem a próbaosztásról beszélek, annál jóval gyorsabbak ezek is), de azok lassabbak és gyakorlatban meg a hibázási valószínűséget annyira le lehet vinni a zéró közelébe (hogy gyakorlatilag sosem következik be), hogy jobban megéri a valószínűségi prímtesztekkel a sebességük miatt.

@17:11

Te is megoszod róla a forráskódod?

Húú annyira komplikált. Ha valamilyen opció szerinti működésre van szükség és, ha a logikailag konzisztens azzal, hogy enumot használjunk akkor erre van az enmum python-ban : [link]

Még rendszerhívások esetében is aminek az interface, hardverközelibb ,ahol alig vannak típusok még ott is követik ezt az elvet pl. python-ban az os modulban bármi ami csupa nagypetűs egy-egy ilyen konstans, igaz azok nem külön-külön típusok csak sima integer-ek, mivel így kompatibilisek a hardverközelibb interface-el rendelkező rendszerhívásokkal.

Még néhány tipp:

A paraméterek típusainak jelölése. Nincs explicit típus deklarálás python-ban de jelölni lehet a típust, ami a kód átláthatóságát javítja : [link]

A függvények deklarációs sora után egy rövid összefoglaló leírás a """ vagy ''' kezdő és záró kommenttel ellátva. Ez segít akkor ha interkatív módban használod a python és kiadod a help(függvényneve), vagy ipythonban lehet függvényneve? is, illetve ha doc generátorral így lehet automatikusan dokumentációt csinálni belőle.

-----

Én is megcsináltam pythonban is.

Mindössze csak ennyi a kódom tokostól vonóstól: [link]