Schwache Primzahl

Schwache Primzahlen (engl. Weakly Prime Numbers oder auch Digitally Delicate Prime<ref> 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. </ref>) 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 <math>p=294001</math> 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 <math>(10-1) \cdot 6 = 54</math> 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.<ref>Weakly Primes kommentar. primepuzzles.net, 2012, abgerufen am 10. Dezember 2018. </ref>

Sie lautet:

<math>\frac{17 \cdot (10^{1000} - 1)}{99} + 2168\ 6652 = 1717 \ldots 1717\ 3885\ 8369</math>.

Diese Zahl beginnt mit 496 Mal einer <math>17</math> und wird durch die Folge <math>3885\ 8369</math> abgeschlossen. Sie besteht aus insgesamt <math>1000</math> Stellen.

Eigenschaften

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

Schwache Primzahlen in beliebigen Zahlensystemen

Obiger Abschnitt behandelte schwache Primzahlen im Dezimalsystem, also zur Basis <math>b=10</math>.

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

Da <math>p</math> in der Basis <math>b</math> aus <math>\lfloor\log_b{p}\rfloor + 1</math> Ziffern besteht, sind dazu <math>b \cdot \lfloor\log_b{p}\rfloor</math> Zahlen zu testen.

Beispiele von schwachen Primzahlen in anderen Zahlensystemen

Die Primzahl <math>p=436_7=\underline{4} \cdot 7^2+\underline{3} \cdot 7^1+\underline{6} \cdot 7^0=196+21+6=223</math> ist eine schwache Primzahl zur Basis <math>b=7</math>, weil gilt:

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

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

<math>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</math> ist keine Primzahl.

Analog funktioniert die Überprüfung aller anderen 23 obigen Zahlen.

Die folgende Tabelle gibt die kleinsten schwachen Primzahlen zur Basis <math>2 \leq b \leq 16</math> an (Folge A186995 in OEIS): <ref>Schwache Primzahlen und das Unärsystem sind unvereinbar. Schwache Primzahlen arbeiten explizit nur mit Ziffern, die kleiner als die Basis sind <math>0 \le d_k < b</math>. Dieses ist essentiell für die Betrachtung von schwachen Primzahlen und ist im Unärsystem prinzipbedingt verletzt. Lässt man Ziffern <math>d_k \ge b</math> zu, gibt es keine schwachen Primzahlen.</ref>

Basis <math>b</math>	schwache Primzahlen zur Basis <math>b</math>	Umrechnung dieser Primzahl ins Dezimalsystem
002	<math>1111111_2</math>	<math>\!\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</math>
003	<math>2_3</math>	<math>\underline{2} \cdot 3^0 = 2</math>
004	<math>11311_4</math>	<math>\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</math>
005	<math>313_5</math>	<math>\underline{3} \cdot 5^2 + \underline{1} \cdot 5^1 + \underline{3} \cdot 5^0 = 75+5+3=83</math>
006	<math>334155_6</math>	<math>\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</math>
007	<math>436_7</math>	<math> \underline{4} \cdot 7^2 + \underline{3} \cdot 7^1 + \underline{6} \cdot 7^0 = 196+21+6=223</math>
008	<math>14103_8</math>	<math>\!\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</math>
009	<math>3738_9</math>	<math>\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</math>
010	<math>294001_{10}</math>	<math>\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</math>
011	<math>2573_{11}</math>	<math>\!\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</math>
012	<math>\mathrm{6B8AB77_{12}}</math>	<math>\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</math>
013	<math>2216_{13}</math>	<math>\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</math>
014	<math>\mathrm{C371CD_{14}}</math>	<math>\!\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</math>
015	<math>\mathrm{9880E_{15}}</math>	<math>\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</math>
016	<math>\mathrm{D2A45_{16}}</math>	<math>\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</math>

Eigenschaften von schwachen Primzahlen in anderen Zahlensystemen

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

Beweis: siehe<ref name="Tao "/> von Terence Tao aus dem Jahr 2011.

Weblinks

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

Einzelnachweise

Vorlage:Navigationsleiste Primzahlklassen