Sophie Germain-prím
A számelméletben Sophie Germain-prímnek nevezzük azokat a p prímszámokat, amelyekre 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 × 21290000 − 1 | 388342 | 2016. február | Scott Brown: PrimeGrid [1] |
18543637900515 × 2666667 − 1 | 200701 | 2012. április | Philipp Bliedung: elosztott PrimeGrid kereséssel, valamint TwinGen és LLR[2] használatával |
183027 × 2265440 − 1 | 79911 | 2010. március | Tom Wu: LLR használatával[3] |
648621027630345 × 2253824 − 1 és 620366307356565 × 2253824 − 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 × 2176311 − 1 | 53081 | 2009. szeptember | Tom Wu[6] |
48047305725 × 2172403 − 1 | 51910 | 2007. január | David Underbakke: TwinGen és LLR használatával[7] |
137211941292195 × 2171960 − 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 -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×21290000 - 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
![]() | Ez a matematikai tárgyú lap egyelőre csonk (erősen hiányos). Segíts te is, hogy igazi szócikk lehessen belőle! |