Primzahlen: Primfaktorzerlegung nach Fermat

Primzahlen:_III._Kapitel:_Primfaktorzerlegung_und_andere_Methoden

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=1\quad 4=1+3\quad 9=1+3+5\quad 16=1+3+5+7\quad ...\$

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\$