Sophie Germain-prím

A számelméletben Sophie Germain-prímnek nevezzük azokat a p prímszámokat, amelyre 2p + 1 szintén prímszám. Ezeket a számokat a francia matematikusról, Marie-Sophie Germainről nevezték el. A Sophie Germain-prímből számított 2p+1 számot nevezzük biztonságos prímnek is. Létezik egy sejtés, hogy végtelen sok Sophie Germain-prím létezik, de mint az ikerprím-sejtés, ez sem bizonyított.

Az első néhány Sophie Germain-prím (1000-nél kisebb):

2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 179, 191, 233, 239, 251, 281, 293, 359, 419, 431, 443, 491, 509, 593, 641, 653, 659, 683, 719, 743, 761, 809, 911, 953 ...

A005384

Sophie Germain-prímek keresése

A matematika megoldatlan problémája:

Létezik-e végtelen sok Sophie Germain-prím?

(A matematika további megoldatlan problémái)

A PrimeGrid, valamint Twin Prime Search elosztott számítási projektek futtatnak keresést, több egyéb mellett a Sophie Germain-prímek megtalálására is.

Az ismert legnagyobb Sophie Germain-prímek (2018. novemberi állapot):

Szám	Számjegyek száma	Megtalálás ideje	Megtaláló és módszere
2618163402417 × 2^1290000 − 1	388342	2016. február	Scott Brown: PrimeGrid ^[1]
18543637900515 × 2⁶⁶⁶⁶⁶⁷ − 1	200701	2012. április	Philipp Bliedung: elosztott PrimeGrid kereséssel, valamint TwinGen és LLR^[2] használatával
183027 × 2²⁶⁵⁴⁴⁰ − 1	79911	2010. március	Tom Wu: LLR használatával^[3]
648621027630345 × 2²⁵³⁸²⁴ − 1 és 620366307356565 × 2²⁵³⁸²⁴ − 1	76424	2009. november	Járai Zoltán, Farkas Gábor, Csajbók Tímea, Kasza János és Járai Antal^[4]^[5]
607095 × 2¹⁷⁶³¹¹ − 1	53081	2009. szeptember	Tom Wu^[6]
48047305725 × 2¹⁷²⁴⁰³ − 1	51910	2007. január	David Underbakke: TwinGen és LLR használatával^[7]
137211941292195 × 2¹⁷¹⁹⁶⁰ − 1	51780	2006. május	Járai Zoltán, Farkas Gábor, Csajbók Tímea, Kasza János és Járai Antal^[8]

Alkalmazása

Jelentős szerepe van a különböző kriptográfiai megoldásokban, ahol $1,846,389,521,368+11^{600}$ -nél nagyobb számokra, erős prímekre van szükség. Mivel a p Sophie Germain-prímből származtatható 2p + 1 számot "biztonságos" prímnek tekintjük, ahhoz hogy "erős" prím legyen, a p - 1 és a p + 1 is nagy prímtényezőkkel kell hogy rendelkezzen. Ezekre az "erős" prímekre van szükség például az RSA algoritmusnál, hogy ne lehessen bizonyos faktorizáló eljárásokkal, mint például a Pollard (p – 1) vagy Williams (p+1) algoritmussal feltörni.

Jegyzetek

Kapcsolódó szócikkek

Biztonságos prímek
Cunningham-lánc

Ez a matematikai tárgyú lap egyelőre csonk (erősen hiányos). Segíts te is, hogy igazi szócikk lehessen belőle!

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]