Faktorisierung einer Zahl nach Fermat


Faktorisierung bedeutet die Zerlegung eines Objekts in (echte) Faktoren.

Beispielsweise können natürliche Zahlen eindeutig in Primfaktoren zerlegt werden (s. auch unter Mathematik/Simulationen/Primzerlegung).
Moderne Verschlüsselungssysteme beruhen darauf, dass das Produkt zweier (Prim)Zahlen schnell berechnet werden kann, umgekehrt die Zerlegung aber deutlich zeitaufwendiger ist.

Auch algebraische Terme lassen sich häufig durch Ausklammern oder durch die Anwendung binomischer Formeln faktorisieren.

Ebenso können Polynome faktorisiert werden. Linearfaktoren zeigen dann die Nullstellen an.


Eine Faktorisierungsmethode für natürliche Zahlen wurde schon 1643 von  

Pierre de Fermat

französischer Mathematiker (1607-1665)

großer Fermat:
an+bn≠cn für n>2

kleiner Fermat:
ap≡ a mod p ; p Primzahl

Gesetz des (zeitlich) kürzesten Weges von Licht

beschrieben.

Sie beruht darauf, dass sich jede ungerade Zahl größer als 1 als Differenz zweier Quadrate darstellen lässt.

Eine Zahl z ist genau dann die Differenz zweier Quadratzahlen a, b ∈ N, wenn z in der Form

       z = d ⋅ ( d+2b)   mit    d, b ∈ N    darstellbar ist.

Beweis:

I. Sei z = a² - b² ; a, b ∈ N und a>b . Setze a := d + b, dann gilt: z = (d + b)² - b² = d² + 2bd + b² - b² = d² + 2bd = d ( d + 2b)

II. Sei z = d (d + 2b) darstellbar mit d, b ∈ N. Dann gilt: z = d² + 2db + b² - b² = (d + b)² - b² = a² - b² mit a = d + b

Mit d=1 und b durchläuft alle natürlichen Zahlen,erhält man alle ungeraden Zahlen.
Beispiele für gerade Zahlen: 6 oder 10 nicht darstellbar, 8 (= 32 - 12) darstellbar.

Die Faktorisierungsmethode von Fermat hat nur dann eine gute Laufzeit, wenn sich die zu zerlegende Zahl als Produkt annähernd gleich großer Faktoren darstellen lässt. Sie bildet zudem die Grundlage allgemeiner Faktorisierungsverfahren für große Zahlen.

Sei N die in die Faktoren p und q zu zerlegende Zahl. Der Algorithmus lässt sich dann wie folgt beschreiben:


Faktorisierung nach Fermat

  1. Falls N gerade, gib 2 und N/2 als Faktoren aus. Abbruch
  2. Bestimme die größtmögliche Zahl a kleiner als N.
  3. Wiederhole
  4.         Inkrementiere a
  5.         Berechne q = a ⋅ a - N
  6. bis (q ist Quadratzahl) oder (a>N)
  8. Ausgabe der Faktoren (a + q) sowie (a - q).

Beispiel: Sei N = 207

a q
14
15 225 - 207 = 18
16 256 - 207 = 49

49 ist eine Quadratzahl. Deshalb erfolgt die Ausgabe: 16 + 7 = 23 sowie 16 - 7 = 9. Es gilt 9 ⋅ 23 = 207.


Simulation:


Produkt zweier Zahlen: N =