modulares radizieren(?)

16.03.2013, 15:07

frox

modulares radizieren(?)

Meine Frage:
ich bin mir nicht ganz sicher, ob ich im richtigen forum poste, aber ich habe ein problem, und zwar muss ich dringend rausfinden, wie man eine wurzel im modularen zahlenraum zieht
bsw. ist q gesucht bei q²=x (mod n)
ich schreibe am mittwoch eine klausur in kryptographie und finde keine lösung zu dem problem.
bitte helft mir :-(

Meine Ideen:
in meinem fall ist n ein produkt aus 2 großen primzahlen q und p
ein konkretes beispiel ist dabei: x=43; n=57 mit n=p*q=3*19
d.h. 10²=100=43 (mod 57)
also: ist sqrt(43) (mod 57) = 10 und -10
es müssen aber wohl noch 2 andere wurzeln herauskommen. was ich gern wüsste, ist wie man das macht. es müsste sich dann herausstellen, das mit sehr großem n auf grund der schwierigen faktorisierung es fast unmöglich wird das hinzubekommen. es muss also irgendwas mit den primfaktoren zutun haben.

16.03.2013, 15:19

watcher

Auf diesen Beitrag antworten »

Hallo,

das Finden von Wurzeln in Restklassenringen ist im Allgemeinen schwierig. Es kann passieren, dass einem nur Durchprobieren übrig bleibt.

Da du in deinem Post q doppelt belegt hast nenne ich die "Wurzel" a.
Hier hilft einem das n zusammengesetzt ist. Nach dem chinesischen Restsatz erfüllt a auch modulo p und q a²=x .

Hier ist auch der Grund zu suchen warum es bis zu vier Lösungen gibt:
$\begin{eqnarray*} \mathbb Z/p \mathbb Z \end{eqnarray*}$ , ebsenso für q, ist ein Körper, daher hat das Polynom X²-x höchstens 2 Nullstellen, modulo n ergeben sich also höchstens 4 mögliche Wurzeln.

Nützlich ist in diesem Zusammenhang auch das Jacobi/Legendre-Symbol um zu bestimmen ob eine Zahl Quadratzahl mod p ist oder nicht.

Zitat:

es müssen aber wohl noch 2 andere wurzeln herauskommen. was ich gern wüsste, ist wie man das macht. es müsste sich dann herausstellen, das mit sehr großem n auf grund der schwierigen faktorisierung es fast unmöglich wird das hinzubekommen. es muss also irgendwas mit den primfaktoren zutun haben.

Woher kommen diese ganzen Konjunktive?

16.03.2013, 15:42

frox

Auf diesen Beitrag antworten »

hallo watcher,
danke für die schnelle und informative antwort und entschuldige wegen der q-doppeltbelegung, das war keine absicht.
die konjunktive kommen vom kontext in dem mir diese aufgabe gestellt wird.
so wie du es sagst, besagt der chinesische restsatz (den ich mir noch genauer ansehen werde), dass aus

a² = x (mod n) mit n = p * q
dann folgt:
a² = x (mod p)
und
a² = x (mod q)

ist das richtig?

bei wikipedia heißt es:

Zitat:

"Zuerst bestimmt man die Primfaktorzerlegung

n = p_1^{m_1} * p_2^{m_2} * ... * p_{k}^{m_k}

des Moduls n und anschließend die Lösungen modulo der einzelnen Primzahlpotenzen p^m. Diese Lösungen setzt man schließlich unter Anwendung des Chinesischen Restsatzes zur gesuchten Lösung zusammen. "

nach deinem post macht das auch in gewisser weise sinn für mich, ich komme aber noch nicht ganz klar. könntest du mir evtl zeigen, wie man in meinem beispiel die beiden anderen wurzeln findet?

wiki-link

16.03.2013, 16:00

watcher

Auf diesen Beitrag antworten »

Finde die Lösungen von
$\begin{eqnarray*} X^2 \equiv 43 \mod 19 \end{eqnarray*}$ (bzw. 3)
Probieren wird hier das schnellste sein. Es gibt je 2 Lösungen.

Damit hast du 4 Fälle, etwa (das ist definitiv nicht die Lösung)
$\begin{eqnarray*} X\equiv 1 \mod 3 \text{ und } X\equiv 5 \mod 19 \end{eqnarray*}$
gesucht ist jetzt ein $\begin{eqnarray*} X\mod 57 \end{eqnarray*}$ das beides erfüllt.
Dank chin. Restsatz gibt's für diese sog. simultane Kongruenzen Lösungsformeln oder man probierts hier schnell per Hand:
Es muss $\begin{eqnarray*} X=5+k\cdot 19 \end{eqnarray*}$ sein, also kommen nur 5, 24, 43 in Frage letzere ist es.

Zitat:

so wie du es sagst, besagt der chinesische restsatz (den ich mir noch genauer ansehen werde), dass aus a² = x (mod n) mit n = p * q dann folgt: a² = x (mod p) und a² = x (mod q) ist das richtig?

Da habe ich mich mindestens unglücklich ausgedrückt. Das folgt bereits aus der Def. der Restklassenringe. Der chin. restsatz ist dafür da sich die lösungen zusammenzukleben.

16.03.2013, 17:49

frox

Auf diesen Beitrag antworten »

so, ich habe mir nun den chinesischen restsatz bei wikipedia reingezogen und auch ein paar videos bei youtube zum thema. ich habe verstanden was der chinesische restsatz ist, verstehe jedoch noch immer nicht wie ich damit zu einer lösungsformel komme, bzw. wie damit

Zitat:

"... die lösungen zusammenzuklebe...

.

durch probieren konnte ich finden:
a²=43=1 (mod 3) => a=2
und
a²=43=5 (mod 19) => a=10

nun ist aber 2 bzw -2 sicher nicht die lösung, denn 2² = 4 != 43 (mod 57)

was genau mache ich nun mit dem chinesischen restsatz um meine lösung zu finden? ich kann den zusammenhang leider noch nicht erkennen.

16.03.2013, 18:05

watcher

Auf diesen Beitrag antworten »

Zitat:

durch probieren konnte ich finden: a²=43=1 (mod 3) => a=2 und a²=43=5 (mod 19) => a=10 nun ist aber 2 bzw -2 sicher nicht die lösung, denn 2² = 4 != 43 (mod 57)

Netterweise haben quadratische Gleichung sobald sie eine Lösung auch eine (ziemlich banal zu findende) zweite Lösung.
Wieso sollte 2 oder -2 eine Lösung sein?
$\begin{eqnarray*} a \mod 57 \end{eqnarray*}$ ist eine Lösung, wenn $\begin{eqnarray*} a\equiv 2 \mod 3 \end{eqnarray*}$ und $\begin{eqnarray*} a\equiv 10 \mod 19 \end{eqnarray*}$ 2 bzw. -2 erfüllen die zweite Bedingung nicht.
Such mal nach natürlichen Zahlen die beide Bedingungen erfüllen.

Wie gesagt ist der chin. Restsatz nützlich für ein schematisches Berechnen der gesuchten Lösung.
Die entsprechende Formel steht in dem von dir verlinkten Wikipedia-Artikel.

Zum "zusammenkleben" der Lösung hab' ich doch extra ein Beispiel angegeben verwirrt

Ist da irgendwas unklar was ich gemacht habe.

Der chin. Restsatz ist für das konkrete Rechnen in solchen Aufgaben nicht so wichtig.
ich ging davon aus, dass dieser prinzipiell bekannt ist, ist er doch unerlässlich z.B. für einen sauberen Beweis, dass RSA funktioniert.

16.03.2013, 18:45

frox

Auf diesen Beitrag antworten »

hey, ich habe es verstanden, vieln dank für deine hilfe und entschuldige meine inkompetenz. das hier ist nicht wirklich mein metiers.

falls interesse an der lösung besteht:

a = 2 (mod 3)
a = 10 (mod 19)

a = 2 * (19 * a1) + 10 * (3 * a2) mit a1,a2 invers zu p=19 bzw. q=3

d.h.
19 * a1 = 1 (mod 3)
1 * a1 = 1 (mod 3) => a1 = 1
und
3 * a2 = 1 (mod 19) => a2 = 13

es gilt also:
a = 2 * (19 * 1) + 10 * (3 * 13) = 428 (mod p*q)
a = 29 (mod 57)

das ist die lösung, da:
29² = 43 (mod 57)

vielen dank :-)

Neue Frage »

Antworten »

modulares radizieren(?)

Verwandte Themen