Primzahl
Primzahl

== Primfaktorzerlegung ==
Es gilt der Fundamentalsatz der Arithmetik: Jede positive ganze Zahl lässt sich als Produkt von Primzahlen darstellen, und diese Darstellung ist bis auf die Reihenfolge der Primzahlen eindeutig. Diese Primzahlen nennt man die ''Primfaktoren'' der Zahl. Die Eins wird dabei als leeres Produkt dargestellt.
Weil sich jede natürliche Zahl größer null durch Multiplikation von Primzahlen eindeutig darstellen lässt, nehmen die Primzahlen eine besondere atomare Stellung in der Mathematik ein, sie „erzeugen“ gewissermaßen alle anderen natürlichen Zahlen. Alexander K. Dewdney bezeichnete sie als den Elementen der Chemie weitgehend ähnlich.
Daraus wird auch klar, warum es unzweckmäßig ist, die Eins als Primzahl zu definieren: Sie ist das neutrale Element der Multiplikation und kann somit multiplikativ keine weiteren Zahlen erzeugen. Sie wird für die Darstellung der Zahlen als Produkt von Primfaktoren nicht benötigt. Würde man die 1 zu den Primzahlen zählen, verlöre sich darüber hinaus die Eindeutigkeit der Primfaktorzerlegung, weil man an jede Zerlegung beliebig viele Einsen anhängen kann, ohne den Wert der Zahl zu ändern.
Man hat eine Reihe von Faktorisierungsverfahren entwickelt, um die Primfaktoren von allgemeinen Zahlen oder auch solchen von spezieller Form möglichst schnell zu bestimmen. Man kennt aber bisher keine Methode, um beliebige Zahlen effizient zu faktorisieren, d. h. in einer Zeit, die höchstens polynomiell mit der Länge der gegebenen Zahl wächst. Die ''Faktorisierungsannahme'' besagt, dass es eine solche Methode auch nicht gibt.