multiplikatives Inverses in Z 256

Re(13): multiplikatives Inverses in Z 256

Harti — Thu, 13 Dec 2001 23:26:45 GMT

Ja, danke. Der Professor hat zwar gemeint, dass man es auch allgemein hätte machen können

Re(12): multiplikatives Inverses in Z 256

Fly — Thu, 13 Dec 2001 22:47:46 GMT

Is' hoffentlich gut gegangen?

Re(11): multiplikatives Inverses in Z 256

Harti — Thu, 13 Dec 2001 15:00:42 GMT

Tut mir leid, da hab ich schon geschlafen - hatte heute um 8 eine Prüfung. Trotzdem danke - hab heute die Beispiele angekreuzt und das erste auch auf der Tafel gerechnet

Re(10): multiplikatives Inverses in Z 256

Fly — Thu, 13 Dec 2001 00:21:26 GMT

Nun, im Endeffekt hab ich nur gewusst dass es 2 Lösungen geben MUSS, und dass ihr Abstand zueinander 128 sein muss.

Warum?

Weil 128*14 mod 256=0 ist.

Dass 128*14 durch 256 teilbar ist ergibt sich trivialerweise daraus, dass das ja auch gleich 256*7 ist, was auch durch 256 teilbar ist.

Daraus lässt sich folgern, dass für uns interessant ist, was ist die höchste Potenz von 2, die in der zu untersuchenden Zahl (in unserem Fall 14) enthalten ist. Dies ist dann auch gleich der Anzahl der zu erwartenden Lösungen, ihr Abstand ist gleich (256 / Anzahl).

Immer davon ausgehend, dass es ÜBERHAUPT eine Lösung gibt, was ja nicht zwingendermassen der Fall ist! Ein multiplikatives Inverses z.B. können in dieser Restklasse nur ungerade Zahlen haben (weil aus x gerade folgt x*y (für y Element Z256) gerade, und daraus folgt, dass x*y mod 256 gerade und damit jedenfalls ungleich 1).

Sofern ich ned irgendwo 'n Denkfehler hab, is' auch schon ein bisserl früh und ich hab Kopfweh...

Re(9): multiplikatives Inverses in Z 256

Harti — Wed, 12 Dec 2001 18:59:07 GMT

Danke, ich hab bei 55 aufgehört und war glücklich ein ergebnis zu haben Kannst du mir jetzt noch kurz und verständlich sagen, wie du so schnell auf die Ergebnisse kommst?

Re(9): multiplikatives Inverses in Z 256

Fly — Wed, 12 Dec 2001 18:51:14 GMT

T'schuldigung, nicht nur f.a. x<128 aus Z256, sondern f.a. x aus Z256.

Re(8): multiplikatives Inverses in Z 256

Fly — Wed, 12 Dec 2001 18:49:56 GMT

Vorsicht, da gibt's 2 Lösungen in Z256!

14*55=770 mod 256=2
14*183=2562 mod 256=2

Genaugenommen ist f(x) = f(x+128) f. a. x<128 aus Z256, also bewegen wir uns in Z128. Wennst die Restklasse mod 128 nimmst statt 256 geht's also wieder.

Re(8): multiplikatives Inverses in Z 256

Harti — Wed, 12 Dec 2001 18:19:56 GMT

Hab dieses Beispiel auch schon gelöst - ich glaube, da war dein Geist bei mir

Danke und noch einen schönen Abend!

Re(7): multiplikatives Inverses in Z 256

Harti — Wed, 12 Dec 2001 18:10:21 GMT

Das bleibt keinem erspart, der nur irgendwie an Informatik vorbeistreift

Ich hab da jetzt noch eine Frage: Ich soll eine Lösung für die Gleichung 14*x=2 wieder in Z 256 finden. Muss ich da jetzt im Prinzip so vorgehen wie vorhin, nur das ich bis 2 herunterrechne?

Re(6): multiplikatives Inverses in Z 256

Fly — Wed, 12 Dec 2001 17:52:33 GMT

Heh. Ja das kenn' ich.

Re(5): multiplikatives Inverses in Z 256

Harti — Wed, 12 Dec 2001 17:45:09 GMT

Bin gerade noch am Verdauen von deiner langen Erklärung - danke dafür! Ich studiere Lehramt Informatik und da haben wir natürlich Mathematik VO und ein Proseminar dazu und je mehr Beispiele man ankreuzeln kann, desto besser ist es

Re(4): multiplikatives Inverses in Z 256

Fly — Wed, 12 Dec 2001 17:36:41 GMT

Mal 'ne ganz andere Frage, wofür brauchst es?

Re(3): multiplikatives Inverses in Z 256

Fly — Wed, 12 Dec 2001 17:35:42 GMT

Nun, das multiplikative INverse ist ja gegeben als x*y=y*x=1.

Naja, nehm ich mir die 15 und multiplizier mal mit der ersten (ganzen) Zahl, mit der's grösser als 256 wird (und damit "überschlägt"). Weil sonst wird's ja nur grösser, und 1 ist nun mal kleiner als 15. Also 15*18=270. Da wir in der Restklasse modulo 256 sind ist 270 also 14 (270 durch 256 und den Rest nehmen).

14 ist nicht 1. Wo gibt's den nächsten Überschlag?

Bei 15*35=525. 525 mod 256=13

Wir erkennen ein Schema.

15*18=14 (genauer: 15*(1+17)=14
15*(1+2*17)=13
15*(1+3*17)=12
...

führen wir dies konsequent fort erhalten wir

15*(1+14*17)=1

Naja, und 1+14*17 ist halt 239. Was uns noch dazu wunderbar in den Kram passt, weil das auch in Z256 ist. Sonst müssten wir halt nochmal das Ergebnis mod 256 rechnen.

Re(2): multiplikatives Inverses in Z 256

Harti — Wed, 12 Dec 2001 17:23:48 GMT

Danke für deine Lösung. Ich weiß jetzt nur nicht, wie du auf 239 kommst?

Re(3): multiplikatives Inverses in Z 256

Harti — Wed, 12 Dec 2001 17:21:23 GMT

Danke für den Tipp. Ich hab mich dort jetzt registriert, wenn ich aber auf Mathematik-Übungen gehe, werde ich ausgelogged und bin wieder anonymes User

Re: multiplikatives Inverses in Z 256

Fly — Wed, 12 Dec 2001 17:21:02 GMT

Hmm... also sofern's in der INformatik so is' wie in der Mathematik...

F=15, ges. Mul. Inv. in Z256.

=> 15*x mod 256=1 für x Elem. Z256

x=239

239*15=3585 mod 256 = 1

Re(2): multiplikatives Inverses in Z 256

Psychopath — Wed, 12 Dec 2001 16:43:39 GMT

Schon im Informatiker-Forum nachgefragt? (Klingt irgendwie nach Informatik..)
j.

Re: multiplikatives Inverses in Z 256

Harti — Wed, 12 Dec 2001 16:34:44 GMT

Wäre super, wenn jemand eine Idee hätte - ich muss das Beispiel nämlich morgen abgeben

multiplikatives Inverses in Z 256

Harti — Wed, 12 Dec 2001 12:35:17 GMT

Ich hab folgendes Problem:
Weiß einer einen Lösungsansatz, wie man das multiplikative Inverse des Bytes F = 15 in Z₂₅₆ finden kann?

Danke,