In der Zahlentheorie ist eine sichere Primzahl von englisch safe prime eine Primzahl q P displaystyle q in mathbb P der Form q 2 p 1 displaystyle q 2p 1 wobei p P displaystyle p in mathbb P ebenfalls prim sein muss Die dazugehorige Primzahl p displaystyle p heisst Sophie Germain Primzahl Inhaltsverzeichnis 1 Namensgebung 2 Beispiele 3 Eigenschaften 4 Weblinks 5 EinzelnachweiseNamensgebung BearbeitenDiese Primzahlen heissen sicher weil sie mit starken Primzahlen verwandt sind Starke Primzahlen q N displaystyle q in mathbb N nbsp sind Primzahlen wenn in ihrer kryptologischen Definition sowohl q 1 displaystyle q 1 nbsp als auch q 1 displaystyle q 1 nbsp grosse Primfaktoren im Sinne von viel grosser kann ein Primfaktor nicht werden als knapp halb so gross wie die Zahl selber besitzen Fur sichere Primzahlen q 2 p 1 displaystyle q 2p 1 nbsp hat die Zahl q 1 2 p displaystyle q 1 2p nbsp den grossen Primfaktor p displaystyle p nbsp weshalb die sichere Primzahl q displaystyle q nbsp zumindest ein Kriterium fur starke Primzahlen erfullt Die Dauer von Methoden die Zahlen faktorisieren welche q displaystyle q nbsp als Primfaktor haben hangt zum Teil von der Grosse des Primfaktors von q 1 displaystyle q 1 nbsp ab wie zum Beispiel bei der Pollard p 1 Methode Sichere Primzahlen spielen auch in der Kryptologie eine wichtige Rolle 1 Beispiele BearbeitenDie kleinsten sicheren Primzahlen sind die folgenden 5 7 11 23 47 59 83 107 167 179 227 263 347 359 383 467 479 503 563 587 719 839 863 887 983 1019 1187 1283 1307 1319 1367 1439 1487 1523 1619 1823 1907 2027 2039 2063 2099 2207 2447 2459 2579 2819 2879 2903 Folge A005385 in OEIS dd Der folgenden Liste kann man die 10 grossten bekannten sicheren Primzahlen entnehmen Samtliche Entdecker dieser Primzahlen sind Teilnehmer des PrimeGrid Projektes Rang Rang in Primzahl liste a 2 3 Primzahl p displaystyle p nbsp Dezimalstellen von p displaystyle p nbsp Entdeckungsdatum Entdecker Quelle1 1958 2618163402417 2 1290001 1 displaystyle 2618163402417 cdot 2 1290001 1 nbsp 388342 displaystyle 388342 nbsp 29 Februar 2016 Scott Brown USA 4 2 2001 18543637900515 2 666668 1 displaystyle 18543637900515 cdot 2 666668 1 nbsp 200701 displaystyle 200701 nbsp 4 oder 9 April 2012 Lee Blyth AUS 5 3 2018 183027 2 265441 1 displaystyle 183027 cdot 2 265441 1 nbsp 79911 displaystyle 79911 nbsp 22 Marz 2010 Tom Wu 6 4 2027 648621027630345 2 253825 1 displaystyle 648621027630345 cdot 2 253825 1 nbsp 76424 displaystyle 76424 nbsp 18 November 2009 Zoltan Jarai Gabor Farkas Timea Csajbok Janos Kasza Antal Jarai 7 5 2028 620366307356565 2 253825 1 displaystyle 620366307356565 cdot 2 253825 1 nbsp 76424 displaystyle 76424 nbsp 2 November 2009 Zoltan Jarai Gabor Farkas Timea Csajbok Janos Kasza Antal Jarai 8 6 2048 1068669447 2 211088 1 displaystyle 1068669447 cdot 2 211088 1 nbsp 63553 displaystyle 63553 nbsp 17 Mai 2020 Michael Kwok 9 7 2055 99064503957 2 200009 1 displaystyle 99064503957 cdot 2 200009 1 nbsp 60220 displaystyle 60220 nbsp 1 April 2016 S Urushihata 10 8 2072 12443794755 2 184516 1 displaystyle 12443794755 cdot 2 184516 1 nbsp 55555 displaystyle 55555 nbsp 9 September 2021 Serge Batalov 11 9 2073 21749869755 2 184515 1 displaystyle 21749869755 cdot 2 184515 1 nbsp 55555 displaystyle 55555 nbsp 9 September 2021 Serge Batalov 12 10 2074 14901867165 2 184515 1 displaystyle 14901867165 cdot 2 184515 1 nbsp 55555 displaystyle 55555 nbsp 9 September 2021 Serge Batalov 13 a Stand 18 Dezember 2021 der Rang verrat nur an welcher Stelle diese Primzahlen in dieser Primzahlliste auftauchenEigenschaften BearbeitenMit Ausnahme der sicheren Primzahl q 7 displaystyle q 7 nbsp haben alle sicheren Primzahlen die Form q 6 k 5 displaystyle q 6k 5 nbsp mit einer ganzen Zahl k N displaystyle k in mathbb N nbsp Mit anderen Worten q 5 mod 6 displaystyle q equiv 5 pmod 6 nbsp Beweis Alle Zahlen der Restklassen n 0 mod 6 displaystyle n equiv 0 pmod 6 nbsp oder n 2 mod 6 displaystyle n equiv 2 pmod 6 nbsp oder n 4 mod 6 displaystyle n equiv 4 pmod 6 nbsp sind gerade und demnach durch 2 displaystyle 2 nbsp teilbar Die Sophie Germain Primzahl p 2 displaystyle p 2 nbsp fuhrt auf die sichere Primzahl q 2 2 1 5 displaystyle q 2 cdot 2 1 5 nbsp und diese erfullt die Bedingung q 5 mod 6 displaystyle q equiv 5 pmod 6 nbsp Alle Zahlen der Restklassen n 0 mod 6 displaystyle n equiv 0 pmod 6 nbsp oder n 3 mod 6 displaystyle n equiv 3 pmod 6 nbsp sind durch 3 displaystyle 3 nbsp teilbar Die Sophie Germain Primzahl p 3 displaystyle p 3 nbsp fuhrt auf die sichere Primzahl q 2 3 1 7 displaystyle q 2 cdot 3 1 7 nbsp und diese erfullt die Bedingung q 5 mod 6 displaystyle q equiv 5 pmod 6 nbsp nicht ist aber aus dieser Behauptung ohnehin ausgenommen Zwar existieren Primzahlen in der Restklasse p 1 mod 6 displaystyle p equiv 1 pmod 6 nbsp jedoch wurde man dadurch wegen q 2 p 1 2 6 n 1 1 12 n 3 3 4 n 1 displaystyle q 2p 1 2 cdot 6n 1 1 12n 3 3 cdot 4n 1 nbsp sichere Primzahlen erhalten die durch 3 displaystyle 3 nbsp teilbar waren und somit keine Primzahlen sein konnen Als einzige Sechser Restklasse fur sichere Primzahlen q displaystyle q nbsp bleibt somit die Restklasse q 5 mod 6 displaystyle q equiv 5 pmod 6 nbsp ubrig displaystyle Box nbsp dd dd Mit Ausnahme der sicheren Primzahl q 5 displaystyle q 5 nbsp haben alle sicheren Primzahlen die Form q 4 k 3 displaystyle q 4k 3 nbsp mit einer ganzen Zahl k N displaystyle k in mathbb N nbsp Mit anderen Worten q 3 mod 4 displaystyle q equiv 3 pmod 4 nbsp Beweis Bis auf die erste Sophie Germain Primzahl p 2 displaystyle p 2 nbsp welche auf die sichere Primzahl q 2 2 1 5 displaystyle q 2 cdot 2 1 5 nbsp fuhrt und fur die diese Behauptung nicht stimmt sind alle anderen Primzahlen ungerade haben also die Form p 2 n 1 displaystyle p 2n 1 nbsp mit n N displaystyle n in mathbb N nbsp Jede sichere Primzahl hat somit die Form q 2 p 1 2 2 n 1 1 4 n 3 displaystyle q 2p 1 2 2n 1 1 4n 3 nbsp was zu zeigen war displaystyle Box nbsp dd dd Mit Ausnahme der sicheren Primzahlen q 5 displaystyle q 5 nbsp und q 7 displaystyle q 7 nbsp haben alle sicheren Primzahlen die Form q 12 k 11 displaystyle q 12k 11 nbsp mit einer ganzen Zahl k N displaystyle k in mathbb N nbsp Mit anderen Worten q 11 mod 12 displaystyle q equiv 11 pmod 12 nbsp Beweis Alle Sophie Germain Primzahlen p gt 3 displaystyle p gt 3 nbsp fuhren auf die sicheren Primzahlen q 2 p 1 gt 2 3 1 7 displaystyle q 2p 1 gt 2 cdot 3 1 7 nbsp und haben die Form p 6 k 5 displaystyle p 6k 5 nbsp siehe Beweis Somit gilt fur die sichere Primzahl q 2 p 1 2 6 k 5 1 12 k 11 displaystyle q 2p 1 2 cdot 6k 5 1 12k 11 nbsp was zu zeigen war displaystyle Box nbsp dd dd Fur alle sicheren Primzahlen q gt 7 displaystyle q gt 7 nbsp gilt 3 displaystyle 3 nbsp ist ein quadratischer Rest modulo q displaystyle q nbsp Beweis Sichere Primzahlen haben die Form q 2 p 1 displaystyle q 2p 1 nbsp mit p P displaystyle p in mathbb P nbsp Wegen der Voraussetzung q gt 7 2 p 1 displaystyle q gt 7 2p 1 nbsp ist p gt 3 displaystyle p gt 3 nbsp Ungerade Primzahlen p gt 3 displaystyle p gt 3 nbsp erfullen aber die Kongruenz p 1 mod 6 displaystyle p equiv 1 pmod 6 nbsp oder p 5 mod 6 displaystyle p equiv 5 pmod 6 nbsp weil alle ungeraden Zahlen der Form n 3 mod 6 displaystyle n equiv 3 pmod 6 nbsp durch 3 displaystyle 3 nbsp teilbar sind Primzahlen der Form p 1 mod 6 displaystyle p equiv 1 pmod 6 nbsp konnen keine Sophie Germain Primzahlen sein weil dann q 2 p 1 2 1 1 3 mod 6 displaystyle q 2p 1 equiv 2 cdot 1 1 3 pmod 6 nbsp durch 3 displaystyle 3 nbsp teilbar ware und somit keine sicheren Primzahlen sind Es bleibt nur p 5 mod 6 displaystyle p equiv 5 pmod 6 nbsp ubrig also ist p 5 mod 12 displaystyle p equiv 5 pmod 12 nbsp oder p 5 6 11 mod 12 displaystyle p equiv 5 6 11 pmod 12 nbsp Somit ist in beiden Fallen q 2 p 1 2 5 1 2 11 1 23 11 mod 12 displaystyle q 2p 1 equiv 2 cdot 5 1 equiv 2 cdot 11 1 23 equiv 11 pmod 12 nbsp Es gibt aber den mathematischen Satz dass 3 displaystyle 3 nbsp ein quadratischer Rest modulo q displaystyle q nbsp ist genau dann wenn q 1 mod 12 displaystyle q equiv 1 pmod 12 nbsp oder q 1 11 mod 12 displaystyle q equiv 1 equiv 11 pmod 12 nbsp ist 14 Somit ist 3 displaystyle 3 nbsp ein quadratischer Rest modulo q displaystyle q nbsp was zu zeigen war displaystyle Box nbsp dd dd Fur alle sicheren Primzahlen q gt 7 displaystyle q gt 7 nbsp gilt q displaystyle q nbsp teilt 3 q 1 2 1 displaystyle 3 frac q 1 2 1 nbsp Beweis Weil 3 displaystyle 3 nbsp ein quadratischer Rest modulo q displaystyle q nbsp ist gilt folgende Kongruenz 3 q 1 2 1 mod q displaystyle 3 frac q 1 2 equiv 1 pmod q nbsp Daraus folgt direkt dass q displaystyle q nbsp ein Teiler von 3 q 1 2 1 displaystyle 3 frac q 1 2 1 nbsp ist displaystyle Box nbsp dd dd Sei q 7 mod 8 displaystyle q equiv 7 pmod 8 nbsp eine sichere Primzahl Dann gilt q displaystyle q nbsp ist Teiler derjenigen Mersenne Zahl dessen Exponent die dazugehorige Sophie Germain Primzahl ist Mit anderen Worten q displaystyle q nbsp teilt M p displaystyle M p nbsp mit p q 1 2 displaystyle p frac q 1 2 nbsp dd siehe auch Teilbarkeitseigenschaften der Mersenne Zahlen Beispiel Es ist q 23 7 mod 8 displaystyle q 23 equiv 7 pmod 8 nbsp Dann ist die dazugehorige Sophie Germain Primzahl p 23 1 2 11 displaystyle p frac 23 1 2 11 nbsp Tatsachlich ist q 23 displaystyle q 23 nbsp Teiler von M 11 2 11 1 2048 1 2047 23 89 displaystyle M 11 2 11 1 2048 1 2047 23 cdot 89 nbsp dd dd Es gibt mit Ausnahme der Primzahl q 5 displaystyle q 5 nbsp keine Fermat Primzahlen welche gleichzeitig sichere Primzahlen sind Beweis Fermat Primzahlen sind von der Form F q 2 n 1 displaystyle F q 2 n 1 nbsp Daraus folgt dass F 1 2 q 1 2 p 2 n 1 displaystyle frac F 1 2 frac q 1 2 p 2 n 1 nbsp eine Zweierpotenz aber keine Sophie Germain Primzahl ist ausser fur p 2 1 displaystyle p 2 1 nbsp und somit fur q 2 2 1 5 displaystyle q 2 cdot 2 1 5 nbsp Somit kann die Fermat Primzahl F displaystyle F nbsp keine sichere Zahl sein was zu beweisen war displaystyle Box nbsp dd dd Es gibt mit Ausnahme der Primzahl q 7 displaystyle q 7 nbsp keine Mersenne Primzahlen welche gleichzeitig sichere Primzahlen sind Beweis Weiter oben wurde bewiesen dass alle sicheren Primzahlen mit Ausnahme von q 7 displaystyle q 7 nbsp die Form q 6 k 2 5 6 k 2 1 1 6 k 1 displaystyle q 6k 2 5 6 k 2 1 1 6k 1 nbsp haben Mersenne Primzahlen sind von der Form p 2 m 1 displaystyle p 2 m 1 nbsp Somit musste 2 m 1 6 k 1 displaystyle 2 m 1 6k 1 nbsp sein und deswegen ware 2 m 6 k displaystyle 2 m 6k nbsp 2 m displaystyle 2 m nbsp ist aber niemals durch 6 displaystyle 6 nbsp teilbar woraus folgt dass niemals eine Mersenne Primzahl gleichzeitig eine sichere Primzahl sein darf mit Ausnahme von q 7 2 3 1 displaystyle q 7 2 3 1 nbsp displaystyle Box nbsp dd dd Jedes Folgenglied einer Cunningham Kette der ersten Art mit Ausnahme des ersten Gliedes einer solchen Kette ist eine sichere Primzahl Beweis Der Beweis liegt in der Definition solcher Cunningham Ketten a 0 p displaystyle a 0 p nbsp also eine Sophie Germain Primzahl alle weiteren Folgenglieder haben die Form a n 1 2 a n 1 displaystyle a n 1 2 cdot a n 1 nbsp und sind somit laut Definition sichere Primzahlen displaystyle Box nbsp dd dd Sei q displaystyle q nbsp eine sichere Primzahl der Form q 10 k 7 displaystyle q 10k 7 nbsp sie soll also mit 7 displaystyle 7 nbsp enden welche in einer Cunningham Kette vorkommt Dann gilt Die Zahl q displaystyle q nbsp beendet die Cunningham Kette sie ist also das letzte Folgenglied dieser Kette Beweis Das nachste Folgenglied dieser Kette ware 2 10 k 7 1 20 k 15 5 4 k 3 displaystyle 2 cdot 10k 7 1 20k 15 5 cdot 4k 3 nbsp und ware somit durch 5 displaystyle 5 nbsp teilbar und deswegen keine Primzahl mehr displaystyle Box nbsp dd dd Sei p P displaystyle p in mathbb P nbsp eine Primzahl Dann gilt 15 16 Ist p 1 mod 4 displaystyle p equiv 1 pmod 4 nbsp dann gilt q 2 p 1 displaystyle q 2p 1 nbsp ist eine sichere Primzahl genau dann wenn q 2 p 1 displaystyle q 2p 1 nbsp Teiler von 2 p 1 displaystyle 2 p 1 nbsp ist dd Ist p 3 mod 4 displaystyle p equiv 3 pmod 4 nbsp dann gilt q 2 p 1 displaystyle q 2p 1 nbsp ist eine sichere Primzahl genau dann wenn q 2 p 1 displaystyle q 2p 1 nbsp Teiler von 2 p 1 displaystyle 2 p 1 nbsp ist dd dd Weblinks BearbeitenEric W Weisstein Sophie Germain Prime In MathWorld englisch Safe Prime In PlanetMath englisch Einzelnachweise Bearbeiten Safe Prime In PlanetMath englisch Chris K Caldwell The Top Twenty Sophie Germain p Prime Pages abgerufen am 24 Juni 2018 Liste der grossten bekannten Primzahlen Abgerufen am 21 Juni 2018 englisch Sophie Germain Zahl 2618163402417 21290001 1 auf Prime Pages Sophie Germain Zahl 18543637900515 2666668 1 auf Prime Pages Sophie Germain Zahl 183027 2265441 1 auf Prime Pages Sophie Germain Zahl 648621027630345 2253825 1 auf Prime Pages Sophie Germain Zahl 620366307356565 2253825 1 auf Prime Pages Sophie Germain Zahl 1068669447 2211088 1 auf Prime Pages Sophie Germain Zahl 99064503957 2200009 1 auf Prime Pages Sophie Germain Zahl 12443794755 2184516 1 auf Prime Pages Sophie Germain Zahl 21749869755 2184515 1 auf Prime Pages Sophie Germain Zahl 14901867165 2184515 1 auf Prime Pages Dusan Djukic Quadratic Congruences Theorem 10c The IMO Compendium Group 2007 S 1 12 abgerufen am 17 Marz 2020 Chris K Caldwell Proof of a result of Euler and Lagrange on Mersenne Divisors Prime Pages abgerufen am 14 August 2019 Henri Lifchitz Generalization of Euler Lagrange theorem and new primality tests Abgerufen am 14 August 2019 V DPrimzahl mengenformelbasiert Carol 2n 1 2 2 Doppelte Mersenne 22p 1 1 Fakultat n 1 Fermat 22n 1 Kubisch x3 y3 x y Kynea 2n 1 2 2 Leyland xy yx Mersenne 2p 1 Mills A3n Pierpont 2u 3v 1 Primorial pn 1 Proth k 2n 1 Pythagoreisch 4n 1 Quartisch x4 y4 Thabit 3 2n 1 Wagstaff 2p 1 3 Williams b 1 bn 1 Woodall n 2n 1 Primzahlfolgen Bell Fibonacci Lucas Motzkin Pell Perrineigenschaftsbasiert Elitar Fortunate Gut Glucklich Higgs Hochkototient Isoliert Pillai Ramanujan Regular Stark Stern Wall Sun Sun Wieferich Wilsonbasis abhangig Belphegor Champernowne Dihedral Einzigartig Frohlich Keith Lange Minimal Mirp Permutierbar Primeval Palindrom Repunit Primzahl 10n 1 9 Schwach Smarandache Wellin Strobogrammatisch Tetradisch Trunkierbar Zirkularbasierend auf Tupel Ausbalanciert p n p p n Chen Cousin p p 4 Cunningham p 2p 1 Drilling p p 2 oder p 4 p 6 Konstellation Sexy p p 6 Sichere p p 1 2 Sophie Germain p 2p 1 Vierling p p 2 p 6 p 8 Zwilling p p 2 Zwillings Bi Kette n 1 2n 1 nach Grosse Titanisch 1 000 Stellen Gigantisch 10 000 Stellen Mega 1 000 000 Stellen Beva 1 000 000 000 Stellen Abgerufen von https de wikipedia org w index php title Sichere Primzahl amp oldid 229189089
