date-created: 2024-06-14 04:02:47 date-modified: 2024-11-20 09:10:01

| (5) | Elementare Zahlentheorie |

anchored to [[104.00_anchor_math]]

Overview:

In Mathe 2 haben wir diverse Gruppen bereits betrachtet, sind da aber auf Probleme oder undefinierte Zustände gestoßen [[math2_gruppen]]. Wir möchten diese jetzt ferner betrachten:

Teilbarkeit von Zahlen
- Betrachtung von Primzahlen in diesem Kontext
chinesischer Restsatz

| Definition (5.1) | ggT/gcd - größter gemeinsamer Teiler |

Siehe [[math2_Modulo#ggT, teilerfremd|ggT Mathe2]]

Seien jetzt $a_{1}, \dots, a_{r} \in Z$ irgendwelche Zahlen aus dem Bereich der ganzen Zahlen. Wir suchen jetzt gemeinsame Teiler für diese Menge:

Wir möchten folgende Eigenschaften betrachten:

[!Definition] größter gemeinsamer Teiler: Ist mindestens ein $a_{i} \neq = 0$ so ist der größte gemeinsame Teiler $g cd (a_{1}, \dots, a_{r})$ die größte natürliche Zahl, die alle $a_{1}, \dots, a_{r}$ teilt!

[!Definition] kleinste gemeinsames Vielfache: Sind jetzt alle $a_{i} \neq = 0$ , so beschreiben wir das kleinste gemeinsame Vielfache, oder auch $k g V (a_{1}, \dots, a_{r}), l c m (a_{1}, \dots, a_{r})$ die kleinste Zahl, die von allen $a_{1}, \dots, a_{r}$ geteilt wird.

Das heißt wir schauen nach einer Zahl, die von allen Werten in ${a_{1}, \dots, a_{r}}$ geteilt wird!

[!Important] Teilerfremde Werte $a_{1}, \dots a_{r}$ Sofern der $gg T (a_{1}, \dots, a_{r}) = 1, g cd (a_{1}, \dots, a_{r}) = 1$ heißen diese Werte $a_{1}, \dots, a_{r}$ dann teilerfremd

–> Also wir können nur 1 als möglichen Teiler der Menge betrachten, es gibt keinen größeren, gemeinsamen Teiler.

[!Important] paarweise teilerfremde Werte $a_{1}, \dots, a_{r}$ Ist jetzt der $gg T (a_{i}, a_{j}) = 1, \forall i, j, mit i \neq = j$ , heißen jetzt $a_{1}, \dots, a_{r}$ paarweise teilerfremd.

Also wenn wir zwei Werte betrachten und diese einen ggT von 1 haben, dann sind diese paarweise teilerfremd zueinander!

Diese Eigenschaft ist stärker als die vorherigen, das heißt es überwiegt in der Relevanz. Sei $6, 10, 15$ , dann sind die drei Werte teilerfremd, aber nicht paarweise teilerfremd ( denn $gg t (10, 15) = 5$ )

| Bemerkung (5.2) | Teilbarkeit

Seien jetzt $q, v, w \in Z, v \neq = 0$

[!Definition] Es gilt jetzt folgend: $(t ∣ v \land t ∣ w) ⟺ (t ∣ v \land t ∣ q \cdot v + w) ⟹ transitive Aussage$ Wir sehen hier folgend, dass bei dieser Umformung ein beliebiger Faktor $q$ angewandt werden kann, der die Eigenschaft nicht verletzt und es somit weiterhin gilt!

Es folgt hieraus mehr oder weniger:

[!Important] $⟹$
$> t ∣ v ⟹ \exists K_{1} \in Z : t \cdot k_{1} = v, > t ∣ w ⟹ \exists K_{1} \in Z : t \cdot k_{1} = w > \dots >$ Also wir können daraus jetzt noch folgern: $g cd (v, w) = g cd (v, q \cdot v + w)$

| Beweis der Teilbarkeit |

Seien jetzt $a_{0}, a_{1} \in Z : ∣ a_{0} ∣ > ∣ a_{1} ∣ \neq = 0$ und weiterhin $a_{1} \neq = a_{0}$ , denn sonst wäre der $g cd (a_{0}, a_{1}) = ∣ a_{1} ∣$ !

Wir suchen jetzt den $g cd (a_{0}, a_{1})$ ! $a_{0} ⟹ = = = = fortsetzen als Gleichung: a_{1} = a_{2} = = = a_{n - 1} = = = q_{1} \cdot a_{1} + (a_{2})_{bildet rest!} g cd (a_{1}, a_{0}) = g cd (a_{1}, q_{1} \cdot a_{1} + a_{2}) g cd (a_{1}, a_{2}) g cd (a_{2}, a_{3}) g cd (a_{3}, a_{4}) \dots q_{2} \cdot a_{2} + a_{3} q_{3} \cdot a_{3} + a_{4} \dots der Rest wird dabei immer kleiner \dots q_{n} \cdot a_{n} + 0 (erstes mal 0 als Rest) g cd (a_{n}, 0) = a_{n} beachte hierbei: (∣ a_{2} ∣<∣ a_{1} ∣<∣ a_{0} ∣)$ Wir haben hiermit bereits den Ablauf des euklidischen Algorithmus beschrieben und weiterhin direkt seine Korrektheit bestimmt / gezeigt.

(Erweiterter) Euklidischer Algorithmus

Ferner können wir jetzt noch den euklidischen Algorithmus betrachten:

Weitere Infos hier : [[104.12_erweiteter_euklidischer_algorithmus]]

![[104.12_erweiteter_euklidischer_algorithmus#Overview]]

Korollar (5.10) | Teilerfremde Abhängigkeiten |

[!Definition] Folgerungen für teilerfremde Zahlen Seien jetzt $a, b \in Z, \neq = 0; c \in Z$

1. $a, b$ teilerfremd $⟺$ $\exists s, t \in Z : s \cdot a + t \cdot b = 1$

2. $a, b$ teilerfremd $⟹$ falls gilt, dass $a ∣ b \cdot c$ , dann gilt auch $a ∣ c$

| Beweis |

Wir möchten zuerst 1 beweisen: $⟹ ⟸ gilt nach 5.5 von oben sei jetzt d = g cd (a, b), dann d ∣ a, d ∣ b$

folgend noch 2: $nach 5.5 gilt \exists s, t \in Z mit 1 = s \cdot a + t \cdot b ⟹ c = c \cdot 1 = s \cdot a \cdot c + t \cdot b \cdot c Da a ∣ a \land a ∣ b \cdot c ⟹ a ∣ s \cdot a \cdot c + t \cdot b \cdot c$

| Definition (5.11) | Primzahlen |

Wir möchten eine natürliche Zahl jetzt als Primzahl beschreiben, wenn folgend gilt:

[!Definition] Definition Primzahl Eine natürliche Zahl $p > 1$ heißt Primzahl, wenn sie nur genau $1 \land p$ als positive Teiler bestizt. Das heißt also:

sie ist nur durch sich selbst teilbar ( im Bereich der natürlichen Zahlen!)

sie ist durch 1 teilbar $g cd (k, p) = 1, \forall k \in {1, p \cdot 1}$

| Lemma (5.12) | Lemma von Euklid |

[!Important] Lemma von Euklid Sei $p \in P$ und weiter auch $a_{1}, \dots, a_{k} \in Z, p ∣ a_{1} \cdot \dots \cdot a_{k}$ dann folgt: $⟹ \exists j : p ∣ a_{j}$

| Beweis des Lemma |

Wir können das obige Lemma unter Anwendung der vollständigen Induktion beweisen: $I A : I S : Nach 5.10 gilt jetzt: k = 1 k - 1 \to K {falls p ∣ a_{k}, falls p \neq ∣ a_{k}, dann fertig dann ist g cd (p, a_{k}) = 1, da p \in P p ∣ a_{1} \cdot \dots \cdot a_{k - 1} (IV gilt!) es gibt also ein p ∣ a_{j} : j \in {1, \dots, k - 1}$

| Primfaktorzerlegung Anwenden |

Wir können die Tatsache, dass man jede $n \in N$ natürliche Zahl als Primfaktorzerlegung darstellen soweit anwenden, dass es damit möglich wird etwa den [[#Definition (5.1) ggT/gcd - größter gemeinsamer Teiler]] und auch den [[#kgv]] einfach damit berechnen zu können:

Primfaktorzerlegung:

Wir können eine beliebige Zahl so oft zerlegen, bis wir nur noch nicht-teilbare Faktoren in dem Produkt haben und somit

Das heißt demnach, dass wir eine beliebige Zahl $n \in N ∖ {0}$ so aufsplitten könnne, dass folgend gilt: $⟹ \exists m_{i} \in N_{0}, p_{i} \in P :$

Das heißt ferner, wir können eine beliebige natürliche Zahl in kleinere Teile aufzusplitten. Dabei sollten dann nur noch Primzahlen und Faktoren dieser vorhanden sein.

Beispielsweise: $28 = 2 \cdot 2 \cdot 7 = 2^{2} \cdot 7$

Es gibt hierbei einige vereinfachbare Strukturen, um die Primzahlen einfacher zu extrahieren:

$P$	$n$	bsp
2	$n$ ist gerade
3	quersumme(n) = $3 \cdot c$	$12 = 1 + 2 = 3 \to 1!$
5	letzte Ziffer in der Zahl $0 ∣ 5$

Am Ende werden meist folgende Zahlen noch angebracht / dargestellt: $7, 11$

[!Definition] Vrgehen zur BErechnung der Primfaktorzerlegung:

Wir fangen an und schauen, ob wir die gegebene Zahl $n$ durch eine der obigen Primzahlen teilen können.

Wir notieren, die Primzahl, durch die wir geteilt haben und betrachten jetzt den Rest dieser Division.

Wir betrachten den Rest und schauen wieder, wie wir diesen entsprechend teilen könne –> notiere die Primzahl und führe das Verfahren fort, bis wir eine vollständige Zerlegung haben

| Primfaktorzerlegung zur Bestimmung ggT |

[!Important] Primfaktorzerlegung zur Bestimmung des ggT Unter Umständen lässt sich der ggT von zwei Zahlen schneller berechnen, indem wir sie in ihrer Primfaktorzerlegung darstellen und anschließend schauen, inwiefern die Zerteilungen übereinstimmen

Wir können so den ggT dann daraus ziehen, indem wir schauen, welches Produkt in der Primfaktorzerlegung bei beiden Zahlen auftritt Betrachte BSP $A = 28, B = 42$ $28 = 2^{2} \cdot 7 = 2 \cdot 2 \cdot 7 42 = 2 \cdot 3 \cdot 7 g c d (28, 42) = 2 \cdot 7 = 14 ⟹ weil das Produkt in der Zerlegung beider Zahlen aufgetreten ist$

ggt alles was die beiden Zahlen gemeinsam haben!

| Primfaktorzerlegung zur Bestimmung kgV |

Hierfür gehen wir ähnlich vor ( im Ansatz zumindest ), werden also auch wieder schauen, dass wir die Primfaktorzerlegung nehmen und dann gucken dass wir mit allen gewählten Primzahlen beide Zahlen konstruieren können.

[!Task] Ansatz: Suche höchste Potenz jeder Primzahl in beiden Zerlegungen –> Dabei müssen wir die Primzahlen aus beiden Zahlen, aus denen wir den KgV (lcm) bilden möchten, übernehmen!

Ein Beispiel bildet eine Abgabe in [[104.88_assignment07]]

| Theorem (5.13) | Fundamentalsatz der elementaren Zahlentheorie |

Zu jeder natürlichen Zahl $n \geq 2$ gibt es endlich viele paarweise verschiedene Primzahlen $p_{1}, \dots, p_{k} \in P$ und natürliche Zahlen $e_{1}, \dots, e_{k}$ mit $n = p_{1}^{e_{1}} \cdot \dots \cdot p_{k}^{e_{k}}$ Die $P_{i}$ heißen dann Primfaktoren bzw Primteiler von $n$ .

Diese Darstellung einer natürlichen Zahl ist eindeutig (bis auf die Reihenfolge).

| Beweis | Fundamentalsatz el. Zahlentheorie |

| Beweis | Korrektheit |

Wir können dies folgend mit der verschärften Induktion beweisen.

[!Important] Intuition verschärfte Induktion Mit der verschärften Induktion möchten wir von allen vorherigen Ergebnissen, die wir gesetzt haben auf die $n + 1$ -Struktur ableiten, also $2, 3, \dots, n \to n + 1$

$IA: IS: IV: Nach IV sind auch: ⟹ n = 2 ist Primzahl 2, \dots, n \to n + 1 sei jetzt n \geq 2 Aussage gelte f \overset{u}{¨} r 2, \dots, n zz: Aussage gilt dann auch f \overset{u}{¨} r n + 1 {ist n + 1 \in P ist n + 1 \neq \in P so gilt die Aussage so ist n + 1 = a \cdot b : a, b \in {2, \dots, n} a \land b ein Produkt von P n + 1 ist ebenfalls ein Produkt von P$

| Beweis | Eindeutigkeit |

Wir möchten noch zeigen, dass diese Primfaktorzerlegung tatsächlich eindeutig ist!:

( Wir möchten dafür annehmen, dass zwei verschiedene Darstellungen existieren ( was nicht möglich ist)). Sei jetzt $n = p_{1}^{e_{1}} \cdot \dots p_{k}^{e_{k}} = p_{i}, q_{i} \in P, ⟹ \exists l : e_{l} \neq = f_{l} ⟹ = p_{l} ⟹ ⟹ ⟹ q_{1}^{f_{1}} \cdot \dots \cdot q_{m}^{f_{m}} wobei sie verschieden sind! Weiterhin e_{i}, p_{j} \in N Nach 5.12 ( also dem Lemma ist eine Kombination entsprechend teilbar!) jedes Pi teils eines der Qi ! p_{i} = q_{i}, da q_{j} \in P, ebenso umgekehrt f \overset{u}{¨} r p_{i} {p_{1}, \dots, p_{j}} = {q_{1}, \dots, q_{m}}, k = m es sei bzw ist jetzt: p_{i} = q_{i} \forall i = 1, \dots, k noch zu zeigen, dass die Exponenten gleich sein m \overset{u}{¨} ssen: e_{i} = f_{i} so sei e_{l} < f_{l} teile beide Seiten den Primfaktorzerlegungen P_{l}^{e_{l}} : p_{1}^{e_{1}} \cdot \dots \cdot p_{l - 1}^{e_{l - 1}} \cdot P_{l + 1}^{e_{l + 1}} \dots p_{k}^{e_{k}} = p_{1}^{f_{1}} \cdot \dots \cdot p_{l - 1}^{f_{l - 1}} \cdot p_{l}^{f_{l} - e_{l}} \cdot p_{l + 1}^{f_{e + 1}} \cdot \dots p_{k}^{f_{k}} teil rechte Seite, alsu auch die linke also nach 5.11 ein p_{j}, j \neq = l dann gilt aber p_{l} = p_{j} \neq = nicht verschieden e_{i} = f_{i} \forall i = 1, \dots, k$

| Korollar (5.14) | Euklid unendlich viele Primzahlen

[!Definition] Es gibt unendlich viele Primzahlen

Wir möchten diese Aussage gleich beweisen:

Angenommen es gibt nur endliche viele Primzahlen $p_{1}, \dots, p_{n} \in P$ Dann bilden wir exemplarisch eine Primfaktorzerlegung einer Zahl $a$ : $a = p_{1} \cdot \dots \cdot p_{n + 1}$ Gemäß der vorherigen Betrachtung [[#Theorem (5.13) Fundamentalsatz der elementaren Zahlentheorie|5.13]] : $\exists q \in P : q ∣ a$ Dadurhc gilt dann: $q = ⟹ = p_{i} f \overset{u}{¨} r ein i in der Zerlegung q ∣ a - p_{1} \cdot \dots \cdot p_{n = 1} was im Widerpsruch steht! □$

| Chinesischer Restsatz |

Zum Berechnen von diversen Kongruenz-Gleichungen können wir folgend den chinesischen Restsatz anwenden:

Mehr hier: [[104.13_chinesischer_restsatz]]

![[104.13_chinesischer_restsatz#Overview]]

| Eulersche $φ$ -Funktion |

Wir haben sie bereits in Mathe 2 in den Restklassen eingebracht und betrachtet: ![[math2_Modulo#Bemerkung $(ma t hbb Z_{m} *, v a r p hi (m))$ ]] (Als kleiner Revisit zur eulerschen Funktion $φ$ -Funktion):

[!Definition] Definition $φ$ -Funktion Wir können für $n \in N$ $φ (n)$ folgend definieren: $∣ {a \in N ∣ 1 \leq a \leq n \land g cd (a, n) = 1} ∣$ Das heißt, wir beschreieben die Menge der zu $n$ teilerfremden Zahlen zwischen $1 \to n$ ( Also einfach alle Zahlen innerhalb eines Intervalles von 1 - bis $n$ , wo wir wissen, dass sie [[104.11_elementare_zahlentheorie#Beweis der Teilbarkeit|teilerfremd]] zu $n$ sind!)

Wir haben dabei die komplette Restklasse auch dadurch beschrieben: $φ (n) := ∣ Z_{n}^{*} ∣$

| Besonderheit bei Primzahlen $P$ |

[!Important] Besonderheit bei $P$ Sei $\in P$ dann gilt bei der eulerschen Funktion folgend: $φ (p) = p - 1$

| Bemerkung (5.19) | $φ (n)$ einfacher Berechnen |

Wir können unter dieser Betrachtung und Anwendung jetzt folgend definieren:

[!Definition] Zerlegung von $φ (n)$ in kleinere Produkte Sei jetzt $M = m_{1} \cdot \dots \cdot m_{n}$ , wobei hier für alle $m_{i} ∣ i \in {1, n}$ gilt, dass sie teilerfremd sind!

Es folgt hieraus jetzt folgend wieder eine Aufteilung in kleinere Produkte ( wir müssen irgendwie das $M$ in kleinere Teile aufsplitten können) $φ (M) = φ (m_{1}) \cdot \dots \cdot φ (m_{n})$

Insbesondere ist jetzt weiter: $n = p_{1}^{e_{1}} \cdot \dots \cdot p_{k}^{e_{k}}$ , wobei hier folgend $p_{i}$ paarweise verschiedene $P$ Primzahlen sind, und weiterhin sind die Potenzen $e_{i} \in N$ ( also es ist wieder eine Primfaktorzerlegung).

Wir können daraus jetzt $φ (n)$ relativ einfach berechnen: $φ (n) = φ (p_{1}^{e_{1}}) \cdot \dots \cdot φ (p_{k}^{e_{k}}$
wir können sie als eine Primfaktorzerlegung darstellen und somit den Term vereinfachen $(p_{1} - 1) \cdot p_{1}^{e_{1}} \cdot \dots \cdot (p_{k} - 1) \cdot p_{k}^{e_{k - 1}}$

| Beispiel | $φ (19845)$

Wir suchen jetzt also für folgende Zahle $φ (19845)$ die Menge von teilerfremden Zahlen, zwischen diesem Intervall von $1 - 19845$ :

[!Definition] Vorgehen durch obige Betrachtung

$M (19845)$ in kleinere Primfaktoren zerteilen und so die folgende Form erhalten $M = p_{1}^{e_{1}} \cdot p_{2}^{e_{2}} \cdot \dots \cdot p_{n}^{e_{n}}$

nimm jetzt jeweils die Primzahlen aus der vorherigen Gleichung und wende $φ (p) = p - 1$ an, also etwa $(p_{1} - 1) \cdot p_{1}^{e_{1}} \cdot \dots \cdot (p_{k} - 1) \cdot p_{k}^{e_{k - 1}}$

wir können daraus jetzt ein vereinfachtes Produkt bilden: ( bsp: $2 \cdot 3^{3} \cdot 3 \cdot 5^{0} \cdot 6 \cdot 7^{1} = 9072$ ) Dadurch erhalten wir $φ (M)$

| Anwendung Zahlentheorie | RSA

Was already covered and explained in : [[netSec_RSA]] ![[netSec_RSA#RSA Key Generation card]]

[!Tip] Intuition RSA Mit dem RSA Verfahren können wir primär ein asymmetrisches Verfahren zur Verschlüsselung umsetzen. Dabei setzt es auf eine Struktur von Public/Private Key und wendet für beide Keys zwei große Primzahlen an, die genutzt werden, um diese Struktur umzusetzen.

| Grundstruktur | Schlüsselerzeugung |

Sofern wir jetzt ein Paar von Public/Private Key berechnen / erzeugen möchten, gehen wir folgend vor:

[!Definition] Schlüsselerzeugung | RSA

wähle zwei große $p, q \in P$

bilde jetzt $n = p \cdot q$

Berechne jetzt $φ (n) = (p - 1) \cdot (q - 1)$ , siehe [[104.01_math_tutorial# $v a r p hi (n)$ ]]

wähle jetzt irgendein $e$ , das teilerfremd zu $φ (n)$ ist!

bestimme jetzt noch ein $d := 0 < d < φ (n) : e \cdot d mod (φ (n)) = 1$

Diesen Wert können wir ausrechnen unter Anwendung des [[104.12_erweiteter_euklidischer_algorithmus|EEA]], wobei $d = (e mod (φ (n)))^{- 1}$ -> also das Inverse zu der Berechnung von $e mod (φ (n))$ !

somit gilt dann: $e \cdot d = 1 + k \cdot φ (n)$ ! –> Wir müssen also die WErte wissen, sonst ist es sehr schwer das zu berechnen!

der Public Key bildet jetzt: $(n, e)$ , private key $d$

[!Definition] Verschlüsseln durch genutzte Angenommen wir haben jetzt Person X, die etwas an das vorher definierte Konstrukt mit einem Pub/Priv Key, verschicken möchte: Wir gehen folgend vor:

Nachricht $m$ ist als Zahl gegeben, wobei $0 \leq m < n$

berechne jetzt: $c = m^{e} mod (n))$

sende dann c an Recipient –> they are able to unwind this equation later!

[!Definition] Entschlüsseln einer Nachricht:

erhalte $v$

berechne jetzt: $c^{d} mod (n) = m$ –> d denotes private key!

Warum gilt jetzt $c^{d} mod (n) = m$ ?: Wir beweisen folgend: $c^{d} = (m^{e})^{d} = m^{e d} = m^{1 + k \cdot φ (n)} = m \cdot (m^{φ (n)})^{k} \equiv 1 mod (n) = m mod (n) Satz von Euler!$

| Warum $φ (n)$ und $n$ nicht gemeinsam bekannt sein sollten:

$n$ wird immer als öffentlicher Schlüssel gegeben, weil man diesen Modul brauch, um entsprechend mit dem öffentlichen Key $e$ verschlüsseln zu können. Dabei ist $n = q \cdot p$ , die beiden Primzahlen, die unbekannt sein sollen. Ferner ist $φ (n) = q - 1 \cdot p - 1$ , was somit nicht geteilt werden sollte, weil wir sonst $q, p$ berechnen können, wenn man $n$ und $φ (n)$ kennt:

Hier ein Eintrag, von welchem ich die Umformung, zum berechnen von $p, q$ abgeleitet / genommen habe: Source: crypto.stackexchange.com

Why is it important that phi(n) is kept a secret, in RSA?

From the definition of the totient function, we have the relation:

φ(n)=(p−1)(q−1)=pq−p−q+1=(n+1)−(p+q)

It then easily follows that:

(n+1)−φ(n)=p+q

(n+1)−φ(n)−p=q

And you know from the definition of RSA that:

n=pq

Substituting one into the other, you can derive:

n=p(n+1−φ(n)−p)=−p2+(n+1−φ(n))p

With some rearranging, we obtain:

p2−(n+1−φ(n))p+n=0

This is a quadratic equation in p, with:

a=1b=−(n+1−φ(n))c=n

Which can be readily solved using the well-known quadratic formula:

p=−b±|b|2−4ac2a=(n+1−φ(n))±|n+1−φ(n)|2−4n2

Because of symmetry, the two solutions for p will in fact be the two prime factors of n.

Example for factoring $q, p$

Here is a short example, let n=13×29=377 and φ(n)=(13−1)×(29−1)=12×28=336. Using the quadratic equation shown above, we need to use the following coefficients for the equation:

a=1b=−(377+1−336)=−42c=377

Thus we have the following quadratic to solve:

p2−42p+377=0 ⟹ p=42±|−42|2−4×3772=42±162

Finally, we calculate the two solutions, which are the two prime factors of 377 as expected:

262=13 and 582=29

[!Important] Conclusion In conclusion, knowledge of φ(n) allows one to factor n in time O(1). The other answers are equivalent, in that knowing d achieves the same result (loss of any security properties of RSA), but just for completeness I thought it would be a good idea to show how n can be factored with this information.

scattered-lenity

date-created: 2024-06-14 04:02:47 date-modified: 2024-11-20 09:10:01