Chinesischer Restesatz

22.04.2020, 18:05

CRA

Chinesischer Restesatz

Meine Frage:
1) Wie berechnet man 2^51 mod 77 unter der Verwendung von 2^51 modulo der Primfaktoren von 77 per Chinesischen Restesatz?

Ich hab den CRA an sich Verstanden, wenn es mehrere Gleichungen gibt die man Lösen will, aber wie stelle ich die Infos die ich hier geschrieben habe so um das ich die Gleichungen lösen kann?

2) Wie berechnet man 37 mod 77 also b^2 mod 77 = 37 nach dem selben Verfahren?

LG

Meine Ideen:
77 = 7 * 11
(alle Gleich ab hier = Kongruent)
phi(7) = 6, phi(11) = 10
2^51 mod 7 = 2^(51 mod phi(7)) = 2^3 = 8 = 1

2^51 mod 11 = 2^(51 mod phi(11)) = 2^1 = 2

22.04.2020, 20:21

HAL 9000

Auf diesen Beitrag antworten »

Den Chinesischen Restsatz benötigst du im zweiten Schritt.

Im ersten Schritt berechest du $\begin{eqnarray*} 2^{51}\bmod p \end{eqnarray*}$ für $\begin{eqnarray*} p=7 \end{eqnarray*}$ sowie $\begin{eqnarray*} p=11 \end{eqnarray*}$ mit dem kleinen Fermat:

Laut dem kann man nämlich für nicht durch $\begin{eqnarray*} p \end{eqnarray*}$ teilbare $\begin{eqnarray*} a \end{eqnarray*}$ rechnen

$\begin{eqnarray*} a^{k(n-1)+m} = \left(a^{n-1}\right)^k\cdot a^m\equiv a^m\bmod p \end{eqnarray*}$ .

Das bedeutet hier $\begin{eqnarray*} 2^{51} = 2^{8\cdot 6+3}\equiv 2^3\equiv 1\bmod 7 \end{eqnarray*}$ sowie $\begin{eqnarray*} 2^{51}=2^{5\cdot 10+1}\equiv 2^1=2\bmod 11 \end{eqnarray*}$

(EDIT: Ah Ok, das hast du ja in deinem "Meine Ideen" ja auch schon in etwa so. Muss wohl mal meine Brille putzen...)

Und nun der zweite Schritt: Per Chinesischem Restsatz $\begin{eqnarray*} x\equiv 1\bmod 7 \end{eqnarray*}$ und $\begin{eqnarray*} x\equiv 2\bmod 11 \end{eqnarray*}$ zu der einen Lösung $\begin{eqnarray*} x\bmod 77 \end{eqnarray*}$ zusammenführen.

22.04.2020, 20:34

cra

Auf diesen Beitrag antworten »

also 1 habe ich mittlerweile selber löäsen können
aber beim wurzel teil komme ich tortzdem nicht weiter

x = 1 mod 7 und x = 2 mod 11
=> x = 36

aber ich bin mir nicht sicher was das beim wurzelziehen bringt Big Laugh

22.04.2020, 22:54

HAL 9000

Auf diesen Beitrag antworten »

Auch in der Zahlentheorie gilt: Vorsicht beim Wurzelziehen mit dem Vorzeichen!!! Tatsächlich bekommt man im ersten Schritt

a) $\begin{eqnarray*} b\equiv \pm 3\bmod 7 \end{eqnarray*}$
b) $\begin{eqnarray*} b\equiv \pm 2\bmod 11 \end{eqnarray*}$

Die beiden $\begin{eqnarray*} \pm \end{eqnarray*}$ sind unabhängig voneinander zu betrachten, demzufolge gibt es $\begin{eqnarray*} 2^2 = 4 \end{eqnarray*}$ Kombinationen von Systemen von zwei linearen Kongruenzen (die eine mod 7, die andere mod 11), mit denen du jeweils in den CRA gehst, und du erhältst damit am Ende vier Lösungen $\begin{eqnarray*} b\bmod 77 \end{eqnarray*}$ .

Etwas Zeit kannst du sparen, wenn du nur die beiden Lösungen von $\begin{eqnarray*} b\equiv \pm 3\bmod 7,b\equiv 2\bmod 11 \end{eqnarray*}$ bestimmst, und die beiden somit erhaltenen Lösungen $\begin{eqnarray*} b\bmod 77 \end{eqnarray*}$ durch die beiden $\begin{eqnarray*} -b\bmod 77 \end{eqnarray*}$ ergänzt - geht auch.

P.S.: Dein $\begin{eqnarray*} x = 36 \end{eqnarray*}$ als Lösung kann ich nicht nachvollziehen. unglücklich

23.04.2020, 06:43

CRA

Auf diesen Beitrag antworten »

das mit x = 36 bezog sich auf
x = 1 mod 7 und x = 2 mod 11
36 = 1 mod 7 und 36 = 2 mod 11

weil ich halt das bei dir so verstanden habe, dass ich diese gleichungen bräuchte

ich muss sagen ich weiß immer noch nicht wie du auf die b's gekommen bist :s

ich habe halt generell zu wurzelziehen in modulo nichts gefunden, und wüsste halt noch nciht mal wie man wurzel 37 mod 7 bspw löst

23.04.2020, 06:49

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von CRA
das mit x = 36 bezog sich auf
x = 1 mod 7 und x = 2 mod 11
36 = 1 mod 7 und 36 = 2 mod 11

Sehr clever, erst eine Zeile von Aufgabe 1 zu sprechen, dann eine zu Aufgabe 2, dann wieder zu Aufgabe 1 (ohne das zu erwähnen!) und direkt darauf beziehend von Wurzelziehen sprechen, so dass man annehmen MUSS, es geht um Aufgabe 2 ... bitte etwas strukturierter posten!!!

Was bei 2) zu tun ist, habe ich doch deutlich dargelegt: Statt einer sind 4 solche linearen Kongruenzsysteme zu lösen, wobei man aus Vorzeichensymmetriegründen sich auf 2 beschränken kann.

23.04.2020, 07:03

Elvis

Auf diesen Beitrag antworten »

36:11=3 Rest 3

Neue Frage »

Antworten »

Chinesischer Restesatz

Verwandte Themen