2.1. Ganze Zahlen

Der zentrale Forschungsgegenstand der elementare Zahlentheorie ist die Menge der ganzen Zahlen \(\Z = \lbrace0, \pm 1, \pm 2, \pm 3, \ldots \rbrace\). Vergleicht man die Menge der ganzen Zahlen mit anderen Zahlsystemen so gilt bekanntermaßen:

\[\N \subset \Z \subset \Q \subset \R \subset \C\]

Im Gegensatz zu den natürlichen Zahlen \(\N\) ist die Menge \(\Z\) nicht nach unten beschränkt. Andererseits besitzt jede nach unten beschränkte Menge von ganzen Zahlen ein kleinstes Element, was z.B. in den reellen Zahlen \(\R\) im Allgemeinen nicht gilt. Analog gilt natürlich auch, dass jede nach oben beschränkte Menge von ganzen Zahlen ein größtes Element besitzt. Die Existenz eines solchen Elements führt uns zu folgender nützlichen Definition.

Definition 2.1 (Abrundungsfunktion)

Sei \(\alpha \in \R\) eine reelle Zahl, so definieren wir die Abrundung (oder auch untere Gaußklammer) von \(\alpha\) als:

\[\lfloor\alpha\rfloor \ \coloneqq \ \max \lbrace b \in \Z \: | \: b \leq \alpha \rbrace.\]

Somit ist \(\lfloor \alpha \rfloor\) also die größte ganze Zahl \(b\), die kleiner oder gleich \(\alpha\) ist.

Obwohl die Rundungsfunktion allgemein bekannt sein sollte, wollen wir deren Anwendung für ganze Zahlen kurz in einem Beispiel verdeutlichen.

Beispiel 2.1 (Abrundungsfunktion)

Wir stellen fest, dass für die Abrundungsfunktion gilt:

\[\lfloor 3.14 \rfloor = 3, \qquad \lfloor -3.14 \rfloor = -4, \qquad \lfloor -1 \rfloor = -1.\]

Es ist leicht einzusehen, dass für beliebige Zahlen \(\alpha \in \R\) gilt:

\[\floor{\alpha} \ \le \ \alpha \ < \ \floor{\alpha}+1.\]

Gilt außerdem \(\alpha \in \R^+_0\), so erhält man den Wert \(\floor{\alpha} \in \Z\) durch einfaches Abschneiden der Nachkommastellen der nichtnegativen, reellen Zahl \(\alpha\).

2.1.1. Teilbarkeit

Das Konzept der Teilbarkeit von ganzen Zahlen ist zentral für viele kryptographische Verfahren, die wir in dieser Vorlesung diskutieren werden. Daher widmen wir uns in diesem kurzen Abschnitt dediziert diesem elementaren Konzept.

Definition 2.2 (Teilbarkeit)

Für \(a,b\in\Z\) sagt man \(a\) teilt \(b\)  (oder \(a\) ist ein Teiler von \(b\)  oder \(b\) ist ein Vielfaches von \(a\)), falls eine ganze Zahl \(c\in\Z\) existiert, so dass gilt \(b=ca\).

Ist \(a\) ein Teiler von \(b\) so schreibt man \(a\mid b\). Teil \(a\) die Zahl \(b\) nicht, so schreibt man hingegen \(a\nmid b\).

Folgendes einfaches Beispiel soll die Notation nochmal konkret verdeutlichen.

Beispiel 2.2 (Teiler)

Es ist klar, dass die Zahl \(4\) ein Teiler der Zahl \(20\) ist, d.h. \(4 \mid 20\), da gilt \(20 = 5\cdot 4\). Andererseits teilt die Zahl \(4\) nicht die Zahl \(19\), d.h, \(4 \nmid 19\), da keine ganze Zahl \(c \in \Z\) existiert, so dass \(19 = c \cdot 4\) gilt.

Das folgende Lemma fasst die wichtigsten Inklusionen und elementaren Rechenregeln für die Teilbarkeit von ganzen Zahlen zusammen.

Lemma 2.1 (Eigenschaften von Teilern)

Für ganze Zahlen \(a,b,c,d\in\Z\) gelten die folgenden Teilbarkeitsregeln:

1. \(a\mid a\), \(1\mid a\), \(a\mid 0\).

2. \(a\mid b \ \wedge \ b\mid c \quad \Longrightarrow \quad a\mid c\) (Transitivität).

3. \(a\mid b \quad \iff \quad \pm a\mid \pm b\).

4. \(a\mid b \ \wedge \ b\mid a \quad \iff \quad a=\pm b\).

