Schwache Primzahl

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.

Beispiele

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

• Die ersten schwachen Primzahlen (zur Basis 10) lauten:

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.

Eigenschaften

• Um festzustellen, ob eine ${\displaystyle k}$-stellige Primzahl eine schwache Primzahl ist, muss man ${\displaystyle 9\cdot k}$ Zahlen kontrollieren, ob sie zusammengesetzt sind oder nicht. Nur wenn alle ${\displaystyle 9\cdot k}$ Zahlen zusammengesetzt sind, ist die ${\displaystyle k}$-stellige Primzahl tatsächlich eine schwache Primzahl (siehe obiges Beispiel).
• Es gibt unendlich viele schwache Primzahlen und ihre Dichte unter den Primzahlen ist echt größer 0.

Beweis: siehe^[3] von Terence Tao aus dem Jahr 2011.

Schwache Primzahlen in beliebigen Zahlensystemen

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.

Beispiele von schwachen Primzahlen in anderen Zahlensystemen

• Die Primzahl ${\displaystyle p=436_{7}={\underline {4}}\cdot 7^{2}+{\underline {3}}\cdot 7^{1}+{\underline {6}}\cdot 7^{0}=196+21+6=223}$ ist eine schwache Primzahl zur Basis ${\displaystyle b=7}$, weil gilt:

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:

036₇, 136₇, 236₇, 336₇, 436₇, 536₇, 636₇,

406₇, 416₇, 426₇, 436₇, 446₇, 456₇, 466₇,

430₇, 431₇, 432₇, 433₇, 434₇, 435₇, 436₇.

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
002	${\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}$
003	${\displaystyle 2_{3}}$	${\displaystyle {\underline {2}}\cdot 3^{0}=2}$
004	${\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}$
005	${\displaystyle 313_{5}}$	${\displaystyle {\underline {3}}\cdot 5^{2}+{\underline {1}}\cdot 5^{1}+{\underline {3}}\cdot 5^{0}=75+5+3=83}$
006	${\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}$
007	${\displaystyle 436_{7}}$	${\displaystyle {\underline {4}}\cdot 7^{2}+{\underline {3}}\cdot 7^{1}+{\underline {6}}\cdot 7^{0}=196+21+6=223}$
008	${\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}$
009	${\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}$
010	${\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}$
011	${\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}$
012	${\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}$
013	${\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}$
014	${\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}$
015	${\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}$
016	${\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}$

Eigenschaften von schwachen Primzahlen in anderen Zahlensystemen

• Um festzustellen, ob eine ${\displaystyle k}$-stellige Primzahl eine schwache Primzahl zur Basis ${\displaystyle b}$ ist, muss man ${\displaystyle (b-1)\cdot k}$ Zahlen kontrollieren, ob sie zusammengesetzt sind oder nicht. Nur wenn alle ${\displaystyle (b-1)\cdot k}$ Zahlen zusammengesetzt sind, ist die ${\displaystyle k}$-stellige Primzahl tatsächlich eine schwache Primzahl zur Basis ${\displaystyle b}$.
• Sei ${\displaystyle b\in \mathbb {N} }$ eine Basis. Dann gibt es unendlich viele schwache Primzahlen zu dieser Basis ${\displaystyle b}$.

Beweis: siehe^[3] von Terence Tao aus dem Jahr 2011.

Ähnliche Konstrukte

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.

Weblinks

• Eric W. Weisstein: Weakly Prime. In: MathWorld (englisch).
• Weakly Primes auf Department of Mathematics der Missouri State University (englisch)

Einzelnachweise

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