Chinesischer Restsatz mit Lösungen als Potenz?

Neue Frage »

Hosenschlange Auf diesen Beitrag antworten »
Chinesischer Restsatz mit Lösungen als Potenz?
Mahlzeit,

gegeben sei eine Reihe von Kongruenzen

wobei und außerdem . Zusätzlich sei M das kleinste gemeinsame Vielfache aus .

Als Zahlenbeispiel sollen a aus [1, 3, 4] und m aus [5, 6, 7] bestehen:


Für den Fall k = 1 lässt sich ein Ergebnis durch den chinesischen Restsatz finden. In diesem Beispiel ist das kleinstmögliche . M ist das kgv (5, 6, 7) = 210. Alle weiteren Ergebnisse lassen sich dann durch , bestimmen, also 291, 501, 711, ...

Wie gehe ich nun aber vor, um die kleinstmögliche und nachfolgende Lösungen zu finden, wenn k > 1?
URL Auf diesen Beitrag antworten »
RE: Chinesischer Restsatz mit Lösungen als Potenz?
Ich glaube nicht, dass das im allgemeinen effizient möglich ist.
Du kannst zunächst das System der Kongruenzen für lösen. Die kleinste Lösung sei . Daraus folgt dann .

Jetzt werfen wir einen Blick auf die RSA-Verschlüsselung. Dort hat man einen öffentlichen Schlüssel , eine Nachricht und berechnet den Verschlüsselungstext . Dabei ist das Produkt zweier Primzahlen.

Wenn man dein Problem effizient lösen kann, dann kann man auch die Nachricht aus Verschlüsselungstext und effizient berechnen.
Hosenschlange Auf diesen Beitrag antworten »

Könnten wir u. U. k = 3 annehmen? Dafür muss ich allerdings obiges Beispiel ändern, da sich (am Computer getestet) keine Lösung findet.

Für den Fall k = 3 soll nun gelten:


Hier ist . Die weiteren Kandidaten sind was sich mit einem unkomplizierten Computerprogramm mittels Trial-and-Error berechnen lässt.

Wie kann ich aber ohne Computer an die Sache rangehen, um die Ergebnisse zu erhalten?
URL Auf diesen Beitrag antworten »

Ist für alle i, wie es bei RSA der Fall ist, dann bekommt man vom CRT direkt eine dritte Potenz geliefert. Das ist bekannt als "short/small public exponent attack".
Beispiel .CRT liefert .

Hier gibts einen praktischen Rechner für CRT smile

Ich komme übrigens auf nicht 8, wie du angegeben hast.
Mit welchem x hast du denn dein Beispiel gerechnet?
Hosenschlange Auf diesen Beitrag antworten »

In dem zweiten Beispiel von mir...wenn , dann .
Das ist das kleine Python-Programm dazu:
code:
1:
2:
3:
4:
M = 7 * 13 * 15
for i in range(1, M):
    if pow(i, 3, 7) == 1 and pow(i, 3, 13) == 1 and pow(i, 3, 15) == 8:
        print (i)
URL Auf diesen Beitrag antworten »

ok, verstanden.
CRT liefert ausgehend von den drei Kongruenzen die Lösung .

Die Suche im Bereich bis zum kgV der Moduln ist eben nicht effizient. Für den realistischen Fall der RSA-Verschlüsselung hat man es mit Modullängen von 3000bit zu tun.
Wenn ich mich recht erinnere, hat Bruce Schneier mal eine Entschlüsselungsaufgabe mit öffentlichem Exponenten 3 und zwei großen Moduln gestellt, die sehr lange ungelöst war. Wie der Stand jetzt ist, kann ich nicht sagen.
Eine dritte Wurzel zu berechnen ist einfach. Das ganze modulo einer großen Zahl zu tun ist hart. Deswegen glaube ich noch immer nicht, dass es einen einfachen Weg gibt (mal abgesehen vom Fall, dass x kleiner als jeder der Moduln ist).

Woher stammt eigentlich das Problem?
 
 
Hosenschlange Auf diesen Beitrag antworten »

Ich hatte das mal bei SPOJ oder UVa gefunden. Bei Project Euler müsste es ein ähnliches geben.
Hosenschlange Auf diesen Beitrag antworten »

Hab mal geschaut. Zumindest bei Euler ist es die 271, wenn auch abgewandelt....
URL Auf diesen Beitrag antworten »

Sei eine Primzahl und , also ein Erzeuger von .
Die Gleichung ist in eindeutig lösbar, wenn 3 kein Teiler von ist. Ist andernfalls eine Lösung, dann sind alle Lösungen.

Damit bekommt man beispielsweise aus die Lösungen in , also die
drei Kongruenzen und und .
Analog bekommt man aus drei Kongruenzen und aus bzw. je eine.
Wirft man jetzt neunmal den CRT an, bekommt man die Lösungen 92, 107, 302, 347, 737, 872, 932, 1082, 1262

project euler 271 kann man genauso erledigen. Dort ist es insofern einfacher, weil die Lösbarkeit von immer gegeben ist.
Hosenschlange Auf diesen Beitrag antworten »

Vielen Dank! Ich werde mir das mal anschauen Big Laugh
Neue Frage »
Antworten »



Verwandte Themen

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