Einführung in die Zahlentheorie

Dozent:

Prof. Dr. Michael Eichberg

Version:

2024-05-09

Quelle:

Im Wesentlichen Cryptography and Network Security - Principles and Practice, 8th Edition, William Stallings

Teilbarkeit

• Ein \(b\) ungleich Null teilt \(a\) wenn \(a = mb\) für ein beliebiges \(m\) und \(a\), \(b\) und \(m\) ganze Zahlen sind.

• \(b\) teilt \(a\) wenn es keinen Rest bei der Division gibt.

• Die Notation \(b|a\) bedeutet, dass \(b\) \(a\) teilt.

• Wenn \(b|a\) gilt, dann sagen wir auch, dass \(b\) ein Teiler von \(a\) ist.

Eigenschaften der Teilbarkeit

• Wenn \(a|1\), dann gilt \(a = \pm 1\).

• Wenn \(a | b\) und \(b|a\), dann gilt \(a = \pm b\).

• Jedes \(b \neq 0\) teilt \(0\).

• Wenn \(a | b\) und \(b|c\), dann \(a|c\).

Eigenschaften der Teilbarkeit

Wenn \(b | g\) und \(b|h\), dann \(b|(mg+nh)\) für beliebige ganze Zahlen \(m\) und \(n\).

Teilungsalgorithmus

Sei eine beliebige positive ganze Zahl \(n\) gegeben und eine beliebige ganze Zahl \(a \geq 0\), so erhält man bei der Division von \(a\) durch \(n\) einen ganzzahligen Quotienten \(q\) und einen nicht negativen, ganzzahligen Rest \(r\), die der folgenden Beziehung gehorchen:

Teilungsalgorithmus für negative \(a\)

Euklidischer Algorithmus

Eine der grundlegenden Techniken der Zahlentheorie.

Verfahren zur Bestimmung des größten gemeinsamen Teilers (GGT) von zwei positiven ganzen Zahlen.

Größter Gemeinsamer Teiler (GGT)

(Greatest Common Divisor (GGT))

• Der größte gemeinsame Teiler von zwei ganzen Zahlen \(a\) und \(b\) ist die größte ganze Zahl, die sowohl \(a\) als auch \(b\) teilt.

• Wir verwenden die Schreibweise \(ggt(a,b)\) für den GGT von \(a\) und \(b\).

• Wir definieren \(ggt(0,0) = 0\).

• Die positive ganze Zahl \(c\) wird als GGT von \(a\) und \(b\) bezeichnet, wenn:

  • \(c\) ein Teiler von \(a\) und \(b\) ist

  • jeder Teiler von \(a\) und \(b\) ein Teiler von \(c\) ist

Alternative Definition des GGT

GGT und relativ prim

Wir stellten fest:

Zwei ganze Zahlen \(a\) und \(b\) sind relativ prim, wenn ihr einziger gemeinsamer positiver ganzzahliger Faktor 1 ist.

\(a\) und \(b\) sind relativ prim wenn \(ggt(a,b)=1\)

Euklidischer Algorithmus

Der Modulus

Wenn \(a\) eine ganze Zahl und \(n\) eine positive ganze Zahl ist, dann definieren wir \(a\; mod\; n\) als Rest der Division von \(a\) durch \(n\). Die ganze Zahl \(n\) wird als Modulus bezeichnet.

Somit gilt für jede ganze Zahl \(a\):

Modulare Arithmetik (kongruent modulo \(n\))

• Zwei ganze Zahlen \(a\) und \(b\) werden als kongruent modulo \(n\) bezeichnet, wenn \((a\; mod\; n) = (b\; mod\; n)\)

• Wir verwenden die Schreibweise \(a \equiv b(mod\; n)\).

• Beachten Sie, dass, wenn \(a \equiv 0 (mod\; n)\) ist, dann gilt \(n|a\).

Eigenschaften der Kongruenz

1. \(a \equiv b (mod\; n)\) wenn \(n|(a-b)\)

2. \(a \equiv b (mod\; n) \Rightarrow b \equiv a (mod\; n)\)

3. \(a \equiv b (mod\; n)\) und \(b \equiv c (mod\; n) \Rightarrow a \equiv c (mod\; n)\)

\(a \equiv b (mod\; n)\) wenn \(n|(a-b)\) — Erklärt

Wenn \(n|(a - b)\), dann gilt \((a - b) = kn\) für ein \(k\)

• Wir können also schreiben \(a=b+kn\).

• Deshalb gilt \((a\; mod\; n)\) =

  (Rest wenn \(b + kn\) geteilt wird durch \(n\)) =

  (Rest wenn \(b\) geteilt wird durch \(n\)) =

  \((b\; mod\; n)\)

Eigenschaften der modularen Arithmetik

1. \([(a\; mod\; n) + (b\; mod\; n)]\; mod\; n = (a + b)\; mod\; n\)

2. \([(a\; mod\; n) - (b\; mod\; n)]\; mod\; n = (a - b)\; mod\; n\)

3. \([(a\; mod\; n) \times (b\; mod\; n)]\; mod\; n = (a \times b)\; mod\; n\)

\([(a\; mod\; n) + (b\; mod\; n)]\; mod\; n = (a + b)\; mod\; n\) — Erklärt

Definiere \((a\; mod\; n) = r_a\) und \((b\; mod\; n) = r_b\).

Dann können wir:

• \(a = r_a + jn\) für eine ganze Zahl \(j\) und

• \(b = r_b + kn\) für eine ganze Zahl \(k\) schreiben.

Dann gilt:

Modulare Arithmetik (Beispiele für Eigenschaften)

Addition Modulo 8

Multiplikation Modulo 8

for i in range(0,8):
    print(str(i)+", ",end="")
for j in range(0,8):
    v = (i*j) % 8
    if v == 1:
        v = "*"+str(v)+"*"
    else:
        v = str(v)
    print(v+",",end="")
print()

Additive und Multiplikative Inverse Modulo 8

Euklidischer Algorithmus - neu betrachtet

def Euclid(a,b):
    if (b = 0) then
        return a;
    else
        return Euclid(b, a mod b);

ggt(10,6)
    ↳ ggt(6,4)
        ↳ ggt(4,2)
            ↳ ggt(2,0)
2              ↩︎

Erweiterter Euklidischer Algorithmus

• Erforderlich für Berechnungen im Bereich der endlichen Körper und Verschlüsselungsalgorithmen wie RSA.

• Für zwei ganze Zahlen \(a\) und \(b\) berechnet der erweiterte euklidische Algorithmus den GGT \(d\), aber auch zwei zusätzliche ganze Zahlen \(x\) und \(y\), die die folgende Gleichung erfüllen:

Erweiterter Euklidischer Algorithmus
Systematische Berechnung für ggt(710,310)

Umgestellt:

Erweiterter Euklidischer Algorithmus - systematische Berechnung

\(x = 7\) und \(y = -16\)

Erweiterter Euklidischer Algorithmus - Formeln

Wir nehmen an, dass wir bei jedem Schritt \(i\) die ganzen Zahlen \(x_i\) und \(y_i\) finden können, die folgende Bedingung erfüllen: \(r_i = ax_i + by_i\).

Erweiterter Euklidischer Algorithmus

Primzahlen

• Primzahlen haben als Teiler nur 1 und sich selbst.

• Sie können nicht als Produkt von anderen Zahlen geschrieben werden.

• Jede ganze Zahl \(a > 1\) kann auf eindeutige Weise faktorisiert werden als: \(a=p_1^{a_1} \times p_2^{a_2} \times p_t^{a_1}\) wobei \(p_1 < p_2 < . . . < p_t\) Primzahlen sind und wobei jedes \(a_i\) eine positive ganze Zahl ist.

  \(a = \displaystyle \prod_{p \in P} p^{a_p}\qquad wenn\; a_p \geq 0\)

• Dies ist als Fundamentalsatz der Arithmetik bekannt.

Fermats (kleines) Theorem

Besagt folgendes:

• Wenn \(p\) eine Primzahl und \(a\) eine positive ganze Zahl ist, die nicht durch \(p\) teilbar ist, dann \(a^{p-1} \equiv 1 (mod\;p)\)

Alternative form:

• Wenn \(p\) eine Primzahl und \(a\) eine positive ganze Zahl ist, dann ist \(a^p \equiv a(mod\; p)\)

Eulers Theorem

besagt, dass für jedes \(a\) und \(n\), die relativ prim sind:

Eine alternative Form ist:

Miller-Rabin-Primzahltest

• Viele kryptografische Algorithmen erfordern eine oder mehrere sehr große Primzahlen nach dem Zufallsprinzip.

• Der Miller-Rabin-Primzahltest ist ein probabilistischer Primzahltest, der schnell und einfach ist.

• Hintergrund: Jede positive ungerade ganze Zahl \(n \geq 3\) kann ausgedrückt werden als:

  \(n-1 = 2^kq \qquad mit\; k > 0, q\; ungerade\)

Miller-Rabin Algorithmus

TEST(n, k) # n > 2, eine ungerade ganze Zahl,
           #        die auf Primalität geprüft wird
           # k,     die Anzahl der Testrunden

let s > 0 and d odd > 0 such that n−1 = pow(2,s)*d
repeat k times:
    a ← random(2, n−2)
    x ← pow(a,d) mod n
    repeat s times:
        y ← sqr(x) mod n
        if y = 1 and x ≠ 1 and x ≠ n−1 then return “composite”
        x ← y
    if y ≠ 1 then return “composite”
return “probably prime”

Deterministische Primzahltests

• Vor 2002 gab es keine bekannte Methode, um für sehr große Zahlen effizient zu beweisen, dass diese Primzahlen sind.

• Alle verwendeten Algorithmen lieferten ein probabilistisches Ergebnis.

• Im Jahr 2002 entwickelten Agrawal, Kayal und Saxena einen Algorithmus, der effizient bestimmt, ob eine gegebene große Zahl eine Primzahl ist:

  • Auch bekannt als AKS-Algorithmus.

  • Er scheint nicht so effizient zu sein wie der Miller-Rabin-Algorithmus.

Chinesischer Restsatz Chinese Remainder Theorem (CRT)

• Wurde vermutlich von dem chinesischen Mathematiker Sun-Tsu um 100 n. Chr. entdeckt [1].

• Eines der nützlichsten Ergebnisse der Zahlentheorie.

• Es besagt, dass es möglich ist, ganze Zahlen in einem bestimmten Bereich aus ihren Residuen modulo einer Menge von paarweise relativ primen Moduli zu rekonstruieren.

• Kann auf verschiedene Weise formuliert werden.

Chinesischer Restsatz - Beispiel in \(Z_{10}\)

Nehmen wir an, die (relativ prim/koprimalen) Faktoren einer Zahl \(x\): \(m_1 = 2\) und \(m_2 = 5\) sind und

Da \(x\; mod \;2 = 0\) ist muss \(x\) eine gerade Zahl sein; außerdem ist \(x\; mod\; 5 = 3\).

Die eindeutige Lösungn in \(Z_{10}\) ist: \(8\).