5. \(a\mid 1 \quad \iff \quad a=\pm 1\).

6. \(0\mid a \quad \iff \quad a=0\).

7. \(d\mid a \ \wedge \ d\mid b \quad \Longrightarrow \quad d\mid (ma+nb) \quad \forall m,n\in\Z\).

8. \(a\mid b \ \wedge \ a\ne 0 \quad \iff \quad \frac{b}{a}\in\Z\).

9. \(a\mid b \ \wedge \ a\ne 0 \quad \iff \quad b\bmod a=0\).

Proof. In den Hausaufgaben zu zeigen. ◻

Für betraglich kleine Zahlen benötigen wir meist keinen Algorithmus, um zu testen ob eine Zahl eine andere Zahl teilt. Anders sieht es jedoch aus, wenn wir mit sehr großen Zahlen arbeiten, wie es in der modernen Kryptographie typisch ist. Um zu beantworten, ob die Zahl \(a = 11111111111111\) ein Teiler von \(b = 12345678910987654321\) ist, benötigen wir effiziente Algorithmen, die uns eine klare Aussage liefern. Sobald wir in ss:modulo lernen wie man Divisionsreste algorithmisch ausrechnen kann, wird speziell die letzte Eigenschaft in Lemma 2.1 nützlich um die Teilbarkeit von zwei Zahlen zu testen.

2.1.2. Speicher- und Rechenaufwand

Zur Analyse und Bewertung kryptographischer Algorithmen ist es entscheidend abzuschätzen wie viele Berechnungen und Speicherplatz benötigt werden. Für den Rechenaufwand zählt man in der Regel die benötigte Anzahl an Additionen, Multiplikationen und Vergleichsoperationen. Angegeben wird der Rechenaufwand häufig in Floating Point Operations (abgekürzt als FLOPs), bei welchen historisch bedingt eine Addition und eine Multiplikation zu einer Rechenoperation zusammengefasst werden. Mit Hinblick auf moderne Mikroprozessorarchitekturen und paralleler Datenverarbeitung ist dies natürlich eine sehr starke Vereinfachung von realen Rechenwerken.

Um den Speicher- und Rechenaufwand eines Algorithmus oder Computerprogramms in eine Klasse von Funktionen einzuordnen, verwendet man typischerweise die Landausche \(\mathcal{O}\)-Notation.

Definition 2.3 (Landau-Notation)

Sind \(f:\N\to \R\), \(g:\N\to \R\) zwei reellwertige Funktionen, so schreibt man

\[f=\mathcal{O}(g)\quad \text{ oder }\quad f(n)=\mathcal{O}(g(n)),\]

falls Zahlen \(C\in\R^+\) und \(n_0\in\N\) existieren, so dass gilt

\[|f(n)| \ \le \ C g(n) \quad \forall n \geq n_0.\]

In diesem Fall ist \(g\) also eine asymptotisch obere Schranke für \(f\) und man sagt: \(f\) ist in Groß-O von \(g\).

Obwohl man \(f=\mathcal{O}(g)\) schreibt, hat hier das Gleichheitszeichen nicht die übliche Bedeutung. So gilt beispielsweise in der \(\mathcal{O}\)-Notation \(n=\mathcal{O}(n^2)\) und \(n=\mathcal{O}(n^3)\), aber die Funktionen \(n^2\) und \(n^3\) verhalten sich asymptotisch nicht gleich. In der Regel versuchen wir eine möglichst genaue (man spricht auch von scharfer) obere Schranke anzugeben.

Um das oben eingeführte abstrakte Konzept von asymptotischen Schranken verständlicher zu machen wollen wir einige konkrete Beispiele für die \(\mathcal{O}\)-Notation angeben.

Beispiel 2.3 (Rechenaufwand)

1. Sei der Rechenaufwand eines Algorithmus gegeben durch

   \[f(n) = 123n^2-33n+7+\ln n.\]

   Wir erkennen, dass \(f(n) = \mathcal{O}(n^2)\), da eine Konstante \(C \coloneqq 123 > 0\) und ein Index \(n_0 \coloneqq 1 > 0\) existieren, so dass gilt:

   \[|123n^2 - 33n + 7 + \ln n| \ \leq \ C n^2 \ = \ 123 n^2, \quad \forall n \geq n_0 = 1.\]

2. Die Anzahl der Vergleiche, die man beim Suchen eines Werts in einer unsortierten Menge aus \(n\) Elementen benötigt liegt in \(\mathcal{O}(n)\), da man jedes Element einzeln überprüfen muss.

   Ist die Menge bereits sortiert, so liegt die Anzahl der benötigten Vergleichsoperationen mit dem Intervallhalbierungsverfahren in \(\mathcal{O}(\operatorname{log} n)\).

