„Félprímek” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
a Hozzáférés ideje (WP:BÜ), replaced: Retrieved on → Hozzáférés ideje: (2) |
|||
17. sor:
A félprímek vagy egy prímszám négyzetei, vagy négyzetmentesek.
Egy számról a prímtényezős felbontása nélkül eldönthető, hogy félprím-e,<ref>Chris Caldwell, [http://primes.utm.edu/glossary/page.php?sort=Semiprime ''The Prime Glossary: semiprime''] at The [[Prime Pages]].
Vannak módszerek, amelyekkel több száz jegyű félprímek állíthatók elő, ismeretlen prímtényezős felbontással. Ilyen módszerek a Goldwasser-Kilian ECPP tétel, vagy az elliptikus pszeudogörbék. Konstrukciójuk miatt az így kapott számok azonban sérülékenyebbek lehetnek a prímtényezős felbontás előállítására, emiatt gyakorlati hasznuk kevés.<ref>{{cite web|last=Broadhurst|first=David|url=http://physics.open.ac.uk/~dbroadhu/cert/semgpch.gp|title=To prove that N is a semiprime|date=12 March 2005|accessdate=2013-09-04}}</ref>
29. sor:
A félprímeket a [[számelmélet]]ben, különösen [[kriptográfia]]i alkalmazásokban a [[Nyilvános kulcsú rejtjelezés|nyílt kulcsú titkosítás]]nál alkalmazzák. Az [[RSA-eljárás]] arra alapul, hogy két nagy prímet találni és összeszorozni viszonylag könnyű, viszont a szorzatot [[Prímfelbontás|faktorizálni]], azaz a félprím ismeretében a szorzat tényezőit meghatározni nehéz.
Az RSA Factoring Challenge-ben a feladat bizonyos elég nagy félprímek prímtényezős felbontása volt. Az RSA Security díjakat tűzött ki a megoldóknak, és néhány díjat már el is vittek. A legutolsót 2007-ben zárták le.<ref>[http://www.rsa.com/rsalabs/node.asp?id=2092 Information Security, Governance, Risk, and Compliance - EMC]. RSA.
A gyakorlati kriptográfiában nem elegendő tetszőleges félprímet választani. Léteznek specializált faktorizáló algoritmusok, amelyek bizonyos alakú félprímeket hatékonyan tudnak faktorizálni, egy jó félprím pedig nehezen faktorizálható. A ''p'' és a ''q'' tényezők legyenek nagyok, közelítőleg azonos nagyságrendűek, de ne legyenek túl közel egymáshoz. Ez kivédi a [[triviális osztás]]t (kis prím az egyik tényező), és a [[Pollard-féle ró algoritmus]]t. Ha túl közel lennének egymáshoz, akkor a [[Fermat-faktorizáció]] miatt lehetne könnyen feltörni a kódot. A tényezők szomszédai se legyenek kis számok szorzatai, mert akkor alkalmazható lenne [[Pollard p-1 algoritmus]]a, vagy [[Williams p+1 algoritmus]]a. Mindezek azonban nem segítenek a titkos vagy jövőbeli algoritmusokkal szemben.
| |||