Fastprimzahl

Eine $n$-Fastprimzahl oder auch Fastprimzahl $n$-ter Ordnung ist eine natürliche Zahl, deren Primfaktorzerlegung aus genau $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.

Definition

Sei $z\in \mathbb{N}\setminus \{0\}$ und $z={\prod }_{i=1}^k{p_i}^{e_i}$ mit Primzahlen $p_1,\dots ,p_k$. Dann heißt $z$ Fastprimzahl $n$-ter Ordnung, wobei $n={\sum }_{i=1}^k{e}_i$ gilt. Die Zahlenfolge für ein festes $n$ wird auch mit $P_n$ bezeichnet. 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:

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

Die ersten zwölf Fastprimzahlen erster bis zwanzigster Ordnung

Vorlage:01. Ordnung	2	3	5	7	11	13	17	19	23	29	31	37	…	Vorlage:OEIS
Vorlage:02. Ordnung	4	6	9	10	14	15	21	22	25	26	33	34	…	Vorlage:OEIS
Vorlage:03. Ordnung	8	12	18	20	27	28	30	42	44	45	50	52	…	Vorlage:OEIS
Vorlage:04. Ordnung	16	24	36	40	54	56	60	81	84	88	90	100	…	Vorlage:OEIS
Vorlage:05. Ordnung	32	48	72	80	108	112	120	162	168	176	180	200	…	Vorlage:OEIS
Vorlage:06. Ordnung	64	96	144	160	216	224	240	324	336	352	360	400	…	Vorlage:OEIS
Vorlage:07. Ordnung	128	192	288	320	432	448	480	648	672	704	720	800	…	Vorlage:OEIS
Vorlage:08. Ordnung	256	384	576	640	864	896	960	1296	1344	1408	1440	1600	…	Vorlage:OEIS
Vorlage:09. Ordnung	512	768	1152	1280	1728	1792	1920	2592	2688	2816	2880	3200	…	Vorlage:OEIS
10. Ordnung	1024	1536	2304	2560	3456	3584	3840	5184	5376	5632	5760	6400	…	Vorlage:OEIS
11. Ordnung	2048	3072	4608	5120	6912	7168	7680	10368	10752	11264	11520	12800	…	Vorlage:OEIS
12. Ordnung	4096	6144	9216	10240	13824	14336	15360	20736	21504	22528	23040	25600	…	Vorlage:OEIS
13. Ordnung	8192	12288	18432	20480	27648	28672	30720	41472	43008	45056	46080	51200	…	Vorlage:OEIS
14. Ordnung	16384	24576	36864	40960	55296	57344	61440	82944	86016	90112	92160	102400	…	Vorlage:OEIS
15. Ordnung	32768	49152	73728	81920	110592	114688	122880	165888	172032	180224	184320	204800	…	Vorlage:OEIS
16. Ordnung	65536	98304	147456	163840	221184	229376	245760	331776	344064	360448	368640	409600	…	Vorlage:OEIS
17. Ordnung	131072	196608	294912	327680	442368	458752	491520	663552	688128	720896	737280	819200	…	Vorlage:OEIS
18. Ordnung	262144	393216	589824	655360	884736	917504	983040	1327104	1376256	1441792	1474560	1638400	…	Vorlage:OEIS
19. Ordnung	524288	786432	1179648	1310720	1769472	1835008	1966080	2654208	2752512	2883584	2949120	3276800	…	Vorlage:OEIS
20. Ordnung	1048576	1572864	2359296	2621440	3538944	3670016	3932160	5308416	5505024	5767168	5898240	6553600	…	Vorlage: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 $P_n$ bilden eine Zerlegung der natürlichen Zahlen.
• Jede Fastprimzahl $n$-ter Ordnung ist das Produkt von Fastprimzahlen der Ordnungen $k_1,\dots ,k_m$ mit $\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 $k_1,\dots ,k_m>0$ gibt es $S_{n,m}$ solcher möglichen Zerlegungen, wobei $S_{n,m}$ die Stirling-Zahlen zweiter Art bezeichnet.
• Da es für die Null keine mögliche Primfaktorzerlegung gibt, ist sie keine Fastprimzahl $n$-ter Ordnung.
• Der Eins wird das leere Produkt als Primfaktorzerlegung zugewiesen. Entsprechend kann sie definitionskonform als Fastprimzahl 0-ter Ordnung bezeichnet werden.
• Sei ${\pi }_k(n)$ die Anzahl der positiven ganzen Zahlen kleiner gleich $n$ mit genau $k$ Primteilern (die nicht unbedingt verschieden sein müssen). Dann gilt:
  ${\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.
  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 $p+2$ eine 2-Fastprimzahl ist.
  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

• Vorlage:MathWorld Fastprimzahlen
• Vorlage:MathWorld 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.