121^161 mod 187 = ?

lookias

121^161 = (11²⁾(7*23) = (11⁷⁾46

dann erst 11^7 mod 187 ausrechnen

und dann 46 mal (11^7 mod 187)*11^7 mod 187 rechnen

borg schrieb:

das zauberwort heißt erweiterter euklidscher algorithmus

Quark.

lookias schrieb:

121^161 = (11²⁾(7*23) = (11⁷⁾46

dann erst 11^7 mod 187 ausrechnen

und dann 46 mal (11^7 mod 187)*11^7 mod 187 rechnen

Viel zu umständlich.

Beachte: phi(187) = 160

lookias

dgfdgfd schrieb:

lookias schrieb:

121^161 = (11²⁾(7*23) = (11⁷⁾46

dann erst 11^7 mod 187 ausrechnen

und dann 46 mal (11^7 mod 187)*11^7 mod 187 rechnen

Viel zu umständlich.

stimmt laesst sich aber gut programmieren wenn man die zerlegung erstmal kennt

Taurin

Ganz allgemein kannst du Potenzen in Restklassenringen wie folgt berechnen:

unsigned pow(unsigned b, unsigned exp, unsigned mod)
{
    if(exp==0)
      return 1;
    if(exp%2==0)
      return (pow(b,exp/2,mod)*pow(b,exp/2,mod))%mod;
    else
      return ((pow(b,exp/2,mod)*pow(b,exp/2,mod)%mod)*b)%mod;
}

Der erw. eukl. Alg. hat damit übringens nix zu tun:
http://de.wikipedia.org/wiki/Euklidischer_Algorithmus

Laut MuPad = 121 ?!?

Coldfly schrieb:

Laut MuPad = 121 ?!?

dgfdgfd schrieb:

Beachte: phi(187) = 160

m3ph1570

Cplusplus schrieb:

die kann ich nicht mit nem Taschenrechner (im Computer) ausrechnen.

Häh? Ruf doch mal den normalen Windows-Taschenrechner auf, wechsel auf die wissenschaftliche Ansicht und gibs ein. Ergebnis: 121.

Gruß,
m3ph1570

lookias

versuch mal

7^{7^{7{^{7^{7}}}}$ mod $10

mit nem pc mit der brute force methode

edit:
kann mich auch wage dran erinnern, dass man das mit der hilfe euler funktion machen kann.

lookias schrieb:

versuch mal
7^{7^{7{^{7^{7}}}}$ mod $10
mit nem pc mit der brute force methode

edit:
kann mich auch wage dran erinnern, dass man das mit der hilfe euler funktion machen kann.

7^{7^{7{^{7^{7}}}} \equiv 7^{7^{7{^{7^{7}}} \mod \varphi(10)}\pmod{10}

borg

Cplusplus schrieb:

Wie kann ich folgendes ausrechnen: 121^161 mod 187 ?

nachdem ich in der ersten antworte scheisse geschrieben hab, also ich würds so machen:

1   0   1   0   0   0   0   1     // exponent binär
154 154 154 154 154 33  55  121   // jeweils quadrate (mod 187)

121^161 = 154*154*121 = 121 (mod 187) // alle wo binär eine 1 ist mutliplizieren

geht also trotzdem per hand auf einem blatt papier, mit einem taschenrechner der multiplizieren und dividieren kann.

borg schrieb:

geht also trotzdem per hand auf einem blatt papier, mit einem taschenrechner der multiplizieren und dividieren kann.

Man muss nur 161 mod 160 = 1 rechnen und kann sofort das Ergebnis hinschreiben.

borg

ddfgdfg schrieb:

borg schrieb:

geht also trotzdem per hand auf einem blatt papier, mit einem taschenrechner der multiplizieren und dividieren kann.

Man muss nur 161 mod 160 = 1 rechnen und kann sofort das Ergebnis hinschreiben.

ja, das ist mir klar. das geht aber nur in diesem speziellen fall, ich denke der autor möchte eher wissen wie er das allgemein lösen kann