Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

ungelöstes Problem
Gehe zu Seite Zurück  1, 2, 3, 4
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> ungelöstes Problem
 
Autor Nachricht
Gauss
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 20.04.2005
Beiträge: 2063

BeitragVerfasst am: 07 Nov 2005 - 10:17:02    Titel:

Aber wieso versuchen es Mathematiker trotzdem einen guten Algorithmus zu finden? Vielleicht bezieht sich die Unterschranke nicht auf allumfassende Algorithmen sondern nur auf spezielle Formen von Algorithmen. Vielleicht gibt es ja auch numerische Lösungen wobei man, dann nur sehr wenige Fälle durchprobieren muss.
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 07 Nov 2005 - 12:59:18    Titel:

Zitat:
Aber wieso versuchen es Mathematiker trotzdem einen guten Algorithmus zu finden?


Also der aktuelle Stand ist ja, wenn ich mich nicht irre, dass bisher keiner eine Reduktion der Faktorisierung auf ein NP-vollständiges Problem angeben konnte. Bis vor kurzen glaubte mancher sogar, der Test ob eine Zahl in Binärdarstellung eine Primzahl ist, würde mindestens in NP-P liegen. Die Tatsache, dass das nicht wahr ist und andererseits die Abwesenheit eines Nachweises der NP-Vollständigkeit für Faktorisierung liefert sicherlich noch einen leichten Anstoß zur Suche nach effizienten Algorithmen. Was ich aber, mangels kompetenter Erfahrungen, meinerseits glaube, ist eher, dass man nach einer Reduktion auf SAT suchen sollte Smile Ein weiterer Punkt sind alternative Berechnungsmodelle: Es könnte sein, dass ein Wechsel auf ein "schnelleres" Berechnungsmodell als TM eine effiziente Lösung liefert.

Zitat:
Vielleicht bezieht sich die Unterschranke nicht auf allumfassende Algorithmen sondern nur auf spezielle Formen von Algorithmen.


Das tut sie immer Smile Untere Schranke: Berechnungsmodell x Aufwandsklasse x Problemstellung. Ob das Berechnungsmodell eingeschränkt war, weiß ich nicht mehr. Man sollte im Netz danach suchen. Es ist tatsächlich so, dass es vielmehr sein könnte, dass z.B.

{ w | w ist Binärdarstellung p*q für zwei Primzahlen p,q }

leichter faktorisiert werden Kann, als die grössere Klasse oder so. Ich würde übrigens genau die Probieren zu lösen.

Zitat:
Vielleicht gibt es ja auch numerische Lösungen wobei man, dann nur sehr wenige Fälle durchprobieren muss.


Und genau das meinte ich oben. Ich glaube, dass eine "praktische" Lösung, also eine mit der man tatsächlich noch zur eigenen Lebzeit eine Faktorisierung z.B. obiger Zahl erhalten kann, sollte einfach "effektiv" raten, wo die Lösung ist. Ist ja so, dass die Lage der Primzahlen nicht ganz so ungesetzmässig ist, wie man glaubt. Daher sollte man, wenn man sich auf wesentliche Merkmale beschränkt, z.B. angeben können, auf welchem Wegteil im Produkt zweier Primzahlen man die erste Marke setzen soll, damit die Division aufgeht.

Interessant ist in dem Kontext, warum ein Äquivalent zur binären Suche nicht funktioniert:

i) Fange mit [1,n] an
ii) Teile die Schranke in zwei gleiche Teile [a,a+floor((b-a)/2)[ und [a+ floor((b-a)/2),b]
iii) Prüfe, ob die Markierung links oder rechts sein soll mit einem Kriterium B(n) effektiv
iv) Arbeite weiter entweder auf dem linken oder auf dem rechten Intervall.

Das berechnen der Wurzel ist uninteressant. Was ist aber mit so einem B(n), welches schnell entscheiden kann, ob man links oder rechts sollte?
Gauss
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 20.04.2005
Beiträge: 2063

BeitragVerfasst am: 11 Nov 2005 - 14:57:22    Titel:

Hier sind die Primfaktoren von RSA-640

1634733 6458092538 4844313388 3865090859 8417836700 3309231218 1110852389 3331001045 0815121211 8167511579


1900871 2816648221 1312685157 3935413975 4718967899 6851549366 6638539088 0271038021 0449895719 1261465571
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 11 Nov 2005 - 15:21:57    Titel:

Ich habe nur noch eine Prüfung zu machen am Dienstag. Dann muss ich noch einen Artikel schreiben. Und dann setze ich mich und probiere mal ein paar Ansätze, die mir so während meiner Prüfungsvorbereitung in den Kopf gekommen sind.

Dieses Thema interessiert mich irgendwie sehr. Willst Du vielleicht mal was gemeinsam machen?
Gauss
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 20.04.2005
Beiträge: 2063

BeitragVerfasst am: 11 Nov 2005 - 15:24:38    Titel:

Ja na klar würde ichschon etwas gemeinsam machen, machen wir doch schon im Forum, oder?
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 11 Nov 2005 - 15:26:46    Titel:

Das ist doch Pipifax hier. Ich meine die Faktorisierung knacken und 20000$ absahnen. Und vielleicht was publizieren.
Gauss
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 20.04.2005
Beiträge: 2063

BeitragVerfasst am: 11 Nov 2005 - 15:28:26    Titel:

Aber die Zahl ist schon faktorisiert, da gibt es kein Geld mehr für.
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 11 Nov 2005 - 15:40:58    Titel:

Sry. Ich bin nicht auf dem Laufenden, weil ich mich gerade mit Verbandstheorie und theoretischer Informatik plage. Dann eben die nächste nicht faktorisierte.

Mich interessiert auch vor allem nicht eine spezielle Zahl, sondern die Kombination algebraischer und stochastischer Methoden zur Lösung des Problems. Es gibt ja dieses Thema im Gespräch P = NP, dass es eigentlich so sein könnte, dass für das allgemeine Problem (speiziell hier Faktorisierung) keine effizienten Lösungen existieren, aber für Fragmente des Problems trotzdem relativ schnelle Lösungen vorhanden sind. Ich habe speziell bei Faktorisierung ein Gefühl, dass man da was machen könnte, wenn hier ist der Spalt zwischen "trivial lösbar" und "extrem schwer lösbar" bei gleicher Problemlänge sehr groß. Ist aber alles Gelaber. Ich werde mir mal irgend ein krasses Buch über Primzahlen bei Gelegenheit mal reinziehen.
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> ungelöstes Problem
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Gehe zu Seite Zurück  1, 2, 3, 4
Seite 4 von 4

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum