Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

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


Anmeldungsdatum: 05.07.2005
Beiträge: 517

BeitragVerfasst am: 04 Nov 2005 - 16:23:43    Titel:

ja ich hab so nen programm geschrieben, was zu einer gegebenen zahl z zwei zahlen liefert, deren produkt z als endziffern hat. hab aber nur mal getestet, obs funktioniert, und es nicht auf zahlenbereiche über integer oder sowas "normales" ausgeweitet.
man kann auf so zahlen halt konstruktiv kommen, und muss nichts ausprobieren. deshalb geht es sehr schnell.

und ja, es gibt natürlich unendlich viele solche zahlen Smile habe dann mal geschaut, ob man ein muster erkennt, bei den zahlenteilen, die vor z stehen, aber nix gesehen. weil man sucht ja sozusagen ein solches zahlenpaar, wo dann beim produkt einfach als spezialfall die 0 vornedran steht.


Zuletzt bearbeitet von yushoor am 04 Nov 2005 - 16:25:23, insgesamt einmal bearbeitet
Gauss
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 20.04.2005
Beiträge: 2063

BeitragVerfasst am: 04 Nov 2005 - 16:24:52    Titel:

Man müsste soetwas mal in Maple programmieren, der rechnet ja auch mit beliebig langen Zahlen.
Gauss
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 20.04.2005
Beiträge: 2063

BeitragVerfasst am: 05 Nov 2005 - 12:11:29    Titel:

Ich habe dieses Programm mal geschrieben, der Nachteil ist, dass sich nach jedem Schritt die Anzahl der Paare verzehnfachen. D.h. der Rechenaufwand wäre

O(10^n) n-Stellenzahl, also nach dem 7-8 Schritt die Rechenzeit viel zu groß wird.
yushoor
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 05.07.2005
Beiträge: 517

BeitragVerfasst am: 05 Nov 2005 - 13:54:46    Titel:

also bei meinem programm gehe ich so vor, dass ich abgesehen von der letzten ziffer, den einen faktor vorgebe und der andere dann ausgerechnet wird (ist dann eindeutig).
dann kann man zb ne schleife über den vorgegebenen faktor machen und so viele verschiedene möglichkeiten sehen.

zb: gesucht a*b mod 10^9 = 123456789

ergibt bei mir diese ausgabe für (a und b), rechenzeit etwa gleich null:
1->123456789
11->465768799
21->720164609
31->874950219
41->51791629
51->237714839
61->297105849
71->663710659
81->112635269
91->12345679
101->456667889
111->676787899
121->133251709
131->687965319
141->256194729
151->338565939
161->833064949
171->527037759
181->669190369
191->21588779
201->791658989
usw, die anderen möglichkeiten für endziffern dann getrennt (sind ja meist nich viele).

zb ist 201*991658989 = 159123456789

oder für ein echtes produkt von 2 primzahlen, nämlich 210532831 findet man dann:
.....
7163->815190637
7173->286380947
7183->311319857
7193->439901367
7203->298099477
7213->879968187
7223->599641497
7233->703333407
7243->641337917
7253->29027
7263->593860737
7273->317367047
7283->357161957
7293->363939467
7303->184473577
7313->753618287
7323->746307597
7333->589555507
7343->434456017
7353->688183127
......
Gauss
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 20.04.2005
Beiträge: 2063

BeitragVerfasst am: 05 Nov 2005 - 14:03:55    Titel:

Aber wenn du eine Zahl mit z.B. 100 Stellen faktorisieren willst, dann musst du ja Schrittweise vorgehen und für jedes gefundene Paar wieder Lösungsvorschläge bringen, das verbraucht doch zu viel Speicher und die Rechenzeit ist, dann doch auch exponentiell oder?
yushoor
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 05.07.2005
Beiträge: 517

BeitragVerfasst am: 05 Nov 2005 - 14:32:31    Titel:

ja klar - ist keine rechenzeit ersparnis zum normalen "probieren" denke ich.
man findet halt für jedes gegebene a (mit passender endziffer) ein b, so dass die letzten 100 stellen von a*b mit dem gegebenen produkt z übereinstimmen.
Gauss
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 20.04.2005
Beiträge: 2063

BeitragVerfasst am: 05 Nov 2005 - 14:38:19    Titel:

Ich bin dabei eine andere Methode zu entwickeln:

Ansatz:

pq=RSA

(a-b)(a+b)=a²-b²=RSA

=> a=0 mod 2 und b=1 mod 2 setze a=2c,b=2d+1

c²-d²-d=(RSA+1)/4

Diese Zahl kann man in Primfaktoren zerlegen, also muss man "nur" noch diese diophantische Gleichung lösen.
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 05 Nov 2005 - 16:40:32    Titel:

Mal als Denkanstoß: Ich habe leider zur Zeit überhaupt keine Zeit für anspruchsvolle Aufgaben, aber ich habe mal daran gedacht, was zur Primzahlenfaktorisierung mit Soft-Computing Methoden zu überlegen. Natürlich kann man nicht einem KNN nicht irgendwie Zahlen vorwerfen und deren Zerlegungen und erwarten, dass es lernen kann einer Zahl ihre Primfaktoren anzusehen. Das ist sinnlos. Aber man kann eine Zahl anhand von geschickten (billigen) Transformationen in einen höhererdimensionalen Merkmalsraum transofrmieren, in dem Zahlen mit ähnlichen Zerlegungen bezüglich eines Maßes nahe aneinander liegen. Die Ähnlichkeit kann mit einem KNN gelernt werden. Ich bin davon überzeugt, dass unter geeigneten Transoformationen auch große Zahlen zu knacken sind. Was haltet Ihr davon?
Gauss
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 20.04.2005
Beiträge: 2063

BeitragVerfasst am: 05 Nov 2005 - 16:45:43    Titel:

So was ähnliches versuche ich ja, ich transformiere die Zahl auf ein Problem welches (scheinbar) einfacher zu lösen ist, die diophantische Gleichung. Der Vorteil ist das Ergebnis kann ich in Primfaktoren darstellen.
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 05 Nov 2005 - 16:53:53    Titel:

Die Komplexitätstheorie lehrt uns: Das Problem der Faktorisierung ist inhärent schwer. Ich habe irgendwie ein Gefühl gehört zu haben, dass es nichttriviale Unterschranken für Faktorisierung gibt, die sehr sehr groß sind. Was ich damit aussagen will: Jeglicher Versuch das Problem exakt zahlentheoretisch anzugehen, münden algorithmisch in nicht effizienten Lösungen, die praktisch völlig sinnlos sind. Ich bewerte es als die Suche nach einem perpetuum mobile, wie man es im Physik Forum des öfteren vorfindet. Was ich oben vorgeschlagen habe, ist ein nicht exakter Ansatz. Ein "Hint" sozusagen, wo genauer zu suchen ist.
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  Weiter
Seite 3 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