Félprímek

két prímszám szorzata
Ez a közzétett változat, ellenőrizve: 2023. január 2.

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, … [1]

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

Tulajdonságok

szerkesztés

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,[2] mivel ha nincs egy n számnak   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:

 [4]
 [5]
 [6]

Alkalmazások

szerkesztés

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.

Ikerfélprímek

szerkesztés

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]

  1. (A001358 sorozat az OEIS-ben)
  2. Chris Caldwell: The Prime Glossary: semiprime (PrimePages), hozzáférés: 2013-09-04
  3. Broadhurst, David: To prove that N is a semiprime, 2005. március 12. (Hozzáférés: 2013. szeptember 4.)
  4. (A117543 sorozat az OEIS-ben)
  5. (A152447 sorozat az OEIS-ben)
  6. (A154928 sorozat az OEIS-ben)
  7. Information Security, Governance, Risk, and Compliance - EMC Archiválva 2013. május 7-i dátummal a Wayback Machine-ben RSA, hozzáférés: 2014-05-11
  8. Stanley Rabinowitz (szerk.): Index to Mathematical Problems, 1980-1984. 231. o.
  9. [https://arxiv.org/pdf/1002.2899.pdf Pintz János: Are there arbitrarily long arithmetic progressions in the sequence of twin primes? 28. o.]
  10. (A202319 sorozat az OEIS-ben)