WikiDer > Faktorisierungsmethode von Fermat

In dem Zahlentheorie ist Faktorisierungsmethode von Fermat ein Algorithmus eine ungerade auflösen zusammengesetzte Zahl${displaystyle n}$ in zwei faktoren${Anzeigestil a}$ und ${displaystyle b}$, also so ${displaystyle n=acdot b}$.

Diese Faktorisierungsmethode ist besonders effektiv, wenn die Zahl als Produkt von ungefähr gleichen Faktoren dargestellt werden kann. Das Verfahren bildet auch die Grundlage allgemeiner Faktorisierungsverfahren für große Zahlen, die weniger Rechenzeit benötigen.

Pierre de Fermat beschrieb 1643 diese heute nach ihm benannte Methode in einem vermutlich an Mersenne oder auf Frenicle de Bessy. In diesem Brief zeigte er die Methode, indem er die Primfaktorzerlegung der Zahl 2.027.651.281 berechnete.^[1] Einige Historiker vermuten jedoch, dass die Methode bereits vorher bekannt war.

Algorithmus

spät ${displaystyle n}$ sei die zu faktorisierende ungerade Zahl und ${displaystyle m=lceil {sqrt {n}}ceil}$ die kleinste ganze Zahl größer oder gleich ${displaystyle {sqrt {n}}}$. Die Faktorisierungsmethode von Fermat berechnet sukzessive:

${displaystyle (m 0)^{2}-n}$

${Displaystil (m 1)^{2}-n}$

${Displaystil (m 2)^{2}-n}$

${displaystyle vdots }$

Dies geht so lange, bis das Ergebnis ein Quadrat ist:

${Anzeigestil (m z)^{2}-n=y^{2}}$

Dann mit ${displaystyle mz=x}$,

${displaystyle n=x^{2}-y^{2}=(x y)(x-y)=acdot b}$.

Dies ergibt die Auflösung von ${displaystyle n}$ für die das Verhältnis ${Anzeigestil a/b}$ (mit ${displaystyle alterq b}$) ist die kleinste.

Hinweis

Durch die Überprüfung der letzten beiden Stellen des berechneten Ergebnisses kann man in vielen Fällen ausschließen, dass es sich um ein Quadrat handelt. Ein Quadrat hat als letzte zwei Ziffern nur eine von 22 Möglichkeiten: 00, X1, X4, 25, Y6 und X9, wobei X für eine gerade Ziffer und Y für eine ungerade Ziffer steht. Auch Fermat nutzte diese Eigenschaft der Quadrate.

Literatur