„Sophie Germain-prím” változatai közötti eltérés

A Wikipédiából, a szabad enciklopédiából
[ellenőrzött változat][ellenőrzött változat]
Tartalom törölve Tartalom hozzáadva
Syp (vitalap | szerkesztései)
a Prímszámok kategória hozzáadva (a HotCattel)
LuCkY (vitalap | szerkesztései)
a formázás, kiegészítés
1. sor: 1. sor:
A [[számelmélet]]ben '''Sophie Germain-prím'''nek nevezzük azokat a ''p'' [[prímszámok]]at, amelyre 2''p'' + 1 szintén prímszám. Ezeket a [[szám]]okat a [[franciák|francia]] [[matematikus]]ról, [[Sophie Germain|Marie-Sophie Germain]]ről nevezték el. A Sophie Germain-prímből számított 2''p''+1 számot nevezzük [[Biztonságos prímek|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.
Azokat a ''p'' [[prímszámok]]at nevezzük '''Sophie Germain-prím'''nek, amelyre 2''p'' + 1 szintén prímszám.


Az első néhány Sophie Germain-prím (1000-nél kisebb):
Ezeket a [[szám]]okat a [[franciák|francia]] [[matematikus]]ról, [[Sophie Germain|Marie-Sophie Germain]]ről nevezték el.


:[[2 (szám)|2]], [[3 (szám)|3]], [[5 (szám)|5]], [[11 (szám)|11]], [[23 (szám)|23]], [[29 (szám)|29]], [[41 (szám)|41]], [[53 (szám)|53]], [[83 (szám)|83]], [[89 (szám)|89]], [[113 (szám)|113]], [[131 (szám)|131]], [[173 (szám)|173]], [[179 (szám)|179]], [[191 (szám)|191]], [[233 (szám)|233]], [[239 (szám)|239]], [[251 (szám)|251]], [[281 (szám)|281]], [[293 (szám)|293]], [[359 (szám)|359]], [[419 (szám)|419]], [[431 (szám)|431]], [[443 (szám)|443]], [[491 (szám)|491]], [[509 (szám)|509]], [[593 (szám)|593]], [[641 (szám)|641]], [[653 (szám)|653]], [[659 (szám)|659]], [[683 (szám)|683]], [[719 (szám)|719]], [[743 (szám)|743]], [[761 (szám)|761]], [[809 (szám)|809]], [[911 (szám)|911]], [[953 (szám)|953]] ... {{OEIS2C|id=A005384}}
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:
== Sophie Germain-prímek keresése ==
A ''PrimeGrid'', valamint ''Twin Prime Search'' [[Elosztott számítások|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 ''(2017 januári állapot)'':
<center>[[2 (szám)|2]], [[3 (szám)|3]], [[5 (szám)|5]], [[11 (szám)|11]], [[23 (szám)|23]], [[29 (szám)|29]], [[41 (szám)|41]], [[53 (szám)|53]], [[83 (szám)|83]], [[89 (szám)|89]], [[113 (szám)|113]], [[131 (szám)|131]], [[173 (szám)|173]], [[179 (szám)|179]], [[191 (szám)|191]], [[233 (szám)|233]], [[239 (szám)|239]], [[251 (szám)|251]], [[281 (szám)|281]], [[293 (szám)|293]], [[359 (szám)|359]], [[419 (szám)|419]], [[431 (szám)|431]], [[443 (szám)|443]], [[491 (szám)|491]], [[509 (szám)|509]], [[593 (szám)|593]], [[641 (szám)|641]], [[653 (szám)|653]], [[659 (szám)|659]], [[683 (szám)|683]], [[719 (szám)|719]], [[743 (szám)|743]], [[761 (szám)|761]], [[809 (szám)|809]], [[911 (szám)|911]], [[953 (szám)|953]], 1013, 1019, 1031, 1049, 1103, 1223, 1229, 1289, 1409, 1439, 1451, 1481, 1499, 1511, 1559...</center>


{| class="wikitable"
Az ismert legnagyobb Sophie Germain-prím 18&nbsp;543&nbsp;637&nbsp;900&nbsp;515&nbsp;&times;&nbsp;2<sup>666667</sup> ‒ 1
|-
! Szám !! Számjegyek száma !! Megtalálás ideje !! Megtaláló és módszere
|-
| 2618163402417 × 2<sup>1290000</sup> − 1 || align="right" | 388342 || 2016. február || Scott Brown: PrimeGrid <ref>{{cite web |url=http://primes.utm.edu/primes/page.php?id=121330 |title=The Prime Database: 2618163402417×2<sup>1290000</sup> - 1 |accessdate=2017-01-09 |publisher = primes.utm.edu|language = angol}}</ref>
|-
| 18543637900515 × 2<sup>666667</sup> − 1 || align="right" | 200701 || 2012. április || Philipp Bliedung: elosztott PrimeGrid kereséssel, valamint TwinGen és [[Lucas–Lehmer–Riesel test|LLR]] <ref>{{cite web|title=PrimeGrid’s Sophie Germain Prime Search|url=http://www.primegrid.com/download/SGS_666667.pdf|publisher=PrimeGrid|format=PDF|accessdate=2017-01-09}}</ref> használatával
|-
|183027 × 2<sup>265440</sup> − 1 || align="right" | 79911 || 2010. március || Tom Wu: LLR használatával<ref>{{cite web |url=http://primes.utm.edu/primes/page.php?id=92222 |title=The Prime Database: 183027*2^265440|accessdate=2017-01-09 |publisher = primes.utm.edu|language = angol}}</ref>
|-
|648621027630345 × 2<sup>253824</sup> − 1 és 620366307356565 × 2<sup>253824</sup> − 1 || align="right" | 76424 || 2009. november || Járai Zoltán, Farkas Gábor, Csajbók Tímea, Kasza János és Járai Antal<ref>{{cite web |url=http://primes.utm.edu/primes/page.php?id=90907 |title=The Prime Database: 648621027630345*2^253824-1|accessdate=2017-01-09 |publisher = primes.utm.edu|language = angol}}</ref><ref>{{cite web |url=http://primes.utm.edu/primes/page.php?id=90711 |title=The Prime Database: 620366307356565*2^253824-1|accessdate=2017-01-09 |publisher = primes.utm.edu|language = angol}}</ref>
|-
|607095 × 2<sup>176311</sup> − 1 || align="right" | 53081 || 2009. szeptember || Tom Wu<ref>{{cite web |url=http://primes.utm.edu/primes/page.php?id=89999 |title=The Prime Database: 607095*2^176311-1|accessdate=2017-01-09 |publisher = primes.utm.edu|language = angol}}</ref>
|-
|48047305725 × 2<sup>172403</sup> − 1 || align="right" | 51910 || 2007. január || David Underbakke: TwinGen és LLR használatával<ref>{{cite web |url=http://primes.utm.edu/primes/page.php?id=79261 |title=The Prime Database: 48047305725*2^172403-1|accessdate=2017-01-09 |publisher = primes.utm.edu|language = angol}}</ref>
|-
|137211941292195 × 2<sup>171960</sup> − 1 || align="right" | 51780 || 2006. május || Járai Zoltán, Farkas Gábor, Csajbók Tímea, Kasza János és Járai Antal<ref>{{cite web |url=http://primes.utm.edu/primes/page.php?id=77705 |title=The Prime Database: 137211941292195*2^171960-1|accessdate=2017-01-09 |publisher = primes.utm.edu|language = angol}}</ref>
|-
|}

== Alkalmazása ==
Jelentős szerepe van a különböző kriptográfiai megoldásokban, ahol <math>1,846,389,521,368 + 11^{600}</math>-nél nagyobb számokra, ''erős'' prímekre van szükség. Mivel a ''p'' Sophie Germain-prímből származtatható 2''p'' + 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 algoritmus]]nál, hogy ne lehessen bizonyos faktorizáló eljárásokkal, mint például a ''Pollard-ró algoritmussal'' feltörni.

== Jegyzetek ==
{{jegyzetek}}


==Kapcsolódó szócikkek==
==Kapcsolódó szócikkek==

A lap 2017. január 11., 11:59-kori változata

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 ... OEISA005384

Sophie Germain-prímek keresése

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 (2017 januári á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-ró algoritmussal feltörni.

Jegyzetek

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

Kapcsolódó szócikkek