euklidischer algorithmus < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:58 Di 04.10.2005 | | Autor: | woldo |
Hola, ich schreibe zur zeit eine seminararbeit über verschlüsselung /speziell rsa-verfahren.
Bei einer aufgabe, und zwar dort wo man den entschlüsselungs-schlüssel berechntet, komm ich nicht weiter.
folgende zeile macht mir probleme:
5 × d = 1 (mod 108)
wie bekomme ich das "d"??
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hi,
euklidscher Algorithmus liefert:
108=21*5+3
5=1*3+2
3=1*2+1
2=2*1+0
also: ggT(5,108)=1
Rückwärts gilt:
1=3-2
2=5-3
3=108 - 21*5
also: 1=3-2=108-21*5-(5-3)=108-22*5+108-21*5=2*108-43*5
so hast du also für d=-43(mod 108)=65(mod 108) deine Lösung.
Gruss,
Spellbinder
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:23 Fr 07.10.2005 | | Autor: | woldo |
wowawieeewa!!
jetzt hab ich das "d", danke. probleme hab ich aber zusätzlich und zwar:
nach der Formel M=C hoch d (mod 108)
meine aufgabe lautet:
M = 26 hoch 65 (mod 108)
tja, leider stellt der handelübliche taschenrechner soviel zahlen nicht dar. wie kann ich diese rechnung optimal aufteilen damit ich ein kleineres (durch modulieren??) ergebnis erhalte??
P.S: danke für die schnelle antw. von vorhin.
|
|
|
| |
|
Hallo!
> nach der Formel M=C hoch d (mod 108)
>
> meine aufgabe lautet:
>
> M = 26 hoch 65 (mod 108)
>
> tja, leider stellt der handelübliche taschenrechner soviel
> zahlen nicht dar. wie kann ich diese rechnung optimal
> aufteilen damit ich ein kleineres (durch modulieren??)
> ergebnis erhalte??
Vielleicht hilft dir hier diese Diskussion weiter. Ansonsten probiere es doch mal mit dem hier.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
Hallo woldo,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
> wowawieeewa!!
>
> jetzt hab ich das "d", danke. probleme hab ich aber
> zusätzlich und zwar:
>
> nach der Formel M=C hoch d (mod 108)
>
> meine aufgabe lautet:
>
> M = 26 hoch 65 (mod 108)
>
> tja, leider stellt der handelübliche taschenrechner soviel
> zahlen nicht dar. wie kann ich diese rechnung optimal
> aufteilen damit ich ein kleineres (durch modulieren??)
> ergebnis erhalte??
Ja, das geht in dem man modulo 108 rechnet.
Du benötigst die Primfaktorzerlegung von 108:
[mm]108\;=\;2^{2}\;3^{3}[/mm]
Nun berechnest Du [mm]\varphi(m)[/mm] wie folgt:
Für eine Primzahl p gilt: [mm]\varphi(m)\;=\;p\;-\;1[/mm]
Für Potenzen von p gilt:[mm]\varphi(p^{n})\;=\;p^{n-1}\;(p\;-\;1)[/mm]
Für zwei teilerfremde Zahlen a,b gilt: [mm]\varphi(a\;b)\;=\;\varphi(a)\;\varphi(b)[/mm]
Das für den Fall, daß Du eine Kongruenzgleichung vorliegen hast.
Beispiel:
[mm]5\;d\; \equiv \;1\;\left( {108} \right)[/mm]
Dann ergibt sich für d die Lösung:
[mm]d \equiv \;5^{\varphi \left( {108} \right)\; - \;1} [/mm]
Die einzelne Potenzen berechnest Du wie folgt:
[mm]5^{0}\;\equiv\;1\;(108)[/mm]
[mm]5^{1}\;\equiv\;5\;(108)[/mm]
[mm]5^{2}\;\equiv\;5\;\times\;5\;\equiv\;25\;(108)[/mm]
[mm]5^{4}\;\equiv\;25\;\times\;25\;\equiv\;85\;(108)[/mm]
[mm]5^{8}\;\equiv\;85\;\times\;85\;\equiv\;97\;(108)[/mm]
[mm]5^{16}\;\equiv\;97\;\times\;97\;\equiv\;13\;(108)[/mm]
[mm]5^{32}\;\equiv\;13\;\times\;13\;\equiv\;61\;(108)[/mm]
Also Du mußt die Potenzen [mm]5^{2^k}[/mm] modulo 108 berechnen.
Das machst Du bis [mm]2^{k}\;\le\;\varphi(m)\;-\;1[/mm].
Stelle also [mm]\varphi(m)\;-\;1[/mm] als Summe von 2er-Potenzen dar.
Gruß
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:13 Sa 08.10.2005 | | Autor: | woldo |
so nun wollt ich mal die rechnung "26 hoch 65" nach dem vorgeschlagenen schema lösen, so hab ichs gmacht:
26 hoch 1 = 26
26 hoch 2 = 28 (mod 108)
26 hoch 2 = 28 (mod 108)
26 hoch 4 = 28 hoch 2 = 28 (mod 108)
26 hoch 8 = 28 hoch 2 = 28 (mod 108)
26 hoch 16 = 28 hoch 2 = 28 (mod 108)
26 hoch 32 = 28 hoch 2 = 28 (mod 108)
26 * 28 * 28 * 28 * 28 * 28 * 28 = 1,25291479 * 10 hoch 10
leider kommt da immer noch so ne hohe zahl raus und ich hab keine ahnung wie ich die modulieren soll, kann mir jmd weiterhelfen?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:30 Sa 08.10.2005 | | Autor: | DaMenge |
Hallo,
wenn alles stimmt, was du da schreibst, dann hast du es doch schon fast:
es fehlt nur noch die Erkenntnis, dass auch gilt:
26 hoch 64 = 28 hoch 2 = 28 (mod 108)
Denn dann gilt doch: (Der Strich bedeutet modulo 108)
$ [mm] \overline{26^{65}} [/mm] = [mm] \overline{26^{64}} [/mm] * [mm] \overline{26} [/mm] = [mm] \overline{28} [/mm] * [mm] \overline{26} =\overline{28*26} [/mm] $
und das letzte schaffst du ja auszurechnen...
viele Grüße
DaMenge
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 12:43 Sa 08.10.2005 | | Autor: | woldo |
danke für die flotte antwort.
28??
naja, als ergebnis sollte ich eigentlich 87 rausbekommen.
irgendwie stimmt da was nicht, evtl. vorher schon beim "d" ??
gruss woldo
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:07 Sa 08.10.2005 | | Autor: | DaMenge |
Hi,
also ich habe doch geschrieben :
[mm] $\overline{28*26}=\overline{728}=\overline{80}$
[/mm]
(wie gesagt: Striche bedeuten modulo 108)
d.h. 80 wäre das Ergebnis von 26 hoch 65 (modulo 108)
Ob 87 nun stimmt und wo du es her hast, kann ich nicht beurteilen..
viele Grüße
DaMenge
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:03 Sa 08.10.2005 | | Autor: | SEcki |
> naja, als ergebnis sollte ich eigentlich 87 rausbekommen.
Woher hast du das Ergebnis? Mupad spuckt mir aus:
>> 26^65 mod 108
80
Genauso gibt mir das auch mein bc aus. Außerdem ist der Rechenweg von DaMenge absolut richtig.
SEcki
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:32 Sa 08.10.2005 | | Autor: | woldo |
ups!
da hat sich ja tatsächlich ein fehler meinerseits eingeschlichen.
die aufgabe hätte 26 hoch 65 (mod 133) und nicht (mod 108) lauten sollen. Nun da ich den Fehler entdeckt habe, is mir alles klar und ich erhalte auch das richtige Ergebnis. und zwar "87".
danke allen für die schnelle hilfe.
mfg
Woldo
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:41 Sa 08.10.2005 | | Autor: | woldo |
Hallo Mathe-Asse,
kann mir jmd. ,an folgendem Beispiel, den euklidischen algorithmus erklären? hab mir schon mal die formeln angesehen, versteh es aber nciht ganz. z.b. was ist ggT und so weiter. wäre schön wenn mir das jmd. mit formel und meinem beispiel zeigen kann.
Beispiel:
5 × d = 1 (mod 108)
der her spellbinder hat mir die lösung schon gegeben und gezeigt, danke, ich würde das halt gern auch anhand von der formel verstehen.
danke im voraus
woldo
|
|
|
| |
|
Hallo woldo,
> folgende zeile macht mir probleme:
>
> 5 × d = 1 (mod 108)
>
>
> wie bekomme ich das "d"??
wir hatten die Lösung als
[mm]
d\; \equiv \;5^{\varphi \left( {108} \right) - 1} \; \equiv \;5^{35} \;\left( {108} \right)[/mm]
angegeben, wobei
[mm]
\varphi \left( {108} \right)\; = \;\varphi \left( {2^2 } \right)\;\varphi \left( {3^3 } \right)\; = \;2\;\left( {2\; - \;1} \right)\;3^2 \;\left( {3\; - \;1} \right)\; = \;36[/mm]
ist.
Wir berechnen also [mm]5^{2^k}[/mm] modulo 108 bis [mm]2^k\;\le\;36[/mm]:
[mm]
\begin{gathered}
5^0 \; \equiv \;1\;\left( {108} \right) \hfill \\
5^1 \; \equiv \;5\;\left( {108} \right) \hfill \\
5^2 \; \equiv \;5\; \times \;5\; \equiv \;25\;\left( {108} \right) \hfill \\
5^4 \; \equiv \;25\; \times \;25\; \equiv \;85\;\left( {108} \right) \hfill \\
5^8 \; \equiv \;85\; \times \;85\; \equiv \;97\;\left( {108} \right) \hfill \\
5^{16} \; \equiv \;97\; \times \;97\; \equiv \;13\;\left( {108} \right) \hfill \\
5^{32} \; \equiv \;13\; \times \;13\; \equiv \;61\;\left( {108} \right) \hfill \\
\end{gathered} [/mm]
Nun läßt sich die Lösung wie folgt schreiben:
[mm]5^{35} \; = \;5^{32} \; \times \;5^2 \; \times \;5^1 [/mm]
Demnach berechnet sich d wie folgt:
[mm]
\begin{gathered}
d\; \equiv \;5^{35} \; \equiv \;5^{32} \; \times \;5^2 \; \times \;5^1 \hfill \\
\equiv \;\left( {61\; \times \;25} \right)\; \times \;5 \hfill \\
\equiv \;13\; \times \;5 \hfill \\
\equiv \;65\;\left( {108} \right) \hfill \\
\end{gathered} [/mm]
Gruß
MathePower
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:02 Sa 08.10.2005 | | Autor: | woldo |
danke!
das öffnet mir die augen!! sehr hilfreich.
grüße an alle die mir geholfen haben, ihr seid spitze.
mfg
woldo
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:14 Sa 08.10.2005 | | Autor: | woldo |
hola,
hab nochmal n paar fragen.
was bedeutet [mm] \equiv
[/mm]
was bedeutet [mm] \varphi
[/mm]
das dürfte alles sein.
mfg
woldo
|
|
|
| |
|
Hi,
Das [mm] \varphi [/mm] steht für die Eulersche [mm] \varphi-Funktion, [/mm] welche in der Antwort von Mathepower erklärt wurde, siehe Beitrag "Eulersche Phi Funktion"
das [mm] \equiv [/mm] steht für "kongruent" ist im Endeffekt die richtige Schreibweise für die Modulo Rechnung und steht für dein =, was hier ja nicht eindeutig ist, da z.B. 2 (mod 5) [mm] \equiv [/mm] 7 (mod 5) [mm] \equiv [/mm] -3 (mod 5) gilt. also ist es nicht wirklich gleich, da du verschiedene Zahlen hast.
Gruss,
Spellbinder
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:20 So 09.10.2005 | | Autor: | woldo |
danke.
weiß jmd wie man dieses zeichen [mm] \varphi [/mm] für die euklidische funktion in microsoft word einfügt bzw. findet?
besten dank
woldo
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:33 So 09.10.2005 | | Autor: | Loddar |
Hallo woldo!
Drei Wege führen hier nach Rom ...
1.) Wenn Du den Formeleditor installiert hast, stehen Dir dort (fast) alle mathematischen Symbole zur Verfügung.
2.) Über <Einfügen> <Symbol ...> und der Schriftart "Symbol" hast Du das [mm] $\varphi$ [/mm] in der 3. Reihe.
3.) Einfach ein "j" (= kleines "Jot"  ) schreiben und in die Schriftart "Symbol" umformatieren.
Gruß
Loddar
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:01 So 09.10.2005 | | Autor: | woldo |
D A N K E
mfg
woldo
|
|
|
|
