Fastprimzahl

Eine ${\displaystyle n}$-Fastprimzahl oder auch Fastprimzahl ${\displaystyle n}$-ter Ordnung ist eine natürliche Zahl, deren Primfaktorzerlegung aus genau ${\displaystyle n}$ Primzahlen besteht, wobei mehrfache Primteiler entsprechend oft gezählt werden. Da alle natürlichen Zahlen größer eins aus Primfaktoren zusammengesetzt sind, ist jede natürliche Zahl zugleich auch eine Fastprimzahl. Fastprimzahlen zweiter Ordnung (also die Produkte von genau zwei Primzahlen) nennt man auch Semiprimzahlen.

Fastprimzahlen bewegen sich zwischen den Polen der unteilbaren Primzahlen und der maximal teilbaren hochzusammengesetzten Zahlen und schließen dabei beide mit ein.

Der Norweger Viggo Brun führte den Begriff um 1915 zur Verallgemeinerung von Primzahlen ein, um einen neuen Ansatz für ungelöste Primzahlprobleme zu finden.^[1]

Definition

Sei ${\displaystyle z\in \mathbb {N} \setminus \{0\}}$ und ${\displaystyle \textstyle z=\prod _{i=1}^{k}{p_{i}}^{e_{i}}}$ mit Primzahlen ${\displaystyle p_{1},\dotsc ,p_{k}}$. Dann heißt ${\displaystyle z}$ Fastprimzahl ${\displaystyle n}$-ter Ordnung, wobei ${\displaystyle \textstyle n=\sum _{i=1}^{k}e_{i}}$ gilt. Die Zahlenfolge für ein festes ${\displaystyle n}$ wird auch mit ${\displaystyle P_{n}}$ bezeichnet.^[2] Die Wohldefiniertheit folgt aus der Eindeutigkeit der Primfaktorzerlegung für alle natürlichen Zahlen.

Dieses Konzept kann problemlos auf die ganzen Zahlen und beliebige ZPE-Ringe verallgemeinert werden.

Beispiele und Werte

Beispiele:

• ${\displaystyle 13}$ ist eine Fastprimzahl erster Ordnung („Primzahl“).
• ${\displaystyle 91=7\cdot 13}$ ist eine Fastprimzahl zweiter Ordnung („Semiprimzahl“).
• ${\displaystyle 100=2^{2}\cdot 5^{2}}$ ist eine Fastprimzahl vierter Ordnung.
• ${\displaystyle 1024=2^{10}}$ ist eine Fastprimzahl zehnter Ordnung.
• ${\displaystyle 5308416=2^{16}\cdot 3^{4}}$ ist eine Fastprimzahl zwanzigster Ordnung.

Die ersten zwölf Fastprimzahlen erster bis zwanzigster Ordnung

01. Ordnung	2	3	5	7	11	13	17	19	23	29	31	37	…	Folge A000040 in OEIS
02. Ordnung	4	6	9	10	14	15	21	22	25	26	33	34	…	Folge A001358 in OEIS
03. Ordnung	8	12	18	20	27	28	30	42	44	45	50	52	…	Folge A014612 in OEIS
04. Ordnung	16	24	36	40	54	56	60	81	84	88	90	100	…	Folge A014613 in OEIS
05. Ordnung	32	48	72	80	108	112	120	162	168	176	180	200	…	Folge A014614 in OEIS
06. Ordnung	64	96	144	160	216	224	240	324	336	352	360	400	…	Folge A046306 in OEIS
07. Ordnung	128	192	288	320	432	448	480	648	672	704	720	800	…	Folge A046308 in OEIS
08. Ordnung	256	384	576	640	864	896	960	1296	1344	1408	1440	1600	…	Folge A046310 in OEIS
09. Ordnung	512	768	1152	1280	1728	1792	1920	2592	2688	2816	2880	3200	…	Folge A046312 in OEIS
10. Ordnung	1024	1536	2304	2560	3456	3584	3840	5184	5376	5632	5760	6400	…	Folge A046314 in OEIS
11. Ordnung	2048	3072	4608	5120	6912	7168	7680	10368	10752	11264	11520	12800	…	Folge A069272 in OEIS
12. Ordnung	4096	6144	9216	10240	13824	14336	15360	20736	21504	22528	23040	25600	…	Folge A069273 in OEIS
13. Ordnung	8192	12288	18432	20480	27648	28672	30720	41472	43008	45056	46080	51200	…	Folge A069274 in OEIS
14. Ordnung	16384	24576	36864	40960	55296	57344	61440	82944	86016	90112	92160	102400	…	Folge A069275 in OEIS
15. Ordnung	32768	49152	73728	81920	110592	114688	122880	165888	172032	180224	184320	204800	…	Folge A069276 in OEIS
16. Ordnung	65536	98304	147456	163840	221184	229376	245760	331776	344064	360448	368640	409600	…	Folge A069277 in OEIS
17. Ordnung	131072	196608	294912	327680	442368	458752	491520	663552	688128	720896	737280	819200	…	Folge A069278 in OEIS
18. Ordnung	262144	393216	589824	655360	884736	917504	983040	1327104	1376256	1441792	1474560	1638400	…	Folge A069279 in OEIS
19. Ordnung	524288	786432	1179648	1310720	1769472	1835008	1966080	2654208	2752512	2883584	2949120	3276800	…	Folge A069280 in OEIS
20. Ordnung	1048576	1572864	2359296	2621440	3538944	3670016	3932160	5308416	5505024	5767168	5898240	6553600	…	Folge A069281 in OEIS

