Verschoben! Zahlentheorie - modulo-Rechnung bei sehr großen Zahlen

21.05.2013, 10:26

Infernius

Auf diesen Beitrag antworten »

Zahlentheorie - modulo-Rechnung bei sehr großen Zahlen

Hallo liebe Community,

ich bin gerade dabei meine Facharbeit zu schreiben und pfeife quasi auf dem letzten Loch. Nun bin ich dabei meine Nachricht (8) zu verschlüsseln und weiß absolut nicht weiter.

Ich müsste berechnen 8^29 mod 221

Weiß aber absolut nicht wie ich das anstellen soll.

Vielleicht kann mir jemand helfen
Danke

21.05.2013, 10:36

RavenOnJ

Auf diesen Beitrag antworten »

Dann bestimme mal $\begin{eqnarray*} 8^x\!\!\!\! \mod 221 \end{eqnarray*}$ für ein paar kleine x. Es gibt eine kleine Zahl x mit $\begin{eqnarray*} 8^x = 1\!\!\!\! \mod 221 \end{eqnarray*}$ .

21.05.2013, 10:54

Infernius

Auf diesen Beitrag antworten »

Tut mir echt leid...Aber...Versteh ich nicht Hammer

Hammer

21.05.2013, 11:25

Infernius

Auf diesen Beitrag antworten »

OK. Teils verstanden. Ich soll also nicht direkt mit 8^29 anfangen, sondern erstmal kleinere x suchen, die ich dann hinterher zu 8^29 zusammenfassen kann.

Aber wie mach ich das?

21.05.2013, 12:00

RavenOnJ

Auf diesen Beitrag antworten »

Es gilt: $\begin{eqnarray*} a = x\!\!\!\!\mod n\land b = y\!\!\!\!\mod n \Rightarrow ab = xy\!\!\!\!\mod n \end{eqnarray*}$

Wenn du also ein k findest mit $\begin{eqnarray*} 8^k = 1\!\!\!\!\mod 221 \end{eqnarray*}$ , dann gilt auch $\begin{eqnarray*} 8^{nk} = 1\!\!\!\!\mod 221,n\in\mathbb N \end{eqnarray*}$ und $\begin{eqnarray*} 8^{nk+m} = 8^m\!\!\!\!\mod 221,n\in\mathbb N \end{eqnarray*}$ .

Edit: Das ganze Thema gehört übrigens zur Algebra, sollte also weg aus "Sonstiges"

21.05.2013, 12:30

Infernius

Auf diesen Beitrag antworten »

Ok. Also muss ich nicht direkt nach

8^29 mod 221

aber wie berechne ich nun diese $\begin{eqnarray*} 8^k = 1 mod 221 \end{eqnarray*}$ . Also..wie berechne ich das k...

Das ist das was ich noch nicht ganz verstehe

Anzeige

21.05.2013, 13:18

ollie3

Auf diesen Beitrag antworten »

hallo,
das k kann man nicht berechnen, sondern muss es durch probieren ermitteln.
Ich verrate schonmal, das k zwischen 1 und 10 liegt.
Nun berechne mal 8^1, 8^2, u.s.w. und nutze zwischenergebnisse aus,
damit die zahlen nicht zu hoch werden...
gruss ollie3

21.05.2013, 13:49

Infernius

Auf diesen Beitrag antworten »

Zitat:

Original von ollie3
hallo,
das k kann man nicht berechnen, sondern muss es durch probieren ermitteln.
Ich verrate schonmal, das k zwischen 1 und 10 liegt.
Nun berechne mal 8^1, 8^2, u.s.w. und nutze zwischenergebnisse aus,
damit die zahlen nicht zu hoch werden...
gruss ollie3

Ist es $\begin{eqnarray*} 8^8 \end{eqnarray*}$ Big Laugh

Big Laugh

21.05.2013, 13:55

RavenOnJ

Auf diesen Beitrag antworten »

ja. Und weiter?

21.05.2013, 13:58

Infernius

Auf diesen Beitrag antworten »

