Die Mathe-Redaktion - 24.10.2019 07:38 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 182 Gäste und 5 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Wauzi
Elementare Zahlentheorie » Zahlen - Darstellbarkeit » ... eine zwei-dimensionale Sicht auf Fermats Faktorisierungsalgorithmus
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich ... eine zwei-dimensionale Sicht auf Fermats Faktorisierungsalgorithmus
PriMath
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 16.05.2019
Mitteilungen: 8
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-09-17


Hallo MathFans !

neulich hat mir @Slash diesen Link zur Verfügung gestellt:
-->  Analytical Representations of Divisors of Integers.

Darin heißt es u.a.:
...
Moreover, numerical experiments suggest (???) that ALL (!!!) divisors lie on countable families of parabolas passing through the origin.
...

Ist dieser Zusammenhang in der Wissenschaft tatsächlich (noch) nicht anerkannt ?
Als (graphischen) 'Beweis' für die Korrektheit der obigen Aussage kann ich die zwei-dimensionale Darstellung des Faktorisierungsalgorithmus von Fermat anführen:

Hinweis:
--> Meine Darstellungen zeigen eine um '90° (gegen den Uhrzeiger-Sinn) gedrehte Teiler-Fläche' !
--> So lassen sich insbes. die Parabeln problemlos formell beschreiben.

Wikipedia-Link: hier  


Beispiel für die Zahl 161:


Nur WEIL alle Teiler(-Punkte) auf Parabeln liegen kann Fermat's Algorithmus funktionieren !

Viele Grüße !
PriMath



  Profil  Quote  Link auf diesen Beitrag Link
Ex_Senior
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-09-17


Herzlichen Glückwunsch, du hast die dritte binomische Formel entdeckt. :)

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 7588
Aus: Cuxhaven-Sahlenburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2019-09-17


Man muss auch bei Aritkeln aus dem arXiv vorsichtig sein. Wenn keine Veröffentlichung angegeben ist, ist es "nur" ein Preprint. Es macht in so einem Fall keinen Unterschied, ob der Artikel im arXiv oder auf einer privaten Homepage liegt. Dann ist der Autor anscheinend kein Profi, sonder - wie ich auch - ein Amatuer-Mathematiker. Die arXiv Kategorie ist GM=General Mathematics. Dort werded oft die Arbeiten von Amateuren eingeordnet. NT=Number Theory ist bei solchen Themen oft besser. Das alles sind natürlich keine Gründe für einen schlechten oder falschen Inhalt eines Artikels, man muss sie aber im Hinterkopf behalten. Auch ein fehlerloseses Profi-Preprint taugt nicht als Referenz. Das nur mal so allgemein zu arXiv Aritkeln. Das Gute am arXiv ist, dass dort so gut wie kein totaler Nonsens zu finden ist, wie z.B. bei viXra, obwohl auch dort jemand wie Simon Plouffe seine Arbeiten veröffentlicht.



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4972
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2019-09-17


Ich würde jetzt eher einen Zusammenhang zum Wurzelsatz von Vieta sehen (s. hier). Aus einer Produktdarstellung
\[n=a\cdot b \quad (a,b\in\mathbb N^*)\] einer ganzen Zahl $n>0$ folgt natürlich sofort, dass die Gleichung
\[n=a\cdot b=-x^2+(a+b)x\] die beiden eindeutigen Lösungen $x=a$ und $x=b$ hat.

Das Problem ist halt wieder einmal, dass diese Faktorisierungsmethode - sofern man davon überhaupt sprechen kann, da es ja mehr ein "Probieren" ist - wirklich nur für kleine Zahlen funktioniert, da man ja den Koeffizienten von $x$ nicht kennt und man kann ja für wirklich große $x$ mit Dutzenden oder gar hunderten Stellen jetzt wohl unmöglich alle in Frage kommenden Parabeln durchprobieren kann.

Auch einen Zusammenhang zur Fermatschen Faktorisierungsmethode sehe ich übrigens überhaupt nicht, da deren Grundidee, dass nämlich jeder Produktdarstellung $n=a\cdot b$ wie oben, wenn man o.B.d.A. noch $a\ge b>0$ voraussetzt, in umkehrbar eindeutiger Weise eine Darstellung $n=x^2-y^2\ (x> y\ge 0)$ als Differenz von zwei Quadratzahlen zugeordnet ist, hier ja überhaupt nicht verwendet, sondern gewissermaßen nur nebenbei erwähnt wird.

[Die Antwort wurde nach Beitrag No.1 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
Ex_Senior
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2019-09-17


Hm? Fermat-Faktorisierung asiert auf der trivialen Tatsache <math>(x-y)(x+y)=x^2-y^2</math>, sodass man, wenn man für eine nat- Zahl <math>n</math> die Darstellung als Differenz zweier verschiedener Quadratzahlen gefunden hat, daraus auch eine Faktorisierung ableitbar ist.

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
PriMath
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 16.05.2019
Mitteilungen: 8
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2019-09-17


Hallo MathFans !

Na selbstverständlich geht's um die 3. binomische Formel (und damit um die Differenz von Quadraten)!
ABER, nach meiner Ansicht handelt es sich bei der (Standard-)Teiler-Fläche um eine FUNDAMENTALE mathematische Struktur, aus der u.a. die 3. binomische Formel HERVOR GEHT (und nicht umgekehrt).

Die Analogie der Teiler-Suche via Parabel-Bewegung zur Fermat'schen Methode kann natürlich auch iterativ zur Beispiel-Zahl 161 aufgezeigt werden:

1. Fermat-Iteration
x=13 --> Parabel -x^2 + 2*13x
r=13^2-161   = 8 (kein Quadrat)

2. Fermat-Iteration
x=14 --> Parabel -x^2 + 2*14x
r=14^2-161   = 27 (kein Quadrat)

3. Fermat-Iteration
x=15 --> Parabel -x^2 + 2*15x
r=15^2-161   = 64 = 8^2  <-- Lösung: (15-8) * (15+8) = 7*23 !

In der Teilerfläche finden sich noch Parabeln 'dazwischen' (bei x=13.5, 14.5 u.s.w.). Diese sind aber irrelevant, weil ALLE Teiler-Punkte auf diesen Parabeln GERADE sind.

OK, es mag eine 'Henne <--> Ei'-Diskussion sein, aber für meine Begriffe steht die Suche nach STRUKTUREN im Zentrum der mathematischen Forschung. In diesem Sinne sind m.E. die Teilerflächen sehr Aufschluss-reiche STRUKTUR-DARSTELLUNGEN.

Ich bin überzeugt davon, dass GRAPHISCHE Stuktur-Darstellungen erhebliche didaktische Vorteile mit sich bringen. So kann man Zusammenhänge sogar SEHEN!

Viele Grüße !
PriMath

P.s.: Wenn jemand interaktiv mal rumprobieren möchte ...
hier

[Die Antwort wurde nach Beitrag No.3 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4972
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2019-09-17


2019-09-17 15:57 - cyrix in Beitrag No. 4 schreibt:
Hm? Fermat-Faktorisierung asiert auf der trivialen Tatsache <math>(x-y)(x+y)=x^2-y^2</math>, sodass man, wenn man für eine nat- Zahl <math>n</math> die Darstellung als Differenz zweier verschiedener Quadratzahlen gefunden hat, daraus auch eine Faktorisierung ableitbar ist.

Ja schon, aber wie ich oben schon sagte, hat das Ganze mit der Fermatschen Faktorisierungsmethode ja überhaupt nichts zu tun, sondern basiert zur Gänze auf dem Wurzelsatz von Vieta. Oder wo siehst du einen echten Bezug zur dritten binomischen Formel bei seiner "Methode"?

[Die Antwort wurde nach Beitrag No.4 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4972
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2019-09-17


2019-09-17 16:20 - PriMath in Beitrag No. 5 schreibt:
Die Analogie der Teiler-Suche via Parabel-Bewegung zur Fermat'schen Methode kann natürlich auch iterativ zur Beispiel-Zahl 161 aufgezeigt werden:

1. Fermat-Iteration
x=13 --> Parabel -x^2 + 2*13x
r=13^2-161   = 8 (kein Quadrat)

2. Fermat-Iteration
x=14 --> Parabel -x^2 + 2*14x
r=14^2-161   = 27 (kein Quadrat)

3. Fermat-Iteration
x=15 --> Parabel -x^2 + 2*15x
r=15^2-161   = 64 = 8^2  <-- Lösung: (15-8) * (15+8) = 7*23 !

Also ich habe deine Methode wie folgt verstanden, bitte korrigiere mich wenn ich damit falsch liegen sollte:

1. Du wählst der Reihe nach Parabeln $y=-x^2+px$ beginnend mit $p=2\lceil \sqrt n\rceil$ und erhöhst bei einem "Mißerfolg" (wird noch in 2. definiert) den Wert von $p$ um jeweils 2. (Hier wird vorausgesetzt, dass $n$ ungerade ist, was dann natürlich auch für seine Teiler zutrifft!)

2. Dabei schaust du jeweils in der Graphik für die Parabel nach, ob die horizontale Gerade $y=n$ die Parabel in Punkten mit ganzzahligen Koordinaten schneidet (nach "Augenmaß" oder macht das ein Programm für dich?). Wenn dies der Fall ist, was also dann ein "Erfolg" hier wäre,  aber sehr lange dauern kann, bis man so eine Parabel findet, dann bist du fertig und die $x$-Koordinaten der beiden Schnittpunkte ergeben dann ein Paar von Komplementärteilern von $n$.

Falls dies im wesentlichen so stimmt, dann hat das aber absolut nichts mit der Fermatschen Faktorisierungsmethode zu tun, welche du oben in dem Beispiel richtig dargestellt hast, die aber ersichtlich ganz anders funktioniert! Ok, eine kleine Gemeinsamkeit gibt es doch: Die Fermatsche Faktorisierungsmethode ist normalerweise grottenschlecht und schlicht und einfach zu vergessen, außer in dem Fall, dass es ein Paar von Komplementärteilern gibt, welche "sehr nahe" bei $\sqrt n$ liegen. In diesem Fall würdest du auch einen "passenden" Koeffizienten $p$ in der Parabelgleichung nach nur wenigen Fehlversuchen finden. Bei wirklich großen Zahlen ist das aber so selten wie ein Sechser im Lotto, was sage ich, noch viel, viel seltener!   biggrin



  Profil  Quote  Link auf diesen Beitrag Link
PriMath
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 16.05.2019
Mitteilungen: 8
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2019-09-18


Hallo @weird !

Am Anfang hatte ich tatsächlich die Schnittpunkte der Parabeln mit der Geraden $y=n$ umständlich errechnet - bis ich den Zusammenhang zu Fermat's Methode erkannt hab :-)

Eine wichtige Information hab ich dir unbeabsichtigt vorenthalten!
--> Es ist ja über die 1. Ableitung problemlos möglich die Scheitelpunkte (SP) der Parabeln $y=-x^2+px$ zu ermitteln.
--> Die Y-Werte dieser Scheitelpunkte (ohne die Parabelm mit ungeradem $p$) sind genau die Quadrate die Fermat verwendet !
--> Die Schnittpunkte der Parabeln mit der Geraden $y=n$ ergeben sich dann ganz einfach über die Subtraktion bzw. Addition der Wurzel der Differenz.


Beispiel zur Zahl 161:
1. Fermat-Iteration
$x=13$ --> Parabel $-x^2 + 2*13x$ --> Scheitelpunkt $SP(13,13^2)$
Differenz $13^2-161   = 8$ (kein Quadrat)
Schnittpunkte: $S1 = (13- \sqrt 8,161)$ $S2 = (13+ \sqrt 8,161)$

2. Fermat-Iteration
$x=14$ --> Parabel $-x^2 + 2*14x$ --> Scheitelpunkt $SP(14,14^2)$
Differenz $14^2-161   = 27$ (kein Quadrat)
Schnittpunkte: $S1 = (14 - \sqrt 27,161)$ $S2 = (14 + \sqrt 27,161)$

3. Fermat-Iteration
$x=15$ --> Parabel $-x^2 + 2*15x$ --> Scheitelpunkt $SP(15,15^2)$
Differenz $15^2-161   = 64$ (Quadrat !)
Schnittpunkte: $S1 = (15 - \sqrt 64,161)$ $S2 = (15 + \sqrt 64,161)$
Lösung ==> $(15-8) * (15+8) = 7*23$

Es IST wirklich das SELBE !
Und es ist deshalb das selbe, weil die Struktur der Teilerfläche es erzwingt !

Fermat's Methode ist definitiv NICHT effizient für allgemeine Faktorisierungsprobleme. Aber in Kombination mit der Probe-Division kann man am 'linken und rechten Ende' des Lösungsraums $\sqrt n$ schon mal deutlich was abzwacken.
Darauf aufbauend hat dann Lehman eine weiter entwickelte Methode vorgestellt, aber das ist dann nochmal ne andere Geschichte ...

Viele Grüße !
PriMath



  Profil  Quote  Link auf diesen Beitrag Link
PriMath hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]