Problem des diskreten Logarithmus Voraussetzungen

Neue Frage »

Kolomna Auf diesen Beitrag antworten »
Problem des diskreten Logarithmus Voraussetzungen
Meine Frage:
Hallo,

beim Problem des diskreten Logarithmus besagen manche Quellen, dass die Basis g ein Generator sein muss. In anderen Quellen ist davon die Rede, dass g nur eine "ausreichend große" Ordnung haben muss.
Wieso sind dies Voraussetzungen dafür, dass das Problem schwer zu lösen ist, und warum gibt es unterschiedliche Versionen?

Meine Ideen:
Wenn man für g ein Element mit niedriger Ordnung wählt, dann gibt es ja weniger mögliche Ergebnisse für die Potenzen.
Wählt man deshalb ein Element mit hoher Ordnung, damit es länger dauert, alle Möglichkeiten "auszuprobieren"?

Vielen Dank im Voraus!!
HAL 9000 Auf diesen Beitrag antworten »

Es geht nicht um "länger dauern", sondern überhaupt um Lösbarkeit:

Wenn eine niedrigere als die Gruppenordnung hat, dann ist das Problem für viele Gruppenelemente schlicht nicht lösbar, für diese Werte gibt es dann keinen diskreten Logarithmus!!! Welchen Sinn macht dann noch der Begriff "Logarithmus" bezogen auf die Gesamtgruppe? Er ist dann nur noch in der von erzeugten echten Untergruppe



überhaupt anwendbar.
 
 
Kolomna Auf diesen Beitrag antworten »

Danke für die Antwort!!

Ok, das leuchtet mir ein.
Manchmal habe ich aber auch gelesen, dass g eine große Ordnung haben muss, wobei nicht davon die Rede war, dass es unbedingt ein Erzeuger sein muss.

Kann das Problem dann trotzdem noch Sinn machen, wenn man ein Element mit großer Ordnung nimmt (und sich dann auf eine auf eine entsprechend große Untergruppe bezieht)?
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Kolomna
Ok, das leuchtet mir ein.

Anscheinend dann doch nicht, sonst hättest du nicht die Wiederholung deines an sich sinnfreien Anliegens nachgeschoben.
Kolomna Auf diesen Beitrag antworten »

Du hast Recht, es war blöd. Hatte es nicht durchdacht, sorry.

Dann beziehen sich die Versionen, in denen nur von der "ausreichend großen Ordnung" die Rede ist, einfach darauf, dass g eine große Gruppe erzeugt (und das Problem dadurch schwieriger ist)?
HAL 9000 Auf diesen Beitrag antworten »

Ja vielleicht.

Wie gesagt, der diskrete Logarithmus macht nur wirklich in zyklischen Gruppen Sinn, und dort auch nur bezogen auf Basen, die Erzeuger der Gruppe sind. Den Logarithmusbegriff anderweitig aufzuweichen ("geht manchmal, und manchmal aber auch nicht") halte ich für groben Unfug.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »