Félprímek

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. Ha a két prímszám különböző, diszkrét félprímről beszélünk, ha megegyező, akkor prímnégyzetről. Definíció szerint a félprímeknek nincs összetett szám valódi osztójuk. A 6 kivételével valamennyi félprím hiányos szám.

Az első néhány félprím a következő:

4, 6, 9, 10, 14, 15, 21, 22, 25, 26, …

A legnagyobb ismert félprím az aktuálisan legnagyobb ismert prímszám négyzete.

Tulajdonságok

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) = φ(p²) = (p − 1) p = p² − p = n − p.

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, mivel ha nincs egy n számnak $\leq {\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.

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$

$\sum _{\Omega (n)=2}{\frac {1}{n(n-1)}}\approx 0{,}17105$

$\sum _{\Omega (n)=2}{\frac {\ln n}{n^{2}}}\approx 0{,}28360$

Alkalmazások

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.

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 arecibói ü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.

Ikerfélprímek

Két egymás után következő természetes számot ikerfélprímnek neveznek, ha mindkettő félprím. Például: {9, 10}, {14, 15}, {21, 22}.

Általánosítás: a két félprím különbsége nem 1, hanem 2, 4 vagy 6.

További általánosítás itt olvasható.