de.wikipedia.org

Schwache Primzahl – Wikipedia

Schwache Primzahlen (engl. Weakly Prime Numbers oder auch Digitally Delicate Prime[1]) sind Primzahlen, die bei Modifikation des Wertes von genau einer ihrer Dezimalstellen immer ihre Primzahl-Eigenschaft verlieren.

Als schwache Primzahlen (engl. Weak Prime) werden aber im Gegensatz zu starken Primzahlen (engl. Strong Prime) zur Schlüsselgenerierung in asymmetrischen Verschlüsselungsverfahren ungeeignete Primzahlen bezeichnet.

  • Die Primzahl {\displaystyle p=294001} ist eine schwache Primzahl, da
Wenn man eine einzige der sechs Dezimalstellen modifiziert, erhält man ausschließlich zusammengesetzte Zahlen, welche keine Primzahlen mehr sind:
094001, 194001, 294001, 394001, 494001, 594001, 694001, 794001, 894001, 994001,
204001, 214001, 224001, 234001, 244001, 254001, 264001, 274001, 284001, 294001
290001, 291001, 292001, 293001, 294001, 295001, 296001, 297001, 298001, 299001,
294001, 294101, 294201, 294301, 294401, 294501, 294601, 294701, 294801, 294901,
294001, 294011, 294021, 294031, 294041, 294051, 294061, 294071, 294081, 294091,
294000, 294001, 294002, 294003, 294004, 294005, 294006, 294007, 294008, 294009
Insgesamt sind in diesem Fall {\displaystyle (10-1)\cdot 6=54} Zahlen zu prüfen, ob sie zusammengesetzte Zahlen sind.
294001, 505447, 584141, 604171, 971767, 1062599, 1282529, 1524181, 2017963, 2474431,
2690201, 3085553, 3326489, 4393139, 5152507, 5564453, 5575259, 6173731, 6191371,
6236179, 6463267, 6712591, 7204777, 7469789, 7469797, … (Folge A050249 in OEIS)
  • Die größte momentan bekannte schwache Primzahl (Stand: 10. Dezember 2018) wurde im März 2007 von Jens Kruse Andersen entdeckt.[2]
Sie lautet:
{\displaystyle {\frac {17\cdot (10^{1000}-1)}{99}}+2168\ 6652=1717\ldots 1717\ 3885\ 8369}.
Diese Zahl beginnt mit 496 Mal einer {\displaystyle 17} und wird durch die Folge {\displaystyle 3885\ 8369} abgeschlossen. Sie besteht aus insgesamt {\displaystyle 1000} Stellen.
Beweis: siehe[3] von Terence Tao aus dem Jahr 2011.

Obiger Abschnitt behandelte schwache Primzahlen im Dezimalsystem, also zur Basis {\displaystyle b=10}.