Jetzt weiß ich, dass $\begin{eqnarray*} 8^8 \end{eqnarray*}$ kongruent ist zu 8^29 mod 221

....

Weiter weiß ich nicht..Weiß gerade nicht was ich die letzten 18 Seiten meiner Facharbeit geschrieben habe..

21.05.2013, 13:59

RavenOnJ

Auf diesen Beitrag antworten »

Zitat:

Original von Infernius
Jetzt weiß ich, dass $\begin{eqnarray*} 8^8 \end{eqnarray*}$ kongruent ist zu 8^29 mod 221

....

Weiter weiß ich nicht..Weiß gerade nicht was ich die letzten 18 Seiten meiner Facharbeit geschrieben habe..

verwirrt

wie das?

21.05.2013, 14:02

Infernius

Auf diesen Beitrag antworten »

Sry...hab da wohl was verwechselt.. Big Laugh

Big Laugh

Aber so richtig weiß ich nicht was mir das nun bringt...

Jetzt weiß ich, dass 8^8 = 1 mod 221 .. aber immer noch nicht was nun der rest von 8^29 ist wenn ich es durch 221 teile..

21.05.2013, 14:03

RavenOnJ

Auf diesen Beitrag antworten »

dann lies dir das nochmal durch:

Zitat:

Original von RavenOnJ
Es gilt: $\begin{eqnarray*} a = x\!\!\!\!\mod n\land b = y\!\!\!\!\mod n \Rightarrow ab = xy\!\!\!\!\mod n \end{eqnarray*}$

Wenn du also ein k findest mit $\begin{eqnarray*} 8^k = 1\!\!\!\!\mod 221 \end{eqnarray*}$ , dann gilt auch $\begin{eqnarray*} 8^{nk} = 1\!\!\!\!\mod 221,n\in\mathbb N \end{eqnarray*}$ und $\begin{eqnarray*} 8^{nk+m} = 8^m\!\!\!\!\mod 221,n\in\mathbb N \end{eqnarray*}$ .

21.05.2013, 14:08

Infernius

Auf diesen Beitrag antworten »

OK.

Ich hab herausgefunden, dass $\begin{eqnarray*} 8^8 = 1 mod 221 \end{eqnarray*}$

dadurch gilt auch 8^(8*3+5) = $\begin{eqnarray*} 8^5 mod 221 \end{eqnarray*}$

Oder?? smile

smile

21.05.2013, 14:17

ollie3

Auf diesen Beitrag antworten »

hallo,
ja, das ist richtig. Freude

Freude

Jetzt musst du also nur noch 8^5 mod 221 berechnen.
gruss ollie3

21.05.2013, 14:21

Infernius

Auf diesen Beitrag antworten »

Alsooo

8^29 mod 221 = 63 smile

smile

21.05.2013, 14:40

mYthos

Auf diesen Beitrag antworten »

Da hab' ich was anderes ...

mY+

21.05.2013, 14:45

ollie3

Auf diesen Beitrag antworten »

hallo,
ich auch Big Laugh

Big Laugh

gruss ollie3

21.05.2013, 15:21

RavenOnJ

Auf diesen Beitrag antworten »

unglücklich

ich auch

21.05.2013, 20:30

Infernius

Auf diesen Beitrag antworten »

8^5 mod 221..Da komm ich auf 63

Weil

8^5 sind 32768 dass durch 211 geteilt, dann kommt man darauf das 211 155 mal ganz reinpasst..Also

32768 - (155*211) = 63 ..

Wo ist den nun mein Fehler

21.05.2013, 21:12

mYthos

Auf diesen Beitrag antworten »

Du solltest nicht durch 211, sondern durch 221 teilen ...

mY+

21.05.2013, 21:14

Infernius

Auf diesen Beitrag antworten »

Stimmt.

Ich bin dumm...

Kommt 60 raus ? smile

smile

21.05.2013, 21:17

mYthos

Auf diesen Beitrag antworten »

Japp!

smile

21.05.2013, 21:17

Infernius

Auf diesen Beitrag antworten »

WHeeyyyyyy

smile

smile

smile

smile

smile

smile

smile

DANKE!!!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »