Schwache Primzahlen (engl. Weakly Prime Numbers oder auch Digitally Delicate Prime [ 1] 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.
Die Primzahl
p
=
294001
{\displaystyle p=294001}
Wenn man eine einzige der sechs Dezimalstellen modifiziert, erhält man ausschließlich zusammengesetzte Zahlen, welche keine Primzahlen mehr sind: 0 94001, 1 94001, 2 940013 94001, 4 94001, 5 94001, 6 94001, 7 94001, 8 94001, 9 94001,20 4001, 21 4001, 22 4001, 23 4001, 24 4001, 25 4001, 26 4001, 27 4001, 28 4001, 29 4001
290 001, 291 001, 292 001, 293 001, 294 001 , 295 001, 296 001, 297 001, 298 001, 299 001,
2940 01 , 2941 01, 2942 01, 2943 01, 2944 01, 2945 01, 2946 01, 2947 01, 2948 01, 2949 01,29400 1 , 29401 1, 29402 1, 29403 1, 29404 1, 29405 1, 29406 1, 29407 1, 29408 1, 29409 1,294000 , 294001 , 294002 , 294003 , 294004 , 294005 , 294006 , 294007 , 294008 , 294009 Insgesamt sind in diesem Fall
(
10
−
1
)
⋅
6
=
54
{\displaystyle (10-1)\cdot 6=54}
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:
17
⋅
(
10
1000
−
1
)
99
+
2168
6652
=
1717
…
1717
3885
8369
{\displaystyle {\frac {17\cdot (10^{1000}-1)}{99}}+2168\ 6652=1717\ldots 1717\ 3885\ 8369}
Diese Zahl beginnt mit 496 Mal einer
17
{\displaystyle 17}
3885
8369
{\displaystyle 3885\ 8369}
1000
{\displaystyle 1000}
Um festzustellen, ob eine
k
{\displaystyle k}
9
⋅
k
{\displaystyle 9\cdot k}
9
⋅
k
{\displaystyle 9\cdot k}
k
{\displaystyle k}
Es gibt unendlich viele schwache Primzahlen und ihre Dichte unter den Primzahlen ist echt größer 0. Beweis: siehe[ 3] Terence Tao aus dem Jahr 2011.Obiger Abschnitt behandelte schwache Primzahlen im Dezimalsystem , also zur Basis
b
=
10
{\displaystyle b=10}
Eine Primzahl
p
∈
P
{\displaystyle p\in \mathbb {P} }
schwache Primzahl zur Basis
b
{\displaystyle b}
, wenn sie geschrieben zur Basis
b
{\displaystyle b}
d
k
{\displaystyle d_{k}}
b
k
{\displaystyle b^{k}}
0
≤
k
≤
⌊
log
b
p
⌋
{\displaystyle 0\leq k\leq \lfloor \log _{b}{p}\rfloor }
d
k
′
{\displaystyle d_{k}'}
d
k
′
≠
d
k
{\displaystyle d_{k}'\neq d_{k}}
0
≤
d
k
′
<
b
{\displaystyle 0\leq d_{k}'<b}
Da
p
{\displaystyle p}
b
{\displaystyle b}
⌊
log
b
p
⌋
+
1
{\displaystyle \lfloor \log _{b}{p}\rfloor +1}
b
⋅
⌊
log
b
p
⌋
{\displaystyle b\cdot \lfloor \log _{b}{p}\rfloor }
Die Primzahl
p
=
436
7
=
4
_
⋅
7
2
+
3
_
⋅
7
1
+
6
_
⋅
7
0
=
196
+
21
+
6
=
223
{\displaystyle p=436_{7}={\underline {4}}\cdot 7^{2}+{\underline {3}}\cdot 7^{1}+{\underline {6}}\cdot 7^{0}=196+21+6=223}
b
=
7
{\displaystyle b=7}
Wenn man eine einzige der drei Ziffern in der Basis
b
=
7
{\displaystyle b=7}
keine Primzahlen mehr sind:
0 367 , 1 367 , 2 367 , 3 367 , 4 367 5 367 , 6 367 ,40 67 , 41 67 , 42 67 , 43 67 , 44 67 , 45 67 , 46 67 ,
430 7 , 431 7 , 432 7 , 433 7 , 434 7 , 435 7 , 436 7 .
Insgesamt erhält man in obiger Liste
6
⋅
3
=
24
{\displaystyle 6\cdot 3=24}
Stellvertretend für alle obigen 24 Zahlen wird hier die Zahl
433
7
{\displaystyle 433_{7}}
433
7
=
4
_
⋅
7
2
+
3
_
⋅
7
1
+
3
_
⋅
7
0
=
196
+
21
+
3
=
220
∉
P
{\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} }
keine Primzahl.
Analog funktioniert die Überprüfung aller anderen 23 obigen Zahlen. Die folgende Tabelle gibt die kleinsten schwachen Primzahlen zur Basis
2
≤
b
≤
16
{\displaystyle 2\leq b\leq 16}
A186995 in OEIS ): [ 4]
Basis
b
{\displaystyle b}
schwache Primzahlen zur Basis
b
{\displaystyle b}
Umrechnung dieser Primzahl ins Dezimalsystem
00 2
1111111
2
{\displaystyle 1111111_{2}}
1
_
⋅
2
6
+
1
_
⋅
2
5
+
1
_
⋅
2
4
+
1
_
⋅
2
3
+
1
_
⋅
2
2
+
1
_
⋅
2
1
+
1
_
⋅
2
0
=
64
+
32
+
16
+
8
+
4
+
2
+
1
=
127
{\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}
00 3
2
3
{\displaystyle 2_{3}}
2
_
⋅
3
0
=
2
{\displaystyle {\underline {2}}\cdot 3^{0}=2}
00 4
11311
4
{\displaystyle 11311_{4}}
1
_
⋅
4
4
+
1
_
⋅
4
3
+
3
_
⋅
4
2
+
1
_
⋅
4
1
+
1
_
⋅
4
0
=
256
+
64
+
48
+
4
+
1
=
373
{\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}
00 5
313
5
{\displaystyle 313_{5}}
3
_
⋅
5
2
+
1
_
⋅
5
1
+
3
_
⋅
5
0
=
75
+
5
+
3
=
83
{\displaystyle {\underline {3}}\cdot 5^{2}+{\underline {1}}\cdot 5^{1}+{\underline {3}}\cdot 5^{0}=75+5+3=83}
00 6
334155
6
{\displaystyle 334155_{6}}
3
_
⋅
6
5
+
3
_
⋅
6
4
+
4
_
⋅
6
3
+
1
_
⋅
6
2
+
5
_
⋅
6
1
+
5
_
⋅
6
0
=
23328
+
3888
+
864
+
36
+
30
+
5
=
28151
{\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}
00 7
436
7
{\displaystyle 436_{7}}
4
_
⋅
7
2
+
3
_
⋅
7
1
+
6
_
⋅
7
0
=
196
+
21
+
6
=
223
{\displaystyle {\underline {4}}\cdot 7^{2}+{\underline {3}}\cdot 7^{1}+{\underline {6}}\cdot 7^{0}=196+21+6=223}
00 8
14103
8
{\displaystyle 14103_{8}}
1
_
⋅
8
4
+
4
_
⋅
8
3
+
1
_
⋅
8
2
+
0
_
⋅
8
1
+
3
_
⋅
8
0
=
4096
+
2048
+
64
+
0
+
3
=
6211
{\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}
00 9
3738
9
{\displaystyle 3738_{9}}
3
_
⋅
9
3
+
7
_
⋅
9
2
+
3
_
⋅
9
1
+
8
_
⋅
9
0
=
2187
+
567
+
27
+
8
=
2789
{\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}
0 10
294001
10
{\displaystyle 294001_{10}}
2
_
⋅
10
5
+
9
_
⋅
10
4
+
4
_
⋅
10
3
+
0
_
⋅
10
2
+
0
_
⋅
10
1
+
1
_
⋅
10
0
=
200000
+
90000
+
4000
+
0
+
0
+
1
=
294001
{\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}
0 11
2573
11
{\displaystyle 2573_{11}}
2
_
⋅
11
3
+
5
_
⋅
11
2
+
7
_
⋅
11
1
+
3
_
⋅
11
0
=
2662
+
605
+
77
+
3
=
3347
{\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}
0 12
6
B
8
A
B
77
12
{\displaystyle \mathrm {6B8AB77_{12}} }
6
_
⋅
12
6
+
11
_
⋅
12
5
+
8
_
⋅
12
4
+
10
_
⋅
12
3
+
11
_
⋅
12
2
+
7
_
⋅
12
1
+
7
_
⋅
12
0
=
17915904
+
2737152
+
165888
+
17280
+
1584
+
84
+
7
=
20837899
{\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}
0 13
2216
13
{\displaystyle 2216_{13}}
2
_
⋅
13
3
+
2
_
⋅
13
2
+
1
_
⋅
13
1
+
6
_
⋅
13
0
=
4394
+
338
+
13
+
6
=
4751
{\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}
0 14
C
371
C
D
14
{\displaystyle \mathrm {C371CD_{14}} }
12
_
⋅
14
5
+
3
_
⋅
14
4
+
7
_
⋅
14
3
+
1
_
⋅
14
2
+
12
_
⋅
14
1
+
13
_
⋅
14
0
=
6453888
+
115248
+
19208
+
196
+
168
+
13
=
6588721
{\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}
0 15
9880
E
15
{\displaystyle \mathrm {9880E_{15}} }
9
_
⋅
15
4
+
8
_
⋅
15
3
+
8
_
⋅
15
2
+
0
_
⋅
15
1
+
14
_
⋅
15
0
=
455625
+
27000
+
1800
+
0
+
14
=
484439
{\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}
0 16
D
2
A
45
16
{\displaystyle \mathrm {D2A45_{16}} }
13
_
⋅
16
4
+
2
_
⋅
16
3
+
10
_
⋅
16
2
+
4
_
⋅
16
1
+
5
_
⋅
16
0
=
851968
+
8192
+
2560
+
64
+
5
=
862789
{\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}
Um festzustellen, ob eine
k
{\displaystyle k}
b
{\displaystyle b}
(
b
−
1
)
⋅
k
{\displaystyle (b-1)\cdot k}
(
b
−
1
)
⋅
k
{\displaystyle (b-1)\cdot k}
k
{\displaystyle k}
b
{\displaystyle b}
Sei
b
∈
N
{\displaystyle b\in \mathbb {N} }
b
{\displaystyle b}
Beweis: siehe[ 3] Terence Tao aus dem Jahr 2011.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.
↑
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 .
↑ Weakly Primes kommentar. abgerufen am 10. Dezember 2018 . ↑ 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 . ↑ Schwache Primzahlen und das Unärsystem sind unvereinbar. Schwache Primzahlen arbeiten explizit nur mit Ziffern, die kleiner als die Basis sind
0
≤
d
k
<
b
{\displaystyle 0\leq d_{k}<b}
d
k
≥
b
{\displaystyle d_{k}\geq b}
↑ Eric W. Weisstein : Truncatable Prime .MathWorld
formelbasiert
Carol ((2n 2 − 2) |
Doppelte Mersenne (22p − 1) |
Fakultät (n! ± 1) |
Fermat (22n + 1) |
Kubisch (x 3 − y 3 )/(x − y ) |
Kynea ((2n 2 − 2) |
Leyland (x y y x |
Mersenne (2p |
Mills (A 3n ) |
Pierpont (2u v |
Primorial (p n |
Proth (k ⋅2n |
Pythagoreisch (4n + 1) |
Quartisch (x 4 + y 4 ) |
Thabit (3⋅2n |
Wagstaff ((2p |
Williams ((b-1 )⋅b n |
Woodall (n ⋅2n
Primzahlfolgen
Bell |
Fibonacci |
Lucas |
Motzkin |
Pell |
Perrin
eigenschaftsbasiert
Elitär |
Fortunate |
Gut |
Glücklich |
Higgs |
Hochkototient |
Isoliert |
Pillai |
Ramanujan |
Regulär |
Stark |
Stern |
Wall–Sun–Sun |
Wieferich |
Wilson
basis abhängig
Belphegor |
Champernowne |
Dihedral |
Einzigartig |
Fröhlich |
Keith |
Lange |
Minimal |
Mirp |
Permutierbar |
Primeval |
Palindrom |
Repunit-Primzahl ((10n |
Schwach |
Smarandache–Wellin |
Strobogrammatisch |
Tetradisch |
Trunkierbar |
Zirkular
basierend auf Tupel
Ausbalanciert (p − n , p , p + n) |
Chen |
Cousin (p , p + 4) |
Cunningham (p , 2p ± 1, …) |
Drilling (p , p + 2 oder p + 4, p + 6) |
Konstellation |
Sexy (p , p + 6) |
Sichere (p , (p − 1)/2) |
Sophie Germain (p , 2p + 1) |
Vierling (p , p + 2, p + 6, p + 8) |
Zwilling (p , p + 2) |
Zwillings-Bi-Kette (n ± 1, 2n ± 1, …)
nach Größe
Titanisch (1.000+ Stellen) |
Gigantisch (10.000+ Stellen) |
Mega (1.000.000+ Stellen) |
Beva (1.000.000.000+ Stellen)
