Félprímek

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,^[2] mivel ha nincs egy n számnak ${\displaystyle \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.^[3]

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

${\displaystyle \sum _{\Omega (n)=2}{\frac {1}{n^{2}}}\approx 0{,}1407604}$ ^[4]

${\displaystyle \sum _{\Omega (n)=2}{\frac {1}{n(n-1)}}\approx 0{,}17105}$ ^[5]

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

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

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.

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}.^[8]

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

További általánosítás itt olvasható.^[10]