Félprímek

A Wikipédiából, a szabad enciklopédiából

Félprím (vagy pq szám) minden olyan természetes szám, amely két (nem feltétlenül különböző) prímszám szorzata. Az első néhány félprím a következő:

4, 6, 9, 10, 14, 15, 21, 22, 25, 26, … (A001358 sorozat az OEIS-ben)

2007-ben a legnagyobb ismert félprím a (232 582 657 ‒ 1)2. Ez a legnagyobb ismert prímszám négyzete. Minden prímszám négyzete félprím.

Tulajdonságok[szerkesztés | forrásszöveg szerkesztése]

Az Euler-függvény értéke egyszerűen kifejezhető abban az esetben, ha p és q különbözőek:

φ(n) = (p − 1) (q − 1) = p q − (p + q) + 1 = n − (p + q) + 1.

Ha p és q megegyeznek, akkor

φ(n) = φ(p2) = (p − 1) p = p2p = np.

Nincsenek valódi nem prím osztóik, vagyis egyetlen összetett szám osztójuk önmaguk.

Definíció szerint prímtényezőik száma 2.

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, [1] mivel ha nincs egy n számnak \le \sqrt[3]{n} prímosztója, akkor vagy prím (amire szintén vannak tesztek), vagy félprím.

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.[2]

A prím zéta-függvény ötlete általánosítható félprímekre is. így kaphatók a következő konstansok:

\sum_{\Omega(n)=2} \frac{1}{n^2} \approx 0.1407604 (A117543 sorozat az OEIS-ben)
\sum_{\Omega(n)=2} \frac{1}{n(n-1)} \approx 0.17105 (A152447 sorozat az OEIS-ben)
\sum_{\Omega(n)=2} \frac{\ln n}{n^2} \approx 0.28360 (A154928 sorozat az OEIS-ben)

Alkalmazások[szerkesztés | forrásszöveg szerkesztése]

A félprímeket a számelméletben, különösen kriptográfiai alkalmazásokban a nyílt kulcsú titkosításná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 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.[3]

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ást (kis prím az egyik tényező), és a Pollard-féle ró algoritmust. 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 algoritmusa, vagy Williams p+1 algoritmusa. Mindezek azonban nem segítenek a titkos vagy jövőbeli algoritmusokkal szemben.

Az Arecibo üzenetet 1974-ben sugározták a világűrbe, mint 1679 bináris jelet. Ezt sematikus ábrákat tartalmazó téglalap alakú táblázatként alkották meg. Azért, hogy a földönkívüliek is meg tudják fejteni, a téglalap méretei 23×73, hogy csak egyféleképpen készíthessék el.

  1. Chris Caldwell, The Prime Glossary: semiprime at The Prime Pages. Retrieved on 2013-09-04.
  2. Broadhurst, David: To prove that N is a semiprime, 2005. március 12. (Hozzáférés: 2013. szeptember 4.)
  3. Information Security, Governance, Risk, and Compliance - EMC. RSA. Retrieved on 2014-05-11.