Fastprimzahl

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:

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

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

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

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

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