Eigenschaften

• Jede Primzahl ist eine Fastprimzahl der Ordnung 1, jede zusammengesetzte Zahl ist eine Fastprimzahl der Ordnung 2 oder höher. Fastprimzahlen dritter Ordnung, sofern diese aus 3 verschiedenen Primfaktoren bestehen, nennt man auch sphenische Zahlen.
• Die Vereinigung der ${\displaystyle P_{n}}$ bilden eine Zerlegung der natürlichen Zahlen.
• Jede Fastprimzahl ${\displaystyle n}$-ter Ordnung ist das Produkt von Fastprimzahlen der Ordnungen ${\displaystyle k_{1},\dotsc ,k_{m}}$ mit ${\displaystyle \sum _{i=1}^{m}k_{i}=n}$, z. B.: Das Produkt der 3-Fastprimzahl 12 und der 4-Fastprimzahl 40 ergibt die 7-Fastprimzahl 480. Für ${\displaystyle k_{1},\dotsc ,k_{m}>0}$ gibt es ${\displaystyle S_{n,m}}$ solcher möglichen Zerlegungen, wobei ${\displaystyle S_{n,m}}$ die Stirling-Zahlen zweiter Art bezeichnet.
• Da es für die Null keine mögliche Primfaktorzerlegung gibt, ist sie keine Fastprimzahl ${\displaystyle n}$-ter Ordnung.
• Der Eins wird das leere Produkt als Primfaktorzerlegung zugewiesen. Entsprechend kann sie definitionskonform als Fastprimzahl 0-ter Ordnung bezeichnet werden.
• Sei ${\displaystyle \pi _{k}(n)}$ die Anzahl der positiven ganzen Zahlen kleiner gleich ${\displaystyle n}$ mit genau ${\displaystyle k}$ Primteilern (die nicht unbedingt verschieden sein müssen). Dann gilt:^[3]
  ${\displaystyle \pi _{k}(n)\sim {\frac {n}{\log n}}\cdot {\frac {(\log \log n)^{k-1}}{(k-1)!}}}$
• Jede genügend große gerade Zahl lässt sich als die Summe zweier Primzahlen oder einer Primzahl und einer Fastprimzahl zweiter Ordnung darstellen.^[4]
  Diese Aussage hat Ähnlichkeit mit der Goldbachschen Vermutung, wurde 1978 von Chen Jingrun bewiesen und nennt sich Satz von Chen.
• Es gibt unendlich viele Primzahlen, sodass ${\displaystyle p+2}$ eine 2-Fastprimzahl ist.^[4]
  Diese Aussage hat Ähnlichkeit mit der Vermutung über Primzahlzwillinge und wurde ebenfalls von Chen bewiesen.

Anwendungen

Fastprimzahlen zweiter Ordnung, also Produkte zweier Primzahlen, finden in der Kryptographie Anwendung.

Weblinks

• Eric W. Weisstein: Almost prime. In: MathWorld (englisch). Fastprimzahlen
• Eric W. Weisstein: Semiprime. In: MathWorld (englisch). Fastprimzahlen 2. Ordnung

Literatur

• Władysław Narkiewicz: The Development of Prime Number Theory. From Euclid to Hardy and Littlewood. Springer, Berlin u. a. 2000, ISBN 3-540-66289-8.
• Hans Riesel: Prime Numbers and Computer Methods for Factorization. Birkhäuser, Boston/Basel/Stuttgart 1985, ISBN 3-7643-3291-3.
• David M. Bressoud: Factorization and Primality Testing. Springer, New York u. a. 1989, ISBN 0-387-97040-1.
• Paulo Ribenboim: The little book of bigger primes. 2. Ausgabe. Springer, New York u. a. 2004, ISBN 0-387-20169-6.
• Die Welt der Primzahlen. Geheimnisse und Rekorde. Auf den neuesten Stand gebracht von Wilfrid Keller. Springer, Berlin / Heidelberg / New York 2006, ISBN 978-3-540-34283-0.