Euklidischer Algorithmus < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:38 Do 19.02.2009 | | Autor: | Sneiper |
| Aufgabe | 7*d = 1(mod160)
d = 23 |
Hallo,
ich habe dieses Beispiel in einem Buch zur Verschlüsselung von ASCII-Codes gefunden. Jedoch weiß ich nicht wie d=23 zustande kommt. Die Formel habe ich bereits nach d umgestellt:
d = [mm] \bruch{1(mod160)}{7}
[/mm]
Mein Ergebnis ist demnach jedoch: [mm] d=\bruch{1}{7}
[/mm]
Rechne ich (mod160) eventuell falsch?
MfG und Danke im voraus!
Sneiper
|
|
| |
|
Hallo Sebastian,
> 7*d = 1(mod160)
> d = 23 ![[ok]](/images/smileys/ok.gif "[ok]")
> Hallo,
>
> ich habe dieses Beispiel in einem Buch zur Verschlüsselung
> von ASCII-Codes gefunden. Jedoch weiß ich nicht wie d=23
> zustande kommt. Die Formel habe ich bereits nach d
> umgestellt:
>
> d = [mm]\bruch{1(mod160)}{7}[/mm]
>
> Mein Ergebnis ist demnach jedoch: [mm]d=\bruch{1}{7}[/mm]
> Rechne ich (mod160) eventuell falsch?
Ja, was bedeutet denn diese Schreibweise?
Der "Bruch" ist doch hier nur eine Bezeichnung für das multiplikativ Inverse von 7 modulo 160
Also [mm] $7\cdot{}\underbrace{\frac{1}{7}}_{=7^{-1}}=1 [/mm] \ [mm] \mod(160)$ [/mm] ist gemeint
Nun ist das Inverse von $7$ modulo 160 genau 23, denn [mm] $7\cdot{}23=161\equiv [/mm] 1 \ [mm] \mod(160)$
[/mm]
>
>
> MfG und Danke im voraus!
> Sneiper
>
LG
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:42 Do 19.02.2009 | | Autor: | Sneiper |
| Aufgabe | 5*d=1(mod2)
[mm] d=\bruch{1(mod2)}{5} [/mm] |
Ich bin mir noch nicht wirklich sicher ob ich dich richtig verstanden habe. Wie würde man diese Aufgabe lösen? Was für Rechenschritte muss ich durchführen um d zu erhalten?
MfG Sneiper
|
|
|
| |
|
hallo,
also im grunde ist das was du schreibst doch äquivalent zu 5*d=1 in Z2, da 5 aber selbst die klasse von 1 in Z2 besitzt, ist d=1 eine lösung, im grunde genommen bieten dir die menge der ungeraden zahlen eine lösung für d.
viele grüße
|
|
|
| |
|
Hallo Sneiper,
"modulo n" ist eine Angabe über Restklassen. Man schreibt dann üblicherweise auch kein Gleichheitszeichen, sondern ein "äquivalent zu": [mm] \equiv.
[/mm]
[mm] 7\equiv 19\equiv -1\equiv 3\mod{4}
[/mm]
Diese vier (zufällig gegriffenen) Zahlen lassen bei Teilung durch vier alle den Rest 3. Man könnte auch sagen, zu jeder dieser Zahlen kann man 1 hinzuzählen oder 3 abziehen, um eine durch 4 teilbare Zahl zu bekommen.
So gibt es in dieser Rechenweise keine Brüche. Du kannst nur dann durch eine Zahl teilen, wenn beide Seiten der Äquivalenz ohne Rest durch diese Zahl teilbar sind. Dennoch gibt es oft (aber nicht immer) eine Umkehrung zur Multiplikation, nämlich die Multiplikation mit dem multiplikativen Inversen.
sei [mm] a=5\mod{7}. [/mm] Dann ist 3 das multiplikativ Inverse, denn es gilt: [mm] 5*3=15\equiv 1\mod{7}.
[/mm]
Man ermittelt es über den ![[]](/images/popup.gif) Erweiterten euklidischen Algorithmus.
Grüße,
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:35 Sa 21.02.2009 | | Autor: | ALDI666 |
Hi,
ich hänge im moment an der rechnung [mm] 7\*d=1(mod180)
[/mm]
meine inverse muss doch ganzzahlig sein ich komme da aber auf ne nachkommastelle.
und wenn ich jetzt die Rechnung in stimmige [mm] 7\*d=2(mod180) [/mm] (d=26) stimmt mein endergebnis nicht mehr
Danke schonmal =)
|
|
|
| |
|
> Hi,
>
> ich hänge im moment an der rechnung [mm]7\*d=1(mod180)[/mm]
> meine inverse muss doch ganzzahlig sein ich komme da aber
> auf ne nachkommastelle.
Hallo,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") .
Das Problem kann nur ein Rechenfehler sein oder die falsche Durchführung des Algorithmus.
Genaueres kann man nur sagen, wenn man Deine Rechnung sieht.
Gruß v. Angela
> und wenn ich jetzt die Rechnung in stimmige [mm]7\*d=2(mod180)[/mm]
> (d=26) stimmt mein endergebnis nicht mehr
>
> Danke schonmal =)
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:18 Sa 21.02.2009 | | Autor: | ALDI666 |
wieso meine rechnung sehen? ^^ die rechnung IST [mm] 7\*d=1(mod180)
[/mm]
^^ nur das ich auf ein ergebnis mit nachkommastelle komme und das kann meiner meinung nach nicht korrekt sein
MFG ALDI
|
|
|
| |
|
> wieso meine rechnung sehen? ^^ die rechnung IST
> [mm]7\*d=1(mod180)[/mm]
Hallo,
das ist wohl eher die zu lösende Aufgabe, oder?
> ^^ nur das ich auf ein ergebnis mit nachkommastelle komme
> und das kann meiner meinung nach nicht korrekt sein
Meiner Meinung nach auch nicht. Denn wenn Du mod 180 rechnest, gibt es gar keine Kommazahlen.
Daher gehe ich davon aus, daß Du beim erweiterten euklidischen Algorithmus etwas verkehrt gemacht hast, und deshalb wollte ich ihn sehen - Du mußt ihn natürlich nicht zeigen, wenn Du nicht möchtest.
Achso: falls Du keinen Euklidischen Algorithmus durchführen möchtest, kannst Du natürlich auch für d alle natürlichen Zahlen zwichen 0 und 179 durchprobieren.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:30 Sa 21.02.2009 | | Autor: | ALDI666 |
achso sry
Ich rechne das immer so das ich mehr oe rminder im kopf (bzw mit dem taschenrechner) danach suche weil wir sowas noch garnicht inner schule hatten und ich EIG garnicht weiß wie das funktioniert.
mein ergebnis wäre 181/7=25,8574...
tja und keine ahnung xD
nen fachbuch haben wir leider nicht und Wiki oder andere Foren sind zu hoch für mich (mathe aufm letzten zeugnis 1 punkt)
und ich brauche das für die letzte rechnung meiner facharbeit 
MFG ALDI
|
|
|
| |
|
> achso sry
> Ich rechne das immer so das ich mehr oe rminder im kopf
> (bzw mit dem taschenrechner) danach suche weil wir sowas
> noch garnicht inner schule hatten und ich EIG garnicht weiß
> wie das funktioniert.
> mein ergebnis wäre 181/7=25,8574...
> tja und keine ahnung xD
Hallo,
7*d=1 mod 180
bedeutet, daß Du ein d finden sollst, so daß 7*d = (Vielfaches von 180) + 1 ist.
Du kannst jetzt losprobieren, für welche Zahl k die Zahl k*180 + 1 durch 7 teilbar ist.
(1*180 + 1):7= 25,86 geht nicht
(2*180 + 1):7= ...
(3*180 + 1):7=
(4*180 + 1):7= ...
(5*180 + 1):7=
Keine Angst, Du wirst bald fündig. Rechts steht dann das gesuchte d.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:54 Sa 21.02.2009 | | Autor: | ALDI666 |
7*d=1 mod 180
bedeutet, daß Du ein d finden sollst, so daß 7*d = (Vielfaches von 180) + 1 ist.
Du kannst jetzt losprobieren, für welche Zahl k die Zahl k*180 + 1 durch 7 teilbar ist.
(1*180 + 1):7= 25,86 geht nicht
(2*180 + 1):7= ...
(3*180 + 1):7=
(4*180 + 1):7= ...
(5*180 + 1):7=
--> das würde ja bedeuten das es mehrere ergebnise gibt da es mehrere teilbare faktoren gibt... ich hab das spielchen eben schnell mit dem taschenrechner bis 25 getrieben und da hatte ich schon 4 treffer...
nämlich die 4, die 11, die 18 und die 25
was is da nun das ergebnis? die 103 die bei der 4 als ergebnis auftaucht oder die 283 die bei 11 berechnet wird?
MFG ALDI
|
|
|
| |
|
>
> 7*d=1 mod 180
>
> bedeutet, daß Du ein d finden sollst, so daß 7*d =
> (Vielfaches von 180) + 1 ist.
>
> Du kannst jetzt losprobieren, für welche Zahl k die Zahl
> k*180 + 1 durch 7 teilbar ist.
>
> (1*180 + 1):7= 25,86 geht nicht
> (2*180 + 1):7= ...
> (3*180 + 1):7=
> (4*180 + 1):7= ...
> (5*180 + 1):7=
>
> --> das würde ja bedeuten das es mehrere ergebnise gibt da
> es mehrere teilbare faktoren gibt... ich hab das spielchen
> eben schnell mit dem taschenrechner bis 25 getrieben und da
> hatte ich schon 4 treffer...
> nämlich die 4, die 11, die 18 und die 25
> was is da nun das ergebnis? die 103 die bei der 4 als
> ergebnis auftaucht oder die 283 die bei 11 berechnet wird?
Hallo,
wie Du bemerkt hast, gibt es mehrere Zahlen die es tun, Du wirst sehr viele finden.
Es sind aber 103 und 283 kongruent mod 180, denn 283=1*180 + 103.
Wenn man mod 180 rechnet, gibt man die Zahlen normalerweise so an, daß sie zwischen 0 und 179 liegen,
es sei denn, es sind aus irgendeinem grund alle natürlichen Zahlen gesucht, die diese Gleichung lösen.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:09 Sa 21.02.2009 | | Autor: | ALDI666 |
demnach wäre ja 103 die richtige lösung, aber kann das sein? weil ich versuche gerade eine rsa-verschlüsselung nachzurechnen für die facharbeit und mein nächster schritt wäre jetzt 42^103(mod209) auszurechnen -_-
das ist ja schon fast nichtmehr menschenmöglich (finde ich)
und am ende muss dann auch noch 74 rauskommen ^^
und iwie finde ich passt die rechnung auch nich zu dem beispiel am anfang der frage hier... von sneiper2000
der fragte ja danach ob in seinem fall d=23 richtig is was es auch war, nur warum, und dort ist ein anderer rechenschritt den wir verfolgen.
MFG ALDI
|
|
|
| |
|
> demnach wäre ja 103 die richtige lösung, aber kann das
> sein?
Hallo,
ja.
Du kannst Dich davon überzeigen, daß 7*103= 4*180 +1 ist, also ist 7*103 =1 (mod 180).
> weil ich versuche gerade eine rsa-verschlüsselung
> nachzurechnen für die facharbeit und mein nächster schritt
> wäre jetzt 42^103(mod209) auszurechnen -_-
Das könnte man sich ja etwas zerlegen in [mm] 2^{103}*3^{103}*7^{103} [/mm] oder ähnliches, und sich dann über kleinere Potenzen vorarbeiten.
> das ist ja schon fast nichtmehr menschenmöglich (finde
> ich)
> und am ende muss dann auch noch 74 rauskommen ^^
>
> und iwie finde ich passt die rechnung auch nich zu dem
> beispiel am anfang der frage hier... von sneiper2000
> der fragte ja danach ob in seinem fall d=23 richtig is was
> es auch war, nur warum,
Er hatte die Aufgabe 7*d=1 mod (160) vorgelegt, und es ist 7*23=1*180 + 1.
> und dort ist ein anderer
> rechenschritt den wir verfolgen.
Ich weiß nicht, was Du mit anderem Rechenschritt meinst.
Gruß v. Angela
>
> MFG ALDI
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:42 Sa 21.02.2009 | | Autor: | ALDI666 |
So ich hoffe das klappt jetzt alles vielen dank für die hilfe =)
ich werde jetzt erstmal in rechnungen versinken (denke das mit 42^103 wird ne weile dauern^^)
MFG ALDI
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:00 Sa 21.02.2009 | | Autor: | ALDI666 |
Ich hab noch so n problem entdeckt ^^
ist 103 nicht ne Primzahl?
wenn ich jetzt 24^103 ausrechnen will (ich hatte eben nen dreher) kann ich die 24 zwar in [mm] 2\*2\*2\*3 [/mm] zerlegen aber die 103 ist ja nich zerlegbar, und das schafft mein taschenrechner nicht und der umrechner ausm netz leider auch nich.
was kann ich tun?
kann ich 103 einfach in 100 und 3 zerlegen sodass ich dann 100 zerlege in [mm] 2\*5\*5\*2 [/mm] und dann einfach noch [mm] \+3 [/mm] rechne?
oder funktioniert das das ich 103 in 8+8+8+8+8+8+8+8+8+8+8+8+2+2+2+1 zerlege und dann [mm] 24^8*24^8*[...]*24^1 [/mm] rechne?
MFG ALDI
|
|
|
| |
|
> Ich hab noch so n problem entdeckt ^^
> ist 103 nicht ne Primzahl?
Hallo,
ja.
> kann ich 103 einfach in 100 und 3 zerlegen sodass ich dann
> 100 zerlege in [mm]2\*5\*5\*2[/mm] und dann einfach noch [mm]\+3[/mm]
> rechne?
Ja das kannst Du tun.
> oder funktioniert das das ich 103 in
> 8+8+8+8+8+8+8+8+8+8+8+8+2+2+2+1 zerlege und dann
> [mm]24^8*24^8*[...]*24^1[/mm] rechne?
Auch das kannst Du machen.
Ich habe eben ausgerechnet, daß [mm] 24^3= [/mm] 30 mod 209 ist,
Jetzt könnte ich rechnen [mm] 24^{103}=24^{3*34 +2}= [/mm] 30^34 * [mm] 24^2=30^34 [/mm] *158= ... Jetzt könnte man z.b [mm] 30^3=39 [/mm] mod 209 nutzen, und sich langsam weiter vorarbeiten.
Gruß v. Angela
>
> MFG ALDI
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:35 Sa 21.02.2009 | | Autor: | ALDI666 |
Ich habe jetzt die 103 zerlegt runter bis auf [mm] 24^4\*24^4\*[...]\*24^1
[/mm]
hab dann erstmal jedes einzelne aufgelöst zu 93, dann immer drei 93er zusammengefasst zu 125.
da kam dann raus
[mm] 125\*125\*125\*125\*125\*125\*125\*80\*158\*158\*158\*24
[/mm]
das hab ich dann weiter vereinfacht zu
[mm] 20\*20\*169\*142
[/mm]
und dafür kam dann das ergebnis 39 raus aber es MUSS 74 rauskommen... was habe ich jetzt schonweider falsch gemacht?
(alles (mod209)
MFG ALDI
|
|
|
| |
|
> Ich habe jetzt die 103 zerlegt runter bis auf
> [mm]24^4\*24^4\*[...]\*24^1[/mm]
Hallo,
103= 25*4 + 3.
Da könnte ein Fehler sein.
Gruß v. Angela
> hab dann erstmal jedes einzelne aufgelöst zu 93, dann
> immer drei 93er zusammengefasst zu 125.
> da kam dann raus
> [mm]125\*125\*125\*125\*125\*125\*125\*80\*158\*158\*158\*24[/mm]
> das hab ich dann weiter vereinfacht zu
> [mm]20\*20\*169\*142[/mm]
> und dafür kam dann das ergebnis 39 raus aber es MUSS 74
> rauskommen... was habe ich jetzt schonweider falsch
> gemacht?
> (alles (mod209)
>
> MFG ALDI
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:49 Sa 21.02.2009 | | Autor: | ALDI666 |
ne leider nicht das hab ich auch einmal durchgerechnet also:
[mm] 24^2\*24^5\*24^5\*24^2+24^3
[/mm]
[mm] 158\*144\*144\*158+30
[/mm]
[mm] 180\*180+30
[/mm]
5+30=35
da fehlen mir 40 xD
oder hab ich mich da iwo verrechnet?
> > Ich habe jetzt die 103 zerlegt runter bis auf
> > [mm]24^4\*24^4\*[...]\*24^1[/mm]
>
> Hallo,
>
> 103= 25*4 + 3.
>
> Da könnte ein Fehler sein.
>
> Gruß v. Angela
>
>
> > hab dann erstmal jedes einzelne aufgelöst zu 93, dann
> > immer drei 93er zusammengefasst zu 125.
> > da kam dann raus
> >
> [mm]125\*125\*125\*125\*125\*125\*125\*80\*158\*158\*158\*24[/mm]
> > das hab ich dann weiter vereinfacht zu
> > [mm]20\*20\*169\*142[/mm]
> > und dafür kam dann das ergebnis 39 raus aber es MUSS 74
> > rauskommen... was habe ich jetzt schonweider falsch
> > gemacht?
> > (alles (mod209)
> >
> > MFG ALDI
>
|
|
|
| |
|
> ne leider nicht das hab ich auch einmal durchgerechnet
> also:
> [mm]24^2\*24^5\*24^5\*24^2+24^3[/mm]
Oh weh.
Bitte eine Portion  Potenzgesetze für Dich.
Du willst doch ausrechnen
[mm] 24^{103} =24^{25*4 +3} =24^{25*4} \* 24^3 ={24^4}^{25}\* 24^3.
[/mm]
Da oben rechnest Du gerade [mm] 24^{2+5+5+2}+24^3= 24^{14} [/mm] + [mm] 24^3 [/mm] aus.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:38 Sa 21.02.2009 | | Autor: | ALDI666 |
Aber ich muss das ja zerlegen bis min hoch 7 weil ich alles drüber nicht berechnen kann...
wiso funktioniert das nicht?
MFG ALDI
|
|
|
| |
|
> Aber ich muss das ja zerlegen bis min hoch 7 weil ich alles
> drüber nicht berechnen kann...
> wiso funktioniert das nicht?
Hallo,
ziemlich kryptisch, Deine Frage.
Mal sehen, ob ich erraten habe, worum es geht, falls nicht, müßtest Du sie nochmal verständlich stellen.
Es ist doch $ [mm] 24^{103} ={24^4}^{25}* 24^3. [/mm] $ [mm] =\underbrace{24^4*24^4* ... *24^4}_{25mal} [/mm] * [mm] 24^3.
[/mm]
Hier hast Du keine hohen Potenzen von 24.
Gruß v. Angela
>
> MFG ALDI
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:57 Sa 21.02.2009 | | Autor: | ALDI666 |
das war schon meine frage aber ich hab das jetzt nochmal durchgerechnet und bekomme jetzt 7 raus -_-
meine rechenschritte waren [mm] 24^4 [/mm] (25mal) [mm] \*24^3
[/mm]
das sind in (mod209) [mm] 93\*30 [/mm] (nur die 93 halt 25 mal^^)
dann hab ich [mm] (93\*93\*93\*93)=130 [/mm] also
[mm] 130\*130\*130\*130\*130\*93\*30
[/mm]
was dann [mm] 201\*180\*73=7 [/mm] ergibt
(alles mod209)
und 7 is ja wieder das falsche ergebnis :(
MFG ALDI
|
|
|
| |
|
> das war schon meine frage aber ich hab das jetzt nochmal
> durchgerechnet und bekomme jetzt 7 raus -_-
Hallo,
ich kann Dir nicht versprechen, daß 74 herauskommt, ich hab's nicht gerechnet. (Nachtrag: aber im Verlaufe des Schreibens diese Posts unter Verwendung Deiner Ergebnisse doch bekommen.)
> meine rechenschritte waren [mm]24^4[/mm] (25mal) [mm]\*24^3[/mm]
> das sind in (mod209) [mm]93\*30[/mm] (nur die 93 halt 25 mal^^)
Aha. Du meinst [mm] 93^{25}*30.
[/mm]
> dann hab ich [mm](93\*93\*93\*93)=130[/mm] also
[mm] 93^4=130
[/mm]
> [mm]130\*130\*130\*130\*130\*93\*30[/mm]
Das ist dann dasselbe wie [mm] 93^4\*93^4\*93^4\*93^4\*93^4\*93\*30= 93^{20}*93*30 [/mm] = [mm] 93^{21}*30.
[/mm]
Ich erinnere mich allerdings dunkel, daß Du eigentlich [mm] 93^{25}*30 [/mm] ausrechnen wolltest...
Wenn Du so schlampig arbeitest, kann ja nicht das richtige Ergebnis herauskommen!
Gruß v. Angela
> was dann [mm]201\*180\*73=7[/mm] ergibt
> (alles mod209)
> und 7 is ja wieder das falsche ergebnis :(
>
> MFG ALDI
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:12 Mo 23.02.2009 | | Autor: | ALDI666 |
Vielen dank für die aufwändige und zeitraubende antwort (ich war wohl gegen ende der rechnung etwas unterzuckert, eig hät ich das mit den potenzgesetzen wissen müssen^^)
Vielen dank =)
MFG ALDI
|
|
|
|