In verschiedenen Teilen der Mathematik, beispielsweise in der analytischen Zahlentheorie oder in der numerischen Mathematik, ist auch folgende Schreibweise nützlich, um das Laufzeitverhalten von Algorithmen noch genauer anzugeben.

Definition 2.4 (Landau-Notation für Restglieder)

Seien \(f,g,h:\N\to\R\) drei reellwertige Funktionen, so schreibt man

\[f=g+\mathcal{O}(h)\quad\text{ oder }\quad f(n)=g(n)+\mathcal{O}(h(n)),\]

falls für das Restglied \(f(n)-g(n)=\mathcal{O}(h(n))\) gilt.

Für große \(n\) ist immer nur die führende Ordnung der asymptotischen Schranke für den Rechenaufwand interessant. Deshalb ist es nicht so wichtig die weiteren Ordnungen genauer zu bestimmen. So werden wir für ein Verfahren, dass beispielsweise \(2n^2+4n + 3\) Operationen benötigt, als Aufwand typischerweise \(2n^2 + \mathcal{O}(n)\) angeben. Diese Schreibweise wird auch zur Beschreibung von Fehlertermen und Restgliedern in Reihenentwicklungen genutzt, wie das folgende Beispiel illustriert.

Beispiel 2.4 (Harmonische Reihe)

Für die (divergierende) harmonische Reihe \(\sum_{k=1}^n\frac{1}{k}\) kann man schreiben

\[\sum_{k=1}^n\frac{1}{k} \ = \ \ln n+C + \frac{1}{2n} - \frac{1}{12n^2} + \frac{1}{120n^4} + \mathcal{O}\left(\frac{1}{n^6}\right) \ = \ \ln n+C+\mathcal{O}\left(\frac{1}{n}\right)\]

mit der Euler-Mascheroni Konstanten \(C=0.5772156649\dots\).

2.1.3. Zahldarstellungen

Definition 2.5 (b-adische Zahldarstellung)

Sei im Folgenden \(b\in\N\) eine natürliche Zahl mit \(b \ge 2\), die auch Basis genannt wird. Dann lässt sich jede natürliche Zahl \(n\in\N\) eindeutig in einem Stellenwertsystem bezüglich der Basis \(b\) schreiben als

\[n=\sum_{i=0}^{k-1}n_i\cdot b^i\quad\text{ mit }\quad n_i\in\{0,1,\dots,b-1\}.\]

Häufig notiert man die Koeffizienten \(n_0, \dots, n_{k-1}\) dieser Darstellung in Form eines Tupels:

\[n=(n_{k-1}n_{k-2}\dots n_1n_0)_b %\quad\text{ oder }\quad n=(n_{k-1},n_{k-2},\dots,n_1,n_0)_b\]

und nennt dies die \(\mathbf{b}\)-adische Darstellung der Zahl \(n\).

Ist \(n_{k-1}\ne 0\), so nennt man \(k\in\N\) die Stellenzahl der Zahl \(n\) in der \(b\)-adischen Darstellung.

Im Folgenden wollen wir einige Beispiele für unterschiedliche \(b\)-adische Zahldarstellung in Abhängigkeit der Basis diskutieren.

Beispiel 2.5 (b-adische Zahldarstellungen)

Wir betrachten in diesem Beispiel unterschiedliche Zahldarstellungen der natürlichen Zahl \(n=431\).

• Für die gewählte Basis \(b=10\) erhält man die übliche Dezimaldarstellung mit den Ziffern \(0,1,\dots,9\). Statt \((n_{k-1}\dots n_1n_0)_{10}\) schreiben wir typischerweise \(n_{k-1}\dots n_1n_0\). In diesem Fall gilt einfach:

  \[431 \ = \ 1\cdot 10^0 + 3\cdot 10^1 + 4\cdot10^2 \ = \ (431)_{10}.\]

• Für die Basis \(b=2\) hat man die Binärdarstellung mit den Ziffern \(0\) und \(1\), wie sie für die Zahldarstellung in Computern verwendet wird. In diesem Fall gilt:

  \[431 \ = \ 1\cdot 2^0 + 1\cdot 2^1 + 1\cdot 2^2 + 1\cdot 2^3 + 0\cdot 2^4 + 1\cdot 2^5 + 0\cdot 2^6 + 1\cdot 2^7 + 1\cdot 2^8 \ = \ (110101111)_2\]

