modulo mit großen Exponenten < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Berechne [mm] 2^{1000000} [/mm] in [mm] \IZ_{77}. [/mm] |
Hallo!
Ich habe bis jetzt mit Hilfe des Satzes von Euler (für ggT(a,n)=1 gilt: [mm] a^{\varphi (n)} \equiv1(modn) [/mm] ) folgende Umformung vorgenommen:
[mm] \varphi(77)=60
[/mm]
[mm] 2^{1000000}=2^{16666*60+40}=(2^{60})^{16666}*2^{40}\equiv 1^{16666}*2^{40}mod(77)
[/mm]
Stimmt das so weit?
Kann mir jemand sagen, was ich jetzt machen muss?
Ich hatte mir schon überlegt den Exponenten in 2er-Potenzen zu zerlegen:
[mm] 40=2^{5}+2^{3}
[/mm]
Weiß aber nicht wirkllich, ob mir das was hilft bzw. das Hornerschema, für das man das machen muss hab ich nicht wirklich verstanden..
Liebe Grüße,
Kate-Mary
|
|
| |
|
Hallo Kate-Mary,
> Berechne [mm]2^{1000000}[/mm] in [mm]\IZ_{77}.[/mm]
>
>
>
> Hallo!
>
> Ich habe bis jetzt mit Hilfe des Satzes von Euler (für
> ggT(a,n)=1 gilt: [mm]a^{\varphi (n)} \equiv1(modn)[/mm] ) folgende
> Umformung vorgenommen:
>
> [mm]\varphi(77)=60[/mm]
>
> [mm]2^{1000000}=2^{16666*60+40}=(2^{60})^{16666}*2^{40}\equiv 1^{16666}*2^{40}mod(77)[/mm]
>
>
> Stimmt das so weit?
Ja.
> Kann mir jemand sagen, was ich jetzt machen muss?
>
> Ich hatte mir schon überlegt den Exponenten in
> 2er-Potenzen zu zerlegen:
> [mm]40=2^{5}+2^{3}[/mm]
> Weiß aber nicht wirkllich, ob mir das was hilft bzw. das
> Hornerschema, für das man das machen muss hab ich nicht
> wirklich verstanden..
>
Nun, dann musst Du [mm]mod\left(2^{2^k},77\right)[/mm] berechnen.
> Liebe Grüße,
> Kate-Mary
>
Gruss
MathePower
|
|
|
| |
|
Danke erstmal, dass du dir schon wieder was von mir angeschaut hast 
Das ich das jetzt ausrechnen muss hab ich schon fast befürchtet. Nur dass da halt auch wieder rießen Zahlen rauskommen....
Gibts da keine einfachere Möglichkeit? also dass ich das noch irgendwie kleiner bekomm...
LG
|
|
|
| |
|
Hallo Kate-Mary,
> Danke erstmal, dass du dir schon wieder was von mir
> angeschaut hast
>
> Das ich das jetzt ausrechnen muss hab ich schon fast
> befürchtet. Nur dass da halt auch wieder rießen Zahlen
> rauskommen....
> Gibts da keine einfachere Möglichkeit? also dass ich das
> noch irgendwie kleiner bekomm...
>
Das kannst Du auch rekursiv berechnen.
Es gilt:
[mm]2^{2^{k+1}} \operatorname{mod} 77=2^{2^{k}}*2^{2^{1}} \operatorname{mod} 77[/mm]
Beginne hier mit k=1.
> LG
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:19 So 26.05.2013 | | Autor: | abakus |
> Berechne [mm]2^{1000000}[/mm] in [mm]\IZ_{77}.[/mm]
>
>
>
> Hallo!
>
> Ich habe bis jetzt mit Hilfe des Satzes von Euler (für
> ggT(a,n)=1 gilt: [mm]a^{\varphi (n)} \equiv1(modn)[/mm] ) folgende
> Umformung vorgenommen:
>
> [mm]\varphi(77)=60[/mm]
>
> [mm]2^{1000000}=2^{16666*60+40}=(2^{60})^{16666}*2^{40}\equiv 1^{16666}*2^{40}mod(77)[/mm]
>
>
> Stimmt das so weit?
> Kann mir jemand sagen, was ich jetzt machen muss?
>
> Ich hatte mir schon überlegt den Exponenten in
> 2er-Potenzen zu zerlegen:
> [mm]40=2^{5}+2^{3}[/mm]
> Weiß aber nicht wirkllich, ob mir das was hilft bzw. das
> Hornerschema, für das man das machen muss hab ich nicht
> wirklich verstanden..
Hallo,
taste dich doch langsam ran. [mm] $2^{10}=1024$ [/mm] ist noch elementar beherrschbar, das lässt den Rest 23 mod 77.
Dann [mm] gilt $2^{20} \equiv 23^2 \equiv [/mm] 529 [mm] \equiv [/mm] 67 [mm] \equiv [/mm] -10 mod 77$ und daraus [mm] $2^{40}\equiv(-10)^2\equiv [/mm] 100 mod 77$.
Gruß Abakus
>
> Liebe Grüße,
> Kate-Mary
>
>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:20 So 26.05.2013 | | Autor: | Kate-Mary |
Ah, okay, super :)
Danke
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:21 So 26.05.2013 | | Autor: | sometree |
Hallo Kate-Mary,
eine kleine allgemeine Ergänzung zu solchen Aufgaben:
Man kann den Exponenten i.d.R. nochmal deutlich reduzieren wenn man statt dem [mm] Euler-$\varphi$ [/mm] die Carmichael-Funktion
https://de.wikipedia.org/wiki/Carmichael-Funktion
verwendet.
Leider wird diese Funktion in den entsprechenden Vorlesungen sehr selten betrachtet, allerdings sind die relevanten Beweise sehr kurz.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:23 So 26.05.2013 | | Autor: | Kate-Mary |
Hallo sometree,
danke für den Hinweiß.
Werd ich mir nachher mal anschauen.
Durchgenommen haben wir das ind er Vorlesung bis jetzt aber leider wirklich noch nicht.
LG
|
|
|
|