Eine Primzahl {\displaystyle p\in \mathbb {P} } ist eine schwache Primzahl zur Basis {\displaystyle b}, wenn sie geschrieben zur Basis {\displaystyle b} bei Änderung einer beliebigen einzelnen Ziffer {\displaystyle d_{k}} (mit der Wertigkeit {\displaystyle b^{k}}) mit {\displaystyle 0\leq k\leq \lfloor \log _{b}{p}\rfloor } in eine andere Ziffer {\displaystyle d_{k}'} mit {\displaystyle d_{k}'\neq d_{k}} und {\displaystyle 0\leq d_{k}'<b} immer ihre Primzahl-Eigenschaft verliert.

Da {\displaystyle p} in der Basis {\displaystyle b} aus {\displaystyle \lfloor \log _{b}{p}\rfloor +1} Ziffern besteht, sind dazu {\displaystyle b\cdot \lfloor \log _{b}{p}\rfloor } Zahlen zu testen.

Wenn man eine einzige der drei Ziffern in der Basis {\displaystyle b=7} verändert, erhält man ausschließlich zusammengesetzte Zahlen, die keine Primzahlen mehr sind:
0367, 1367, 2367, 3367, 4367, 5367, 6367,
4067, 4167, 4267, 4367, 4467, 4567, 4667,
4307, 4317, 4327, 4337, 4347, 4357, 4367.
Insgesamt erhält man in obiger Liste {\displaystyle 6\cdot 3=24} zusammengesetzte Zahlen.
Stellvertretend für alle obigen 24 Zahlen wird hier die Zahl {\displaystyle 433_{7}} auf ihre Primalität geprüft:
{\displaystyle 433_{7}={\underline {4}}\cdot 7^{2}+{\underline {3}}\cdot 7^{1}+{\underline {3}}\cdot 7^{0}=196+21+3=220\ \not \in \mathbb {P} } ist keine Primzahl.
Analog funktioniert die Überprüfung aller anderen 23 obigen Zahlen.

Die folgende Tabelle gibt die kleinsten schwachen Primzahlen zur Basis {\displaystyle 2\leq b\leq 16} an (Folge A186995 in OEIS): [4]

Basis
{\displaystyle b} 		schwache Primzahlen zur Basis {\displaystyle b} Umrechnung dieser Primzahl ins Dezimalsystem
2 {\displaystyle 1111111_{2}} {\displaystyle \!{\underline {1}}\cdot 2^{6}+{\underline {1}}\cdot 2^{5}+{\underline {1}}\cdot 2^{4}+{\underline {1}}\cdot 2^{3}+{\underline {1}}\cdot 2^{2}+{\underline {1}}\cdot 2^{1}+{\underline {1}}\cdot 2^{0}=64+32+16+8+4+2+1=127}
3 {\displaystyle 2_{3}} {\displaystyle {\underline {2}}\cdot 3^{0}=2}
4 {\displaystyle 11311_{4}} {\displaystyle {\underline {1}}\cdot 4^{4}+{\underline {1}}\cdot 4^{3}+{\underline {3}}\cdot 4^{2}+{\underline {1}}\cdot 4^{1}+{\underline {1}}\cdot 4^{0}=256+64+48+4+1=373}
5 {\displaystyle 313_{5}} {\displaystyle {\underline {3}}\cdot 5^{2}+{\underline {1}}\cdot 5^{1}+{\underline {3}}\cdot 5^{0}=75+5+3=83}
6 {\displaystyle 334155_{6}} {\displaystyle {\underline {3}}\cdot 6^{5}+{\underline {3}}\cdot 6^{4}+{\underline {4}}\cdot 6^{3}+{\underline {1}}\cdot 6^{2}+{\underline {5}}\cdot 6^{1}+{\underline {5}}\cdot 6^{0}=23328+3888+864+36+30+5=28151}
7 {\displaystyle 436_{7}} {\displaystyle {\underline {4}}\cdot 7^{2}+{\underline {3}}\cdot 7^{1}+{\underline {6}}\cdot 7^{0}=196+21+6=223}
8 {\displaystyle 14103_{8}} {\displaystyle \!{\underline {1}}\cdot 8^{4}+{\underline {4}}\cdot 8^{3}+{\underline {1}}\cdot 8^{2}+{\underline {0}}\cdot 8^{1}+{\underline {3}}\cdot 8^{0}=4096+2048+64+0+3=6211}
9 {\displaystyle 3738_{9}} {\displaystyle {\underline {3}}\cdot 9^{3}+{\underline {7}}\cdot 9^{2}+{\underline {3}}\cdot 9^{1}+{\underline {8}}\cdot 9^{0}=2187+567+27+8=2789}
10 {\displaystyle 294001_{10}} {\displaystyle {\underline {2}}\cdot 10^{5}+{\underline {9}}\cdot 10^{4}+{\underline {4}}\cdot 10^{3}+{\underline {0}}\cdot 10^{2}+{\underline {0}}\cdot 10^{1}+{\underline {1}}\cdot 10^{0}=200000+90000+4000+0+0+1=294001}
11 {\displaystyle 2573_{11}} {\displaystyle \!{\underline {2}}\cdot 11^{3}+{\underline {5}}\cdot 11^{2}+{\underline {7}}\cdot 11^{1}+{\underline {3}}\cdot 11^{0}=2662+605+77+3=3347}
12 {\displaystyle \mathrm {6B8AB77_{12}} } {\displaystyle {\underline {6}}\cdot 12^{6}+{\underline {11}}\cdot 12^{5}+{\underline {8}}\cdot 12^{4}+{\underline {10}}\cdot 12^{3}+{\underline {11}}\cdot 12^{2}+{\underline {7}}\cdot 12^{1}+{\underline {7}}\cdot 12^{0}=17915904+2737152+165888+17280+1584+84+7=20837899}
13 {\displaystyle 2216_{13}} {\displaystyle {\underline {2}}\cdot 13^{3}+{\underline {2}}\cdot 13^{2}+{\underline {1}}\cdot 13^{1}+{\underline {6}}\cdot 13^{0}=4394+338+13+6=4751}
14 {\displaystyle \mathrm {C371CD_{14}} } {\displaystyle \!{\underline {12}}\cdot 14^{5}+{\underline {3}}\cdot 14^{4}+{\underline {7}}\cdot 14^{3}+{\underline {1}}\cdot 14^{2}+{\underline {12}}\cdot 14^{1}+{\underline {13}}\cdot 14^{0}=6453888+115248+19208+196+168+13=6588721}
15 {\displaystyle \mathrm {9880E_{15}} } {\displaystyle {\underline {9}}\cdot 15^{4}+{\underline {8}}\cdot 15^{3}+{\underline {8}}\cdot 15^{2}+{\underline {0}}\cdot 15^{1}+{\underline {14}}\cdot 15^{0}=455625+27000+1800+0+14=484439}
16 {\displaystyle \mathrm {D2A45_{16}} } {\displaystyle {\underline {13}}\cdot 16^{4}+{\underline {2}}\cdot 16^{3}+{\underline {10}}\cdot 16^{2}+{\underline {4}}\cdot 16^{1}+{\underline {5}}\cdot 16^{0}=851968+8192+2560+64+5=862789}
Beweis: siehe[3] von Terence Tao aus dem Jahr 2011.

Ein ähnliches Konstrukt stellen die trunkierbaren Primzahlen (vom englischen truncatable prime) dar. Von diesen Primzahlen lassen sich beliebig viele Stellen abtrennen, ohne dass deren Primeigenschaft verloren ginge:[5]

  • Linkstrunkierbare Primzahlen (Left-truncatable primes) (Folge A024785 in OEIS), z. B. 1367 – 367, 67 und 7 wären ebenfalls prim.
  • Rechtstrunkierbare Primzahlen (Right-truncatable primes) (Folge A024770 in OEIS), z. B. 3739 – 373, 37 und 3 wären ebenfalls prim.
  • Beidseitig trunkierbare Primzahlen (Two-sided primes) (Folge A020994 in OEIS) – in der strengen Definition der beidseitigen Ziffernabtrennbarkeit existieren nur 15 Primzahlen mit dieser Eigenschaft:
2, 3, 5, 7, 23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797, 739397

Es gibt auch eine Kombinationsmöglichkeit: Schwache trunkierbare Primzahlen (Digitally delicate truncatable primes) (Folge A347424 in OEIS), beginnend mit: 7810223, 19579907, 909001523, 984960937, 78406036607, ... welche beide Kriterien erfüllen.

  1. ↑ N. J. A. Sloane: Weakly prime numbers (changing any one decimal digit always produces a composite number). Also called digitally delicate primes. OEIS, abgerufen am 10. Dezember 2018.
  2. ↑ Weakly Primes kommentar. primepuzzles.net, 2012, abgerufen am 10. Dezember 2018.
  3. ↑ a b Terence Tao: A remark on primality testing and decimal expansions. In: Journal of the Australian Mathematical Society. Band 91, Nr. 3, 2011, S. 505—413, doi:10.1017/S1446788712000043, arxiv:0802.3361.
  4. ↑ Schwache Primzahlen und das Unärsystem sind unvereinbar. Schwache Primzahlen arbeiten explizit nur mit Ziffern, die kleiner als die Basis sind {\displaystyle 0\leq d_{k}<b}. Dieses ist essentiell für die Betrachtung von schwachen Primzahlen und ist im Unärsystem prinzipbedingt verletzt. Lässt man Ziffern {\displaystyle d_{k}\geq b} zu, gibt es keine schwachen Primzahlen.
  5. ↑ Eric W. Weisstein: Truncatable Prime. In: MathWorld (englisch).
formelbasiert

Carol ((2n − 1)2 − 2) | Doppelte Mersenne (22p − 1 − 1) | Fakultät (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 | Perrin

eigenschaftsbasiert

Elitär | Fortunate | Gut | Glücklich | Higgs | Hochkototient | Isoliert | Pillai | Ramanujan | Regulär | Stark | Stern | Wall–Sun–Sun | Wieferich | Wilson

basis­abhängig

Belphegor | Champernowne | Dihedral | Einzigartig | Fröhlich | Keith | Lange | Minimal | Mirp | Permutierbar | Primeval | Palindrom | Repunit-Primzahl ((10n − 1)/9) | Schwach | Smarandache–Wellin | Strobogrammatisch | Tetradisch | Trunkierbar | Zirkular

basierend 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 Größe

Titanisch (1.000+ Stellen) | Gigantisch (10.000+ Stellen) | Mega (1.000.000+ Stellen) | Beva (1.000.000.000+ Stellen)