Primzahlen: Primfaktorzerlegung nach Fermat

Die Primzahlzerlegung nach Fermat ist ein recht einfach zu verstehendes Verfahren, das allerdings nicht besonders effektiv ist; jedoch wesentlich effektiver als das konsequente Testen.

Die Folge der Quadratzahlen

Um die Folge der Quadratzahlen zu bekommen gibt es eine einfache Methode: Man addiert alle ungeraden, natürlichen Zahlen.

$1=14=1+39=1+3+516=1+3+5+7...$

Die allgemeine Formel lautet:

$\sum _{i=1}^{n}2\cdot i-1=n^2$

Da $n^2=(\sum _{i=1}^{n-1}2\cdot i-1)+2\cdot n-1=(n-1{)}^2+2\cdot n-1$ gilt, läßt sich jede ungerade, natürliche Zahl auf mindestens eine Art als Differenz zweier Quadratzahlen darstellen.

Die dritte Binomische Formel

Da sich jede ungerade, natürliche Zahl $n$ auf mindestens eine Art als Differenz zweier Quadratzahlen $n=b^2-a^2$ darstellen läßt, kann man die dritte Binomische Formel $b^2-a^2=(b+a)\cdot (b-a)$ anwenden. Die Terme $(b+a)$ und $(b-a)$ sind dabei Faktoren von $n$, da wegen $n=b^2-a^2$ auch $n=(b+a)\cdot (b-a)$ gilt.

Einschränkung

Die Primzahlzerlegung nach Fermat funktioniert nur für ungerade, natürliche Zahlen. Der Faktor 2 muß also vorher entfernt werden.

Verfahren

Man will eine ungerade natürliche Zahl $n$ faktorisieren. Dazu nimmt man die Quadratzahl $q>n$ die am nächsten an $n$ liegt. Nun ermittelt man die Differenz $d=a^2-n$. Wenn die Differenz $d$ eine Quadratzahl $b^2$ ist, kann man zwei Faktoren von $n$ bestimmen. Falls nicht, nimmt man die nächst höhere Quadratzahl.

Beispiel

51

$64-51=13$

$81-51=30$

$100-51=49$ Treffer: $100=10^2$ und $49=7^2$ sind beides Quadratzahlen.

Mit der Anwendung des dritten binomischen Satz $(10+7)\cdot (10-7)=17\cdot 3=51$ bekommt man die beiden Faktoren.

Der schlimmste Fall

Im schlimmsten Fall ist die zu prüfende Zahl $n$ eine Primzahl. In diesem Fall sind die einzigen Teiler $n$ und 1. Die dabei zugehörigen $a$ und $b$ sind $a=\frac{n-1}{2}+1$ und $b=\frac{n-1}{2}$.

Beispiel

43

$b=\frac{43-1}{2}=21$

$a=21+1=22$