Faktorisieren großer Zahl 'N' bei bekanntem Phi(N)

Neue Frage »

tejubin Auf diesen Beitrag antworten »
Faktorisieren großer Zahl 'N' bei bekanntem Phi(N)
Meine Frage:
Hallo Leute, mir fehlt für folgende Aufgabe ein direkter Ansatz:

Wir sollen die Zahl

faktorisieren. Wir wissen den Wert der Phi-Funktion:





Meine Ideen:
Meine Idee (Hoffnung) war es, dass unser in der Form vorliegt und man mit schlichtem Umstellen von
zu nun idealerweise einfach die PQ-Formel benutzt. Dies scheitert aber leider, zumindest nach meinen Berechnungen..

Hättet ihr noch andere Ansätze?

*Edit: Diese Aufgabe soll mit einem handelsüblichen Taschenrechner zu lösen sein, hierfür hatte ich die Idee, um die Größe der Zahlen zu mindern, stehts den Ausdruck zu benutzen, da dieser in der PQ-Formeln zu benutzen wäre und viel kleiner wäre als selbst, da die ersten Ziffern der Zahlen gleich sind.
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von tejubin
Dies scheitert aber leider, zumindest nach meinen Berechnungen..

Dann versuch's nochmal, denn an sich ist das der richtige Weg.
tejubin Auf diesen Beitrag antworten »

Es ist doch aber auch möglich, dass mit paarweise verschiedenen und oder nicht?
tejubin Auf diesen Beitrag antworten »

Mit Matlab ist mir nun doch eine Lösung gelungen. Allerdings gibt mir die PQ-Formel ja zwei mögliche für den einen gesuchten Faktor. Die jeweils entstehenden ergeben somit zwei mögliche Faktorisierungen, die mir Matlab auch beide als richtig ausgibt, was ja an Rechenungenauigkeiten liegen muss. Matlab weißt mir beide Faktoren als ganzzahlig aus..
Mystic Auf diesen Beitrag antworten »

Nein, nicht im klassischen RSA... geschockt

Und wie deine Aufgabe mit einem gewöhnlichen TR gehen soll, sehe ich überhaupt nicht... Bist du sicher, dass damit nicht eine andere Aufgabe gemeint war? verwirrt

Edit: Zu deinem obigem Posting, das ich noch nicht gesehen hatte: Schon mal von der Formel

p*q=q*p

was gehört? Und sind das jetzt zwei wesentlich verschiedene Lösungen? verwirrt
tejubin Auf diesen Beitrag antworten »

Zitat:
Original von Mystic
Nein, nicht im klassischen RSA... geschockt


Was meinst du?

*edit:

Die beiden Faktorisierungen sehen wie folgt aus:

und
 
 
Mystic Auf diesen Beitrag antworten »

Ich meine, dass dies im RSA, wie es üblicherweise definiert ist, eben nicht erlaubt ist... Natürlich kann man rein theoretisch alle möglichen Verallgemeinerungen betrachten, nur spielen diese meines Wissens nach in der Praxis keine Rolle...

Edit: Mit deinen Faktorisierungen oben kann ich rein gar nichts anfangen... Du schon? verwirrt
tejubin Auf diesen Beitrag antworten »

Zitat:
Original von Mystic
Ich meine, dass dies im RSA, wie es üblicherweise definiert ist, eben nicht erlaubt ist... Natürlich kann man rein theoretisch alle möglichen Verallgemeinerungen betrachten, nur spielen diese meines Wissens nach in der Praxis keine Rolle...


Klar, aber von RSA war keine Rede. Klar wird sich dieses indirekt darauf beziehen (Da die Aufgabe innerhalb einer Kryptologie-VL gestellt wurde). Aufgabenstellung ist allerdings ohne Bezug.
tejubin Auf diesen Beitrag antworten »

Warum hast du deine Faktorisierung wieder zurückgenommen? Irgendwie muss ich doch etwas falsch gemacht haben.. hmm. Bei dir kommen ja wie es eigtl sein müsste wirklich nur zwei unwesentlich verschiedene Faktorisierungen heraus.
Mystic Auf diesen Beitrag antworten »

Warum rechnest du eigentlich approximativ? Das macht hier keinen Sinn... geschockt
tejubin Auf diesen Beitrag antworten »

Alles klar, jetzt bekomme ich die Lösung raus, die auch du, Mystic, zwischenzeitlich gepostet und wieder zurückgenommen hast.




OffTopic: Weiß jemand, wie ich die Anzahl der dargestellten Ziffern in Matlab ändere?

@Mystic
Ja ich weiß nicht, wie ich bei Matlab die Genauigkeite der Darstellung so ändere, dass mir die Zahlen genau angezeigt werden. Ich möchte ja nicht approximativ arbeiten.
Mystic Auf diesen Beitrag antworten »

Probier mal sowas in der Art round(x*10^20)/10^20 ...
tejubin Auf diesen Beitrag antworten »

Zitat:
Original von Mystic
Probier mal sowas in der Art round(x*10^20)/10^20 ...


Selbes Ergebnis.
Mystic Auf diesen Beitrag antworten »

Manchmal gibts eine Systemvariable digits, mit der man die Genauigkeit einstellen kann.. Weiß nicht, ob das hier zutrifft...
tejubin Auf diesen Beitrag antworten »

Die gibt es sogar, eine Änderung dieser ergibt leider nichts. Aber trotzdem super Dank an Dich für Deine Hilfe! Freude Ich werde dann wegen der Genauigkeit nochmal weiter recherchieren.
Shalec Auf diesen Beitrag antworten »

Hallo,
nur nochmal zum Matlab Problem (falls sich mal wieder jemand hierhin verirrt)

Die anzahl der Stellen lassen sich über fprintf erzwingen. Dies ist aber vom formatSpec abhängig. Ein kleines Beispiel:

code:
1:
2:
x=2^32;
fprintf('%30.4f\n', x)


Erklärung:
%30.4 -> 30 Vorkomma-, 4 Nachkommastellen (Nachkommasstellen sind systemspezifisch beschränkt, 64Bit ~ 19 Stellen, praktisch weniger.)
\n -> neue Zeile (für die Ausgabe ist dies wichtig sonst kommt alles in eine Zeile..)
die ' ' sind ebenfalls wichtig.


Also viel Erfolg allen, die sich dieser Aufgabe stellen. Übrigens:
Für die Programmierung ist folgende Zeile sehr interessant:
('%6.4f', pi) is equivalent to ('%*.*f', 6, 4, pi). ;-)

Shalec
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »