Bestimmen Sie 3-2^k für k ∈ {0, 1, 2, 3, 4} möglichst effizient.

Question

Aufgabe:Wir rechnen in der Gruppe  (ℤ^x₅₃, · )

(a) Bestimmen Sie 3^{-2^k} für k ∈ {0, 1, 2, 3, 4} möglichst effizient.
(b) Wieviele Multiplikationen sind dazu jeweils nötig (abhängig von k)

Meine letzte Frage für diese Woche :))

a) 3^-2. 3^-4     3^-8  3^{-16  und wie rechne ich hier weiter ?}

Problem/Ansatz:

Answer 1

3^{-2} = a

3^{-4} = a^2 = b

3^{-8} = b^2 = c

3^{-16} = c^2

Answer 2

In dem betrachteten Restklassenkörper ist

\(2\cdot 3\cdot 3\cdot 3=54=1\), also

\(3^{-1}=2\cdot 3\cdot 3=18\)

\(3^{-2}=2\cdot 3=6\)

\(3^{-3}=2\)

\(3^{-4}=3^{-2}\cdot 3^{-2}=6\cdot 6=36\)

\(3^{-8}=3\cdot 3^{-9}=3\cdot 3^{-3}\cdot 3^{-3}\cdot 3^{-3}=3\cdot 2\cdot 2\cdot 2=24\)

\(3^{-16}=3^{-8}\cdot 3^{-8}=24\cdot 24=46\)

Es ist mir klar, dass die Anzahl der Multiplikationen hier

nicht minimiert wurde. Stattdessen habe ich nach einer Methode

gesucht, die fast ausschleßlich mit kleinen Faktoren arbeitet

und ohne Taschenrechner auskommt.