Komplexität und Einwegfunktionen - Kryptologie - page 59

Die Anzahl der Bits einer natürlichen Zahl N ist O

(

log N

)

. Genauer: Die An-

( ) ∈ N ≥ 2 , beträgt

zahl f N der Stellen in g -adischer Darstellung, g

log g N

( )= + = ( )

f N 1 O log N .

Der Wert von g spielt asymptotisch keine Rolle.

Bemerkung
Für den logarithmus naturalis verwenden wir die Bezeichnung log

= log e oh-

ne Angabe der Basis. Sollte es einmal (wie etwa bei den obigen asymptotischen
Betrachtungen) nicht auf die Basis ankommen, so bevorzugen wir auch im Fall
g

=

e die einfache Schreibweise log anstelle log g .

4.1.2 Die Laufzeit von Algorithmen

Das Ziel dieses Abschnitts ist es, die Laufzeit von Algorithmen abzuschätzen und
zu vergleichen. Dabei nutzen wir ein sehr grobes Maß: Wir zählen die nötigen
Iterationen in Abhängigkeit von der Größe der Eingabe bezogen auf eine einfa-
che Grundoperation . Wir abstrahieren dadurch von der Hardware, die natürlich
die tatsächlich benötigte Zeit entscheidend mitbestimmt. Insbesondere kann die
Grundoperation durchaus eine größere Anzahl von Prozessorzyklen in Anspruch
nehmen und selbst zeitaufwändig sein. Sie muss aber O

(

1

)

sein, darf also nicht

von der Größe der Eingabe abhängen.
Unsere Angaben werden immer asymptotisch sein, dabei ignorieren wir die De-
tails der Implementierung , also die konkrete Umsetzung eines Algorithmus in eine
Programmiersprache. Auch diese beeinflusst durchaus erheblich die tatsächlich
benötigte Zeit.
Asymptotische Aussagen sagen insbesondere nichts über die Laufzeit für kleine
Eingangsgrößen aus. Um darüber Ergebnisse zu erzielen, muss man die Konstan-
ten genau studieren.
Ist n die Größe der Eingabe (etwa die Anzahl der Bits) in einen Algorithmus, so
heißt der Algorithmus

n α ) ( α ∈ R > 0 , ist, • polynomial , wenn die Laufzeit O ,

• linear , falls er polynomial mit α = 1 ist,

• quadratisch , falls er polynomial mit α = 2 ist,

e α n

α ∈ R > 0 , beträgt.
In diesem Sinne ist die Laufzeit des Einlesens der Daten linear. Insbesondere hat
das Einlesen einer natürlichen Zahl N nach dem letzten Beispiel die Laufzeit
O

( )

• exponentiell , wenn die Laufzeit O ,

( )

. Wir werden im nächsten Abschnitt sehen, dass der übliche Algorith-
mus für die Addition natürlicher Zahlen linear, der für die Multiplikation qua-
dratisch ist.

log N