Schwache Primzahl

Begriff und Bedeutung

Schwache Primzahlen im Sinn von „Weakly Prime Numbers“ oder „Digitally Delicate Prime“ sind Primzahlen, bei denen jede Änderung genau einer Dezimalstelle dazu führt, dass die Zahl ihre Primzahleigenschaft verliert. In den Beispielen entstehen dabei ausschließlich zusammengesetzte Zahlen, also Zahlen, die nicht prim sind.

Der Ausdruck „Weak Prime“ wird außerdem für Primzahlen verwendet, die im Gegensatz zu starken Primzahlen („Strong Prime“) zur Schlüsselgenerierung in asymmetrischen Verschlüsselungsverfahren ungeeignet sind. Diese kryptografische Bedeutung ist von der Eigenschaft der ziffernempfindlichen Primzahlen zu unterscheiden.

Beispiel im Dezimalsystem

Die Primzahl p = 294001 ist eine schwache Primzahl zur Basis 10. Sie hat sechs Dezimalstellen. Wird eine der sechs Stellen durch eine andere Ziffer ersetzt, erhält man 54 mögliche veränderte Zahlen, und zwar (10 − 1) · 6 = 54. Alle diese Zahlen sind zusammengesetzt.

Beispielsweise werden sämtliche möglichen Änderungen der ersten Stelle, der zweiten bis sechsten Stelle geprüft. Dazu gehören etwa 094001, 194001, 394001, 994001, 204001, 294001, 290001, 299001, 294101, 294901, 294011, 294091 sowie 294000 bis 294009. Die ursprüngliche Zahl 294001 erscheint dabei in den Aufstellungen als unveränderte Vergleichszahl, geprüft werden müssen jedoch die Änderungen zu einer anderen Ziffer.

Die ersten schwachen Primzahlen zur Basis 10 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 und 7469797; die Folge ist als A050249 in OEIS angegeben.

Als größte momentan bekannte schwache Primzahl nennt der Artikel mit Stand vom 10. Dezember 2018 eine im März 2007 von Jens Kruse Andersen entdeckte Zahl:

17 · (10^1000 − 1) / 99 + 2168 6652 = 1717 … 1717 3885 8369.

Sie beginnt mit 496 Wiederholungen der Ziffernfolge 17, endet mit 3885 8369 und besitzt insgesamt 1000 Stellen.

Prüfung und Verallgemeinerung auf Zahlensysteme

Für eine k-stellige Primzahl im Dezimalsystem müssen 9 · k veränderte Zahlen darauf untersucht werden, ob sie zusammengesetzt sind. Nur wenn alle diese Zahlen zusammengesetzt sind, ist die Primzahl schwach.

Allgemein sei b eine Zahlbasis. Eine Primzahl p ist schwach zur Basis b, wenn bei ihrer Darstellung zur Basis b jede Änderung genau einer Ziffer d_k mit der Wertigkeit b^k in eine andere Ziffer d'_k mit d'_k ≠ d_k und 0 ≤ d'_k < b die Primzahleigenschaft zerstört. Dabei gilt 0 ≤ k ≤ ⌊log_b p⌋. Die Darstellung von p zur Basis b hat ⌊log_b p⌋ + 1 Ziffern.

Im Definitionsabschnitt gibt der Artikel als Zahl der zu testenden Zahlen b · ⌊log_b p⌋ an. Für eine k-stellige Zahl nennt er im Eigenschaftsabschnitt dagegen (b − 1) · k Zahlen. Diese zweite Angabe entspricht der Zahl möglicher Ersetzungen: Für jede der k Stellen gibt es b − 1 andere Ziffern. Im Dezimalsystem ergibt sich daraus 9 · k.

Für jede natürliche Basis b gibt es unendlich viele schwache Primzahlen zu dieser Basis. Außerdem gibt es im Dezimalsystem unendlich viele schwache Primzahlen, und ihre Dichte unter den Primzahlen ist echt größer als 0. Als Beleg verweist der Artikel auf einen Beweis von Terence Tao aus dem Jahr 2011.

Beispiel und kleinste Werte anderer Basen

Die Zahl 436_7 ist eine schwache Primzahl zur Basis 7. Ihre Umrechnung lautet 4 · 7^2 + 3 · 7^1 + 6 · 7^0 = 196 + 21 + 6 = 223. Da jede der drei Ziffern durch eine der sechs anderen Ziffern ersetzt werden kann, sind insgesamt 6 · 3 = 24 Zahlen zu prüfen. Die aufgelisteten Veränderungen sind alle zusammengesetzt. Als Einzelprüfung wird beispielsweise 433_7 betrachtet: 4 · 7^2 + 3 · 7^1 + 3 · 7^0 = 196 + 21 + 3 = 220, also keine Primzahl.

Die kleinsten im Artikel angegebenen schwachen Primzahlen für die Basen 2 bis 16 sind:

• Basis 2: 1111111_2 = 127.
• Basis 3: 2_3 = 2.
• Basis 4: 11311_4 = 373.
• Basis 5: 313_5 = 83.
• Basis 6: 334155_6 = 28151.
• Basis 7: 436_7 = 223.
• Basis 8: 14103_8 = 6211.
• Basis 9: 3738_9 = 2789.
• Basis 10: 294001_10 = 294001.
• Basis 11: 2573_11 = 3347.
• Basis 12: 6B8AB77_12 = 20837899.
• Basis 13: 2216_13 = 4751.
• Basis 14: C371CD_14 = 6588721.
• Basis 15: 9880E_15 = 484439.
• Basis 16: D2A45_16 = 862789.

Die Folge dieser kleinsten Werte ist als A186995 in OEIS angegeben. Buchstaben wie B, C, D und E dienen dabei als Ziffern für Werte, die in den jeweiligen Zahlensystemen größer als 9 sind.

Ähnliche Primzahlkonstrukte

Ein verwandtes, aber anders definiertes Konstrukt sind trunkierbare Primzahlen („truncatable primes“). Bei ihnen können beliebig viele Stellen abgetrennt werden, ohne dass die verbleibende Zahl ihre Primzahleigenschaft verliert.

• Bei linkstrunkierbaren Primzahlen werden Stellen von links entfernt. Beispiel: Bei 1367 bleiben 367, 67 und 7 prim. Die Folge ist A024785 in OEIS.
• Bei rechtstrunkierbaren Primzahlen werden Stellen von rechts entfernt. Beispiel: Bei 3739 bleiben 373, 37 und 3 prim. Die Folge ist A024770 in OEIS.
• Bei beidseitig trunkierbaren Primzahlen darf die Ziffernabtrennung von beiden Seiten erfolgen. In der strengen Definition gibt es nur 15 solche Primzahlen: 2, 3, 5, 7, 23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797 und 739397. Diese Eigenschaft ist das Gegenstück zum Zerstören der Primzahleigenschaft durch Ziffernänderung.

Eine Kombination sind schwache trunkierbare Primzahlen („Digitally delicate truncatable primes“). Sie erfüllen beide Kriterien. Der Artikel nennt als Anfang der Folge: 7810223, 19579907, 909001523, 984960937 und 78406036607; die Folge ist A347424 in OEIS.