Seite 1 von 1

Babystep-Giantstep

Verfasst: 11. Feb 2013 21:04
von itportal2
Hallo zusammen,

in Übung 11 Aufgabe P2 rechnet man mit n = 13, weil 16 eine zyklische Gruppe Ordnung 13 erzeugt. Wieso dürfen wir an der Stelle mit n = 13 (bzw. m = 4) rechnen? Was ist die Regel dafür, steht nichts im Buch und ich habe mir nichts dazu in der Vorlesung notiert.

Re: Babystep-Giantstep

Verfasst: 12. Feb 2013 00:59
von ISTler
Wenn die Elementordung von 16 gleich 13 ist ergibt es ja nur Sinn Ergbenisse x kleiner als 13 suchen zu wollen. Zwar lösen alle s mit \(s \equiv x\; mod\; 13\) die Gleichung \(16^s \equiv 46\; mod\; 53\) aber es reicht ja sich auf die betragsmäßig kleinste Lösung zu beschränken.