|
Fermats Faktorisierungsmethode berechnet für eine ungerade Zahl n deren beide Teiler a und b so dass gilt
Fermats Methode ist geeignet wenn die Teiler a und b ähnlich groß sind. Fermats Methode macht sich zu Nutze dass jede positive ungerade Zahl n ausgedrückt werden kann als
Da dies nicht auf den ersten Blick ersichtlich ist, hier ein kurzer Beweis:
Das lässt sich mit Hilfe der binomischen Formeln auch schreiben als
n = a * b = x² - y² = (x + y) * (x - y)
Man kann erkennen,dass
Das lässt sich nach x bzw. y auflösen und umstellen zu
2x = a + b und 2y = a - b
Daraus folgt:
x = 1/2 * (a + b) und y = 1/2 * (a - b)
Das Ganze eingesetzt in obige Formel:
n = x² - y² = 1/4 * [(a + b)² - (a - b)²] = 1/4 * [(a² + 2ab + b²) - (a² - 2ab + b²)] = 1/4 * [a² + 2ab + b² - a² + 2ab - b²)] = 1/4 * 4ab = a * b
q.e.d.
Da n = x² - y² ist, sucht Fermats Methode also nach folgender Repräsentation für y² = x² - n. Dazu setzt es x auf √n. Dies genügt da immer ein Teiler von n größer als √n sein muss (Bsp.: 3 * 5 = 15. √15 = 3,87…).
An einem Beispiel wird Fermats Methode anschaulicher. Es sei n = 901 und gesucht sind die Teiler a und b so dass a * b = 901.
| Schritt |
Beschreibung |
x |
r = x² - n |
| 1 |
Zu Beginn wird x festgelegt als √n
und zur nächsten Ganzzahl aufgerundet. In diesem Fall: x = √n =
30,01… ≈ 31 |
31 |
|
| 2 |
Außerdem wird eine temporäre Variable r
eingeführt. Da nach einer Darstellung y² = x² - n gesucht wird, ist r =
x² - n. r ist also eine temporäre Variable für y² (r = y²) |
31 |
r = x² - n = 31² - 901 = 60 |
| 3 |
Es wird geprüft ob r eine Quadratzahl ist,
also ob es eine Darstellung y² = x² - n gibt |
√60 = 7,74…, d.h. 60
ist keine Quadratzahl. Daher wird x um eins erhöht. |
| 4 |
x wurde um eins erhöht. Es wird wieder r
berechnet und geprüft ob r eine Quadratzahl ist |
32 |
r = 32² - 901 = 123 |
| 5 |
Es wird geprüft ob r eine Quadratzahl ist,
also ob es eine Darstellung y² = x² - n gibt |
√123 = 11,09….., d.h.
123 ist keine Quadratzahl. Daher wird x um eins erhöht. |
| 6 |
x wurde um eins erhöht. Es wird wieder r
berechnet und geprüft ob r eine Quadratzahl ist |
33 |
r = 33² - 901 = 188 |
| 7 |
Es wird geprüft ob r eine Quadratzahl ist,
also ob es eine Darstellung y² = x² - n gibt |
√188 = 13,71….., d.h.
188 ist keine Quadratzahl. Daher wird x um eins erhöht. |
| 8 |
x wurde um eins erhöht. Es wird wieder r
berechnet und geprüft ob r eine Quadratzahl ist |
34 |
r = 34² - 901 = 255 |
| 9 |
Es wird geprüft ob r eine Quadratzahl ist,
also ob es eine Darstellung y² = x² - n gibt |
√255 = 15,96….., d.h.
255 ist keine Quadratzahl. Daher wird x um eins erhöht. |
| 10 |
x wurde um eins erhöht. Es wird wieder r
berechnet und geprüft ob r eine Quadratzahl ist |
35 |
r = 35² - 901 = 324 |
| 11 |
Es wird geprüft ob r eine Quadratzahl ist,
also ob es eine Darstellung y² = x² - n gibt |
√324 = 18,
d.h. 324 ist
eine Quadratzahl |
Da r = 324 eine Quadratzahl ist und r definiert wurde als r = y² lässt sich jetzt a und b bestimmen.
r = y² daraus folgt: y = 18
a und b sind definiert als
Dadurch können die Werte für a und b bestimmt werden:
a = x + y = 35 + 18 = 53
b = x - y = 35 - 18 = 17
Nützliche Links zu diesem Thema: Wikipedia und Wolfram Research
|