Seite 1 von 1

Übung 4

Verfasst: 17. Mär 2013 17:57
von barracuda317
Hallo,

wie löse ich denn die Übung 4 ohne PC?

mein Taschenrechner mag mir 3^23 mod 47 nicht mehr ausgeben.

GIbt es da einen Trick?

Re: Übung 4

Verfasst: 17. Mär 2013 18:43
von JannikV
Hey,

laut Aufgabenstellung mit Hilfe der "effizienten Exponentiation”

VG

Re: Übung 4

Verfasst: 17. Mär 2013 18:47
von barracuda317
Hmm, stand zwar genau genommen nicht bei dem Aufgabenteil, aber das leuchtet natürlich ein.

Dann darf ich aber nicht zu viele Generatoren ausprobieren. Sonst dauert das etwas zu lang.

Re: Übung 4

Verfasst: 17. Mär 2013 19:02
von Ankou
alternativ stückweise berechnen.
Beispiel:
5^23 mod 47 = 46, schafft der Taschenrechner aber nicht.
Mit umformen schafft ers aber:
5^23 mod 47 = ((5^5 mod 47)^4 mod 47)*(5^3 mod 47) mod 47 = (23^4 mod 47)*31 mod 47 = 3*31 mod 47 = 46