Weihnachtsuebung A2 a)

mark_fau
Neuling
Neuling
Beiträge: 1
Registriert: 9. Jan 2015 14:27

Weihnachtsuebung A2 a)

Beitrag von mark_fau » 9. Jan 2015 14:54

Hallo,

ich hoffe mir kann jemand mit einem Ansatz für die Aufgabe 2a) weiterhelfen.

Mein Ansatz bisher war \(g^r*y^s\) zu \(gy^r*y^{s-r}\) für \(s>r\) und gedreht für \(r \le s\). Das hilf aber leider nicht die Anzahl der Quadrierungen und Multipikationen von 2n auf n zu bringen.
Andere Ansätze die ich bereits versucht habe sind
- Der Chinesische Restsatz, welcher nicht zum Ergebnis geführt hat.
- Der kleine Satz von Fermat \(a^p \equiv a\,(\mathrm{mod}\,p),\)
- Teile aus dem Satz von Euler \(a^b \equiv a^{b\,\mathrm{mod}\,\varphi(n)}\,(\mathrm{mod}\,n)\qquad a, b, n \in\mathbb{N} \wedge \mathrm{ggT}(a,n)=1\)

Ich muss scheinbar etwas einfaches übersehen haben. Im neuen und im alten Skript finde ich keine Ansätze, welche die schnelle Exponentation von zwei Durchläufen auf einen Durchlauf reduziert. Ich komme auf keinen brauchbaren Ansatz.

Benutzeravatar
mmi1991
Computerversteher
Computerversteher
Beiträge: 349
Registriert: 20. Okt 2011 18:46
Wohnort: Hattersheim

Re: Weihnachtsuebung A2 a)

Beitrag von mmi1991 » 9. Jan 2015 21:52

Denke weniger nach. ;) Probier einfach mal aus. Kannst ja auch mal den langsamen Algo durchprobieren.
Ophasentutor SoSe 2014, WiSe 2015/16
Alle Angaben wie immer ohne Gewähr

Antworten

Zurück zu „Archiv“