Faktorisierungsmethode von Fer < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:46 Do 18.07.2013 | | Autor: | ThomasTT |
Ich lese immer sehr oft, dass bei der Faktorisierungsmethode von Fermat der Fall $n=3p$ der sogenannte "worst case" ist. Ich frage mich aber wieso das der Fall ist? Irgendwie überspringen alle Bücher, die ich zu dem Thema finde, diesen Schritt und beweisen diese Tatsache garnicht.
Über eine kleine Erläuterung wäre ich sehr dankbar.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:20 Do 18.07.2013 | | Autor: | leduart |
hallo
da das Verfahren etwa in der "Mitte" also bei [mm] \wurzel{3n} [/mm] anfängt, dauert es endlos, bis man bei dem faktor 3 ankommt, wenn n prim ist.
versuch mal nach fermat 30021 zu faktorisieren aber ohne zu benutzen , dass es ja durch 3 teilbar ist.
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:26 Do 18.07.2013 | | Autor: | ThomasTT |
Danker erstmal, doch meine Frage ist, gibt es dazu eine kleine mathematische Herleitung?
Einfach zu sagen "es dauert endlos wenn $n=3p$ für eine Primezahl $p$", ist ja nicht wirklich ein Beweis, sondern eine Beobachtung. :/
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:30 Do 18.07.2013 | | Autor: | leduart |
hallo
wenn du eine grosse Zahl 3p hast dauert es ca [mm] \sqrt{n}-3 [/mm] Schritte, bis du bei 3 bist:
warum ist das kein "beweis"
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:45 Do 18.07.2013 | | Autor: | ThomasTT |
Also meist startet man ja mit [mm] $x_0=\lceil\sqrt{n}\rceil$ [/mm] und geht dann alle Werte [mm] $x=x_0,\ x_0+1,\ x_0+2,\ \ldots$ [/mm] durch und prüft ob [mm] $\sqrt{x^2-n}$ [/mm] eine ganze Zahl ist.
Wenn nun $n=3p$ ist, dann ist [mm] $\sqrt{x^2-n}$ [/mm] erst eine ganze Zahl, wenn das letztmögliche [mm] $x=\lfloor\frac{n+9}{6}\rfloor$ [/mm] erreicht ist (z.B. laut Crandall's und Pomerance's Buch, Seite 226).
Doch wieso kann [mm] $\sqrt{x^2-n}$ [/mm] nie eine ganze Zahl sein bevor wir [mm] $x=\lfloor\frac{n+9}{6}\rfloor$ [/mm] erreichen und wo genau kommt diese Grenze her?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:56 Do 18.07.2013 | | Autor: | leduart |
Hallo
wenn du Fermats Methode hinschreibst, und schon weisst ,dass ein Faktor 3 ist dann musst du doch auch dahin kommen? worst case gilt nur für 3p nicht wenn n zusammengesetzt ist.
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:59 Do 18.07.2013 | | Autor: | ThomasTT |
Es tut mir leid, ich sehe einfach nicht wie ich dahin komme (manchmal sieht man den Wald vor lauter Bäumen nicht). Daher versuche ich ja hier eine Antwort zu erhalten.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:48 Do 18.07.2013 | | Autor: | leduart |
Hallo
dann versuch dich doch mal an meinem Beispiel, vielleicht fällt dann der Groschen.
Gruss leduart
|
|
|
|
