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.

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. 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.

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:
  ${\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.
  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.
  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.

Einzelnachweise

1. ↑ Wolfgang Blum: Goldbach und die Zwillinge. In: Spektrum der Wissenschaft, Dezember 2008, S. 97 (reproduziert: Primzahlen: Wer lüftet das Geheimnis der Unteilbarkeit? Spiegel Online, 25. Dezember 2008; abgerufen am 24. August 2018).
2. ↑ Paulo Ribenboim: Die Welt der Primzahlen. Geheimnisse und Rekorde. Springer, Berlin / Heidelberg / New York 2006, ISBN 978-3-540-34283-0, S. 219.
3. ↑ Edmund Landau: Handbuch der Lehre von der Verteilung der Primzahlen. B. G. Teubner, 1909, S. 211, abgerufen am 30. Juni 2018. 
4. 1 2 Konstantin Fackeldey: Die Goldbachsche Vermutung und ihre bisherigen Lösungsversuche. (PDF) Freie Universität Berlin, 2002, S. 25–27, abgerufen am 30. Juni 2018.