DLP mit CRT zu lösen

07.11.2013, 21:02

pablosen

DLP mit CRT zu lösen

Hallo

Um die Aufgabe...

Berechne x sodass $\begin{eqnarray*} 7^x=14750571 \mod 21495809 \end{eqnarray*}$ mit dem chinesischen Restsatz.

...zu lösen habe ich

$\begin{eqnarray*} \Phi(21495809)=2^{19}*41 \end{eqnarray*}$ also muss ich

$\begin{eqnarray*} 7^{x_1}=14750571=70507 \mod 2^{19} \end{eqnarray*}$ und
$\begin{eqnarray*} 7^{x_2}=1 \mod 41 \end{eqnarray*}$ lösen?

Einerseits sehe ich jetzt nicht, wie ich hier eine ganze Zahl bekommen soll, wenn ichs von Hand berechne (mit Mathematica kriege ich nur Zahlen mit vielen Kommastellen...und die Lösung sollte doch eigentlich ganzzahlig sein?) und andererseits sehe ich nicht ganz, wie ich dann folglich auf das Ergebnis kommen soll?

Weiss hier jemand, wie das gemeint ist?

07.11.2013, 21:20

HAL 9000

Auf diesen Beitrag antworten »

Vielleicht bin ich einfach zu müde, aber was hat die Lösung dieses Systems

Zitat:

Original von pablosen
...zu lösen habe ich

$\begin{eqnarray*} \Phi(21495809)=2^{19}*41 \end{eqnarray*}$ also muss ich

$\begin{eqnarray*} 7^{x_1}=14750571=70507 \mod 2^{19} \end{eqnarray*}$ und
$\begin{eqnarray*} 7^{x_2}=1 \mod 41 \end{eqnarray*}$ lösen?

mit der Originalaufgabe

$\begin{eqnarray*} 7^x \equiv 14750571 \bmod 2149580{\color{red}9} \end{eqnarray*}$

zu tun? So wie ich das verstehe, löst man damit allenfalls

$\begin{eqnarray*} 7^x \equiv 14750571 \bmod 2149580{\color{red}8} \end{eqnarray*}$ .

Mir ist schon klar, dass das irgendwie mit Fermat-Euler zu tun haben soll, aber doch nicht so - oder? verwirrt

07.11.2013, 21:33

pablosen

Auf diesen Beitrag antworten »

Hi HAL

Ja, gut da kannst du Recht haben. Wie muss hier dann aber das CRT angewendet werden?

07.11.2013, 21:42

HAL 9000

Auf diesen Beitrag antworten »

Ehrlich gesagt kenne ich keinerlei "Spezialmethoden" zur effizienteren Berechnung des diskreten Logarithmus - da musst du wohl auf die wahren Algebra/Zahlentheorie-Experten warten (vllt. Che Netzer, tmo, Mystic u.a.).

Ich würde es einfach per Brute force lösen (x=1312), aber das ist ja nun keine Kunst. Augenzwinkern

07.11.2013, 21:54

Captain Kirk

Auf diesen Beitrag antworten »

Das klingt für mich so als sollte x mittels Pohlig-Hellman berechnet werden.

07.11.2013, 22:20

pablosen

Auf diesen Beitrag antworten »

Hmmm aber dann müsste ich ja doch in $\begin{eqnarray*} \Phi(n)= 2^{19} *41 \end{eqnarray*}$ rechnen?

Aber muss ich dann das Problem $\begin{eqnarray*} 7^x = 1475057\textcolor{red}{\textbf{0}} \mod \Phi(n) \end{eqnarray*}$ betrachten oder wie läuft das hier?

edit: Nein, diese Gleichung führt nicht zum gleichen x. Wie muss ich das nun auf dieses $\begin{eqnarray*} \Phi(n)=2^{19}*41 \end{eqnarray*}$ ummünzen, um dann mit Papier und Kugelschreiber an die Aufgabe heranzugehen ohne Mathematica?

07.11.2013, 22:45

Captain Kirk

Auf diesen Beitrag antworten »

Wie wärs noch mit $\begin{eqnarray*} \color{red} 6\color{black}^x=15750571 \mod n \end{eqnarray*}$
dann hätten wir von allem mal sinnlos 1 abgezogen.

Natürlich läuft das nicht so:
Der Exponent muss mod $\begin{eqnarray*} \varphi (n) \end{eqnarray*}$ betrachtet werden, denn das ist ja gerade die Gruppenordnung.

Du berechnest $\begin{eqnarray*} 15750571^{2^{19}} =(7^{2^{19}})^a \mod n \end{eqnarray*}$
und $\begin{eqnarray*} 15750571^{41} =(7^{41})^b \mod n \end{eqnarray*}$
damit ist $\begin{eqnarray*} x\equiv a \mod 41 und x \equiv b \mod 2^{19} \end{eqnarray*}$

a und b kann man per Hand oder mit GiantStep-BabyStep o.ä. berechnen, bei Primzahlpotenzen kann man auch noch Verfeinerungen vornehmen.

Neue Frage »

Antworten »

DLP mit CRT zu lösen

Verwandte Themen