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 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 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:
.
Diese Zahl beginnt mit 496 Mal einer und wird durch die Folge abgeschlossen. Sie besteht aus insgesamt Stellen.

Eigenschaften

  • Um festzustellen, ob eine -stellige Primzahl eine schwache Primzahl ist, muss man Zahlen kontrollieren, ob sie zusammengesetzt sind oder nicht. Nur wenn alle Zahlen zusammengesetzt sind, ist die -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 .

Eine Primzahl ist eine schwache Primzahl zur Basis , wenn sie geschrieben zur Basis bei Änderung einer beliebigen einzelnen Ziffer (mit der Wertigkeit ) mit in eine andere Ziffer mit und immer ihre Primzahl-Eigenschaft verliert.

Da in der Basis aus Ziffern besteht, sind dazu Zahlen zu testen.

Beispiele von schwachen Primzahlen in anderen Zahlensystemen

  • Die Primzahl ist eine schwache Primzahl zur Basis , weil gilt:
Wenn man eine einzige der drei Ziffern in der Basis 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 zusammengesetzte Zahlen.
Stellvertretend für alle obigen 24 Zahlen wird hier die Zahl auf ihre Primalität geprüft:
ist keine Primzahl.
Analog funktioniert die Überprüfung aller anderen 23 obigen Zahlen.

Die folgende Tabelle gibt die kleinsten schwachen Primzahlen zur Basis an (Folge A186995 in OEIS): [4]

Basis
schwache Primzahlen zur Basis Umrechnung dieser Primzahl ins Dezimalsystem
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016

Eigenschaften von schwachen Primzahlen in anderen Zahlensystemen

  • Um festzustellen, ob eine -stellige Primzahl eine schwache Primzahl zur Basis ist, muss man Zahlen kontrollieren, ob sie zusammengesetzt sind oder nicht. Nur wenn alle Zahlen zusammengesetzt sind, ist die -stellige Primzahl tatsächlich eine schwache Primzahl zur Basis .
  • Sei eine Basis. Dann gibt es unendlich viele schwache Primzahlen zu dieser Basis .
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.

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 . Dieses ist essentiell für die Betrachtung von schwachen Primzahlen und ist im Unärsystem prinzipbedingt verletzt. Lässt man Ziffern zu, gibt es keine schwachen Primzahlen.
  5. Eric W. Weisstein: Truncatable Prime. In: MathWorld (englisch).