Fastprimzahl

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 aus Primfaktoren zusammengesetzt sind, ist jede natürliche Zahl zugleich auch eine Fastprimzahl. Fastprimzahlen zweiter Ordnung nennt man auch Semiprimzahlen. Fastprimzahlen bewegen sich zwischen den Polen der unteilbaren Primzahlen und den 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[Bearbeiten]

Sei z \in \Bbb N \setminus \{0\} und z = \prod_{i=1}^k{p_i}^{e_i} mit Primzahlen {p_1}, \ldots, {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.[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.

Eigenschaften[Bearbeiten]

  • 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}, ..., {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}, ..., {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.

Beispiele und Werte[Bearbeiten]

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.
Die ersten zwölf Fastprimzahlen erster bis siebter Ordnung
1. Ordnung   2 3 5 7 11 13 17 19 23 29 31 37 Folge A000040 in OEIS
2. Ordnung 4 6 9 10 14 15 21 22 25 26 33 34 Folge A001358 in OEIS
3. Ordnung 8 12 18 20 27 28 30 42 44 45 50 52 Folge A014612 in OEIS
4. Ordnung 16 24 36 40 54 56 60 81 84 88 90 100 Folge A014613 in OEIS
5. Ordnung 32 48 72 80 108 112 120 162 168 176 180 200 Folge A014614 in OEIS
6. Ordnung 64 96 144 160 216 224 240 324 336 352 360 400 Folge A046306 in OEIS
7. Ordnung 128 192 288 320 432 448 480 648 672 704 720 800 Folge A046308 in OEIS

Anwendungen[Bearbeiten]

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

Die beiden folgenden Sätze wurden in den 1970er-Jahren bewiesen:

  • Jede genügend große, natürliche, gerade Zahl lässt sich als die Summe einer Fastprimzahl erster und einer Fastprimzahl zweiter Ordnung darstellen. Diese Aussage ist vergleichbar mit der Goldbachschen Vermutung.
  • Es gibt unendlich viele Primzahlen, die einen Abstand von 2 zu einer 2-Fastprimzahl haben. Dies ist vergleichbar mit der Vermutung über Primzahlzwillinge.

Literatur[Bearbeiten]

Weblinks[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. Wolfgang Blum: Goldbach und die Zwillinge. In: Spektrum der Wissenschaft. Dezember 2008, S. 97 (reproduziert in Spiegel Online: Primzahlen: Wer lüftet das Geheimnis der Unteilbarkeit? 25. Dezember 2008)
  2. Paulo Ribenboim: Die Welt der Primzahlen. Geheimnisse und Rekorde. Springer, Berlin/ Heidelberg/New York 2006, ISBN 978-3-540-34283-0, S. 219