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

↑ The Prime Database: 2618163402417×2^1290000 - 1 (angol nyelven). primes.utm.edu. (Hozzáférés: 2017. január 9.)
↑ PrimeGrid’s Sophie Germain Prime Search (PDF). PrimeGrid. (Hozzáférés: 2017. január 9.)
↑ The Prime Database: 183027*2^265440 (angol nyelven). primes.utm.edu. (Hozzáférés: 2017. január 9.)
↑ The Prime Database: 648621027630345*2^253824-1 (angol nyelven). primes.utm.edu. (Hozzáférés: 2017. január 9.)
↑ The Prime Database: 620366307356565*2^253824-1 (angol nyelven). primes.utm.edu. (Hozzáférés: 2017. január 9.)
↑ The Prime Database: 607095*2^176311-1 (angol nyelven). primes.utm.edu. (Hozzáférés: 2017. január 9.)
↑ The Prime Database: 48047305725*2^172403-1 (angol nyelven). primes.utm.edu. (Hozzáférés: 2017. január 9.)
↑ The Prime Database: 137211941292195*2^171960-1 (angol nyelven). primes.utm.edu. (Hozzáférés: 2017. január 9.)

Kapcsolódó szócikkek

Biztonságos prímek
Cunningham-lánc

Sablon:Prímszámok osztályozása m v sz Prímszámok osztályozása
Képlet alapján	Fermat (2^2ⁿ + 1) Mersenne (2^p − 1) Dupla Mersenne (2^{2^p−1} − 1) Wagstaff (2^p + 1)/3 Proth (k·2ⁿ + 1) Faktoriális (n! ± 1) Primoriális (p_n# ± 1) Eukleidész (p_n# + 1) Pitagoraszi (4n + 1) Pierpont (2^u·3^v + 1) Kvartikus prímek (x⁴ + y⁴) Solinas (2^a ± 2^b ± 1) Cullen (n·2ⁿ + 1) Woodall (n·2ⁿ − 1) Köbös (x³ − y³)/(x − y) Carol (2ⁿ − 1)² − 2 Kynea (2ⁿ + 1)² − 2 Leyland (x^y + y^x) Szábit (3·2ⁿ ± 1) Mills (floor(A^3ⁿ))
Számsorozat alapján	Fibonacci Lucas Pell Newman–Shanks–Williams Perrin Partíciók Bell Motzkin
Tulajdonság alapján	Wieferich (pár) Wall–Szun–Szun Wolstenholme Wilson Szerencsés Fortunátus Ramanujan Pillai Regular Erős Stern Szuperszinguláris (elliptikus) Szuperszinguláris (holdfény-elmélet) Jó Szuper Higgs Erősen kotóciens
Számrendszerfüggő	Boldog Diéder Palindrom Mírp Repunit (10ⁿ − 1)/9 Permutálható Körkörös Csonkolható Középpontosan tükrös Minimális Gyenge Full reptend Unikális Primeval Önös Smarandache–Wellin
Mintázatok	Iker (p, p + 2) Ikerprímlánc (n − 1, n + 1, 2n − 1, 2n + 1, …) Prímhármas (p, p + 2 vagy p + 4, p + 6) Prímnégyes (p, p + 2, p + 6, p + 8) prím n−es Unokatestvér (p, p + 4) Szexi (p, p + 6) Chen Sophie Germain (p, 2p + 1) Cunningham-lánc (p, 2p ± 1, …) Biztonságos (p, (p − 1)/2) Számtani sorozatban (p + a·n, n = 0, 1, …) Kiegyensúlyozott (egymást követő p − n, p, p + n)
Méret alapján	Titáni (1000+ számjegy) Gigantikus (10 000+) Mega (1 000 000+) Ismert legnagyobb
Komplex számok	Eisenstein-prím Gauss-prím
Összetett számok	Álprím Erős álprím Majdnem prím Félprím Interprím
Kapcsolódó fogalmak	Valószínű prím Ipari szintű prím Illegális prímszám Prímszámképlet Prímhézag
Az első 100 prím	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541
Prímszámok listája