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.

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

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

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.

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.