Schwache Primzahl

Schwache Primzahlen (engl. Weakly Prime Numbers oder auch Digitally Delicate Prime) 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 $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 $(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, … (Vorlage:OEIS)

• Die größte momentan bekannte schwache Primzahl (Stand: 10. Dezember 2018) wurde im März 2007 von Jens Kruse Andersen entdeckt.

Sie lautet:

$\frac{17\cdot (10^{1000}-1)}{99}+21686652=1717\dots 171738858369$.

Diese Zahl beginnt mit 496 Mal einer $17$ und wird durch die Folge $38858369$ abgeschlossen. Sie besteht aus insgesamt $1000$ Stellen.

Eigenschaften

• Um festzustellen, ob eine $k$-stellige Primzahl eine schwache Primzahl ist, muss man $9\cdot k$ Zahlen kontrollieren, ob sie zusammengesetzt sind oder nicht. Nur wenn alle $9\cdot k$ Zahlen zusammengesetzt sind, ist die $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 von Terence Tao aus dem Jahr 2011.

Schwache Primzahlen in beliebigen Zahlensystemen

Obiger Abschnitt behandelte schwache Primzahlen im Dezimalsystem, also zur Basis $b=10$.

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

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

Beispiele von schwachen Primzahlen in anderen Zahlensystemen

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

Wenn man eine einzige der drei Ziffern in der Basis $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 $6\cdot 3=24$ zusammengesetzte Zahlen.

Stellvertretend für alle obigen 24 Zahlen wird hier die Zahl $433_7$ auf ihre Primalität geprüft:

$433_7=\underset{\_}{4}\cdot 7^2+\underset{\_}{3}\cdot 7^1+\underset{\_}{3}\cdot 7^0=196+21+3=220\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 $2\le b\le 16$ an (Vorlage:OEIS):

Basis $b$	schwache Primzahlen zur Basis $b$	Umrechnung dieser Primzahl ins Dezimalsystem
Vorlage:02	$1111111_2$	$\underset{\_}{1}\cdot 2^6+\underset{\_}{1}\cdot 2^5+\underset{\_}{1}\cdot 2^4+\underset{\_}{1}\cdot 2^3+\underset{\_}{1}\cdot 2^2+\underset{\_}{1}\cdot 2^1+\underset{\_}{1}\cdot 2^0=64+32+16+8+4+2+1=127$
Vorlage:03	$2_3$	$\underset{\_}{2}\cdot 3^0=2$
Vorlage:04	$11311_4$	$\underset{\_}{1}\cdot 4^4+\underset{\_}{1}\cdot 4^3+\underset{\_}{3}\cdot 4^2+\underset{\_}{1}\cdot 4^1+\underset{\_}{1}\cdot 4^0=256+64+48+4+1=373$
Vorlage:05	$313_5$	$\underset{\_}{3}\cdot 5^2+\underset{\_}{1}\cdot 5^1+\underset{\_}{3}\cdot 5^0=75+5+3=83$
Vorlage:06	$334155_6$	$\underset{\_}{3}\cdot 6^5+\underset{\_}{3}\cdot 6^4+\underset{\_}{4}\cdot 6^3+\underset{\_}{1}\cdot 6^2+\underset{\_}{5}\cdot 6^1+\underset{\_}{5}\cdot 6^0=23328+3888+864+36+30+5=28151$
Vorlage:07	$436_7$	$\underset{\_}{4}\cdot 7^2+\underset{\_}{3}\cdot 7^1+\underset{\_}{6}\cdot 7^0=196+21+6=223$
Vorlage:08	$14103_8$	$\underset{\_}{1}\cdot 8^4+\underset{\_}{4}\cdot 8^3+\underset{\_}{1}\cdot 8^2+\underset{\_}{0}\cdot 8^1+\underset{\_}{3}\cdot 8^0=4096+2048+64+0+3=6211$
Vorlage:09	$3738_9$	$\underset{\_}{3}\cdot 9^3+\underset{\_}{7}\cdot 9^2+\underset{\_}{3}\cdot 9^1+\underset{\_}{8}\cdot 9^0=2187+567+27+8=2789$
Vorlage:010	$294001_{10}$	$\underset{\_}{2}\cdot 10^5+\underset{\_}{9}\cdot 10^4+\underset{\_}{4}\cdot 10^3+\underset{\_}{0}\cdot 10^2+\underset{\_}{0}\cdot 10^1+\underset{\_}{1}\cdot 10^0=200000+90000+4000+0+0+1=294001$
Vorlage:011	$2573_{11}$	$\underset{\_}{2}\cdot 11^3+\underset{\_}{5}\cdot 11^2+\underset{\_}{7}\cdot 11^1+\underset{\_}{3}\cdot 11^0=2662+605+77+3=3347$
Vorlage:012	$\mathrm{6}\mathrm{B}\mathrm{8}\mathrm{A}\mathrm{B}\mathrm{7}{\mathrm{7}}_{\mathrm{1}\mathrm{2}}$	$\underset{\_}{6}\cdot 12^6+\underset{\_}{11}\cdot 12^5+\underset{\_}{8}\cdot 12^4+\underset{\_}{10}\cdot 12^3+\underset{\_}{11}\cdot 12^2+\underset{\_}{7}\cdot 12^1+\underset{\_}{7}\cdot 12^0=17915904+2737152+165888+17280+1584+84+7=20837899$
Vorlage:013	$2216_{13}$	$\underset{\_}{2}\cdot 13^3+\underset{\_}{2}\cdot 13^2+\underset{\_}{1}\cdot 13^1+\underset{\_}{6}\cdot 13^0=4394+338+13+6=4751$
Vorlage:014	$\mathrm{C}\mathrm{3}\mathrm{7}\mathrm{1}\mathrm{C}{\mathrm{D}}_{\mathrm{1}\mathrm{4}}$	$\underset{\_}{12}\cdot 14^5+\underset{\_}{3}\cdot 14^4+\underset{\_}{7}\cdot 14^3+\underset{\_}{1}\cdot 14^2+\underset{\_}{12}\cdot 14^1+\underset{\_}{13}\cdot 14^0=6453888+115248+19208+196+168+13=6588721$
Vorlage:015	$\mathrm{9}\mathrm{8}\mathrm{8}\mathrm{0}{\mathrm{E}}_{\mathrm{1}\mathrm{5}}$	$\underset{\_}{9}\cdot 15^4+\underset{\_}{8}\cdot 15^3+\underset{\_}{8}\cdot 15^2+\underset{\_}{0}\cdot 15^1+\underset{\_}{14}\cdot 15^0=455625+27000+1800+0+14=484439$
Vorlage:016	$\mathrm{D}\mathrm{2}\mathrm{A}\mathrm{4}{\mathrm{5}}_{\mathrm{1}\mathrm{6}}$	$\underset{\_}{13}\cdot 16^4+\underset{\_}{2}\cdot 16^3+\underset{\_}{10}\cdot 16^2+\underset{\_}{4}\cdot 16^1+\underset{\_}{5}\cdot 16^0=851968+8192+2560+64+5=862789$

Eigenschaften von schwachen Primzahlen in anderen Zahlensystemen

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

Beweis: siehe 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:

• Linkstrunkierbare Primzahlen (Left-truncatable primes) (Vorlage:OEIS), z. B. 1367 – 367, 67 und 7 wären ebenfalls prim.
• Rechtstrunkierbare Primzahlen (Right-truncatable primes) (Vorlage:OEIS), z. B. 3739 – 373, 37 und 3 wären ebenfalls prim.
• Beidseitig trunkierbare Primzahlen (Two-sided primes) (Vorlage: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) (Vorlage:OEIS), beginnend mit: 7810223, 19579907, 909001523, 984960937, 78406036607, ... welche beide Kriterien erfüllen.

Weblinks

• Vorlage:MathWorld
• Weakly Primes auf Department of Mathematics der Missouri State University (englisch)