• Für die Basis \(b=16\) hat man die Hexadezimaldarstellung. Als Ziffern benutzt man hierbei in der Regel \(0,1,\dots,9\),a,b,c,d,e,f oder \(0,1,\dots,9\),A,B,C,D,E,F. In diesem Fall gilt:

  \[431 \ = \ 15\cdot 16^0 + 10\cdot 16^1 + 1\cdot 16^2 \ = \ (1\texttt{AF})_{16}.\]

Wie Beispiel 2.5 zeigt, lässt sich eine natürliche Zahl äquivalent in unterschiedlichen Zahldarstellungen repräsentieren, wie beispielsweise die folgende \(27\)-Bit-Zahl:

\[(123456789)_{10} \ = \ (111010110111100110100010101)_2 \ = \ (75\texttt{BCD}15)_{16}.\]

Während Computer intern ausschließlich mit der binären Zahldarstellung operieren, wird in der Kryptographie häufig die Hexadezimaldarstellung zur Darstellung von Zahlen verwendet. Dies liegt zum Einen daran, dass diese Darstellung durch die größere Basis \(b = 16 > 10\) kompakter ist als die herkömmliche Zahldarstellung. Zum Anderen bildet die Hexadezimaldarstellung eine einfache Brücke zur Binärdarstellung, da jeweils zwei Zeichen unabhängig zu einem Byte (\(256 = 16^2\) mögliche Zahlen) zusammengefasst werden können und man anschließend die entstehenden Bytes nur noch konkatenieren muss, um die Binärdarstellung zu erhalten.

Bemerkung 2.1 (Konversion von Zahldarstellungen in Python)

1. In Python lassen sich Zahlen in Binärdarstellung durch Voranstellen der Zeichen 0b beispielsweise wie folgt definieren:

   n = 0b1011010011.
   

   Die Konversion einer natürlichen Zahl \(n\in\N\) in Binärdarstellung lässt sich durch bin(n){.python} realisieren. Mit int('0100111010', 2){.python} erhält man aus einer Binärzahl wieder eine natürliche Zahl in gewohnter Dezimaldarstellung.

2. In Python lassen sich Zahlen in Hexadezimaldarstellung durch Voranstellen der Zeichen 0x beispielsweise wie folgt definieren:

   n = 0xa3fc36a27b.
   

   Die Konversion einer natürlichen Zahl \(n\in\N\) in Hexadezimaldarstellung lässt sich durch hex(n){.python} realisieren. Mit int('13f45ac', 2){.python} erhält man aus einer Hexadezimalzahl wieder eine natürliche Zahl in gewohnter Dezimaldarstellung.

Mit Hilfe der Logarithmus-Funktion und der Abrundungsfunktion lässt sich die benötigte Anzahl an Stellen für eine \(b-\)adische Zahldarstellung exakt angeben, wie folgendes Lemma festhält.

Lemma 2.2 (Stellenanzahl)

Ist \(n\in\N\) eine natürliche Zahl und \(b\in\N, b \geq 2\) eine Basis, so hat \(n\) in der \(b\)-adischen Darstellung genau \(k\in \N\) Stellen mit:

\[k=\floor{\frac{\ln n}{\ln b}}+1.\]

Proof. Sei

\[n=\sum_{i=0}^{k-1}n_i\cdot b^i\quad\text{ mit }\quad n_i\in\{0,1,\dots,b-1\}\quad\text{ und }\quad n_{k-1}\ne 0.\]

Dann gilt

\[b^{k-1} \ \le \ n \ \le \ \sum_{i=0}^{k-1}(b-1)b^i \ = \ b^k-1 \ < \ b^k,\]

und damit \((k-1)\ln b\le \ln n<k \ln b\), also

\[k-1 \ \le \ \frac{\ln n}{\ln b} \ < \ k.\]

Dann ist

\[k-1 \ = \ \floor{\frac{\ln n}{\ln b}},\]

und damit

\[k \ = \ \floor{ \frac{\ln n}{\ln b}} + 1,\]

wie behauptet. ◻

Mit dem Landau-Symbol kann man die Stellenzahl einer natürlichen Zahl \(n\in\N\) also berechnen als

\[k \ = \ \left\lfloor\frac{\ln n}{\ln b}\right\rfloor+1.\]

Insbesondere ist \(k = O(\ln n)\), d.h. die Stellenzahl von \(n\) wächst wie \(\ln n\). Die Anzahl der Bits von \(n\) ist die Anzahl der Stellen in der Binärdarstellung und lässt sich konkret berechnen als \(\lfloor \frac{\ln n}{\ln 2}\rfloor +1\).