Formelblad

$[a] = {b \in A : a R b}$ $a ∣ b : a delar b$ $sgd (a, b) = 1 \land a ∣ b c ⟹ a ∣ c$
Om $a$ är ett primtal och $a ∤ b$ så är $sgd (a, b) = 1$
${x, y} = {c u - b n, c v + a n}, n \in Z$
$(a + b)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) a^{n - k} b^{k}$
$Q : Rationella tal$ $R : Reella tal$ $\emptyset : Tomma mängden$

Sats 7.11

En sammanhängande graf $G$ innehåller en Eulercykel om och endast om alla gradtal i $G$ är jämna.

Sats 7.12

Låt $u, v \in V, u \neq v$ vara två noder i en sammanhängande graf $G = (V, E)$ . $G$ innehåller minst en Eulerväg från $u$ till $v$ om och endast om $d_{u}$ och $d_{v}$ är udda och för alla andra noder $w \in V$ gäller att $d_{w}$ är jämnt.

Sats 5.22

En diofantisk ekvation $a x + b y = c$ är lösbar $⟺ sgd (a, b) ∣ c$

Summor	Kombinatorik	Euklides
$\sum_{i = a}^{b} (A_{i} + B_{i}) = \sum_{i = a}^{b} A_{i} + \sum_{i = a}^{b} B_{i}$ $\sum_{x \in M} x = 1 + 2 + 3$ $\prod_{i = 1}^{n} a_{i} = a_{1} * a_{2} * \dots * a_{n}$ Aritmetisk summa: $\sum_{i = 1}^{n} a_{i} = \frac{n}{2} * (a_{1} + a_{n})$	$(\binom{n}{k}) = \frac{n!}{k! (n - k)!}$ $_{n} P_{k} = \frac{n!}{(n - k)!}$	$sgd (a, b) = r_{n}$ $a = b \cdot q_{1} + r_{1}$ $b = r_{1} \cdot q_{2} + r_{2}$ $r_{1} = r_{2} \cdot q_{3} + r_{3}$ $⋮$ $r_{n - 2} = r_{n - 1} \cdot q_{n} + r_{n}$ $r_{n - 1} = r_{n} \cdot q_{n + 1} + 0$

Begrepp	Förklaring	Notation
Antisymmetrisk	$(a R b \land b R a) ⟹ a = b \forall a, b \in A$
Associativitet	$(a * b) * c = a * (b * c)$
Bijektiv	Injektiv och surjektiv
Bipartit graf	Graf då noder kan delas in i två grupper och alla kanter går mellan grupperna
Diofantisk ekv.	Bestående av och lösning med heltal i $Z$
Disjunktion	"eller"	$\lor$
Ekvivalensrelation	Reflexiv, symmetrisk och transitiv
Gradtal	Antalet kanter som ansluter till en nod	$d_{v}$
Kardinalitet	Storleken/antalet element i en mängd	$\| A \|$
Konjunktion	"och"	$\land$
Kvantifiera	Bind variablerna i ett predikat för att få ett sanningsvärde	$\forall$ , $\exists$
Identitet	$e$ sådant att $a * e = a \forall a \in A$	$e$
Inducerad delgraf	$\tilde{G} = (\tilde{V}, \tilde{E})$ är inducerad delgraf till $G = (V, E)$ då $\forall x, y \in \tilde{V} : {x, y} \in E \to {x, y} \in \tilde{E}$
Injektiv	Alla funktionsärden $f (x)$ är unika
Invers	Funktion: $g$ är invers till $f$ om $f (g (x)) = x$ Operator: $a * a^{- 1} = e$ där $e : identitet på A$	$f^{- 1}$ $a^{- 1}$
Partiell ordning	Reflexiv, antisymmetrisk och transitiv
Reflexiv	$a R a \forall a \in A$
Specificera	Specificera variabeln i ett predikat för att få ett sanningsvärde
Surjektiv	$f : A \to B, \forall b \in B \exists a \in A : f (a) = b$
Symmetrisk	$a R b ⟹ b R a \forall a, b \in A$
Transitiv	$(a R b \land b R c) ⟹ a R c \forall a, b, c \in A$

Blandad notation: $D_{f}$ , $V_{f}$

Pasted image 20241023194014.png

Pasted image 20241025170216.png

Kryptering

RSA: Välj två stora primtal* $p_{s}, q_{s}$ och ett heltal $a_{s}$ sådant att $sgd (a_{s}, Φ (p_{s} q_{s})) = 1$ . Inversen till $a_{s} mod Φ (p_{s} q_{s})$ betecknas $b_{s}$ .
Tillsammans är bildar dessa heltal en sluten nyckel. Produkten $p_{s} q_{s}$ och $a_{s}$ bildar en motsvarande öppen nyckel.

Inversen: $a_{s} b_{s} \equiv 1 mod Φ (p_{s} q_{s})$
Enkryptering: $y = x^{a_{s}} mod p_{s} q_{s}$
Dekryptering: $y^{b_{s}} = (x^{a_{s}})^{b_{s}} = x^{a_{s} b_{s}} = x^{n Φ (p_{s} q_{s}) + 1} = (x^{Φ (p_{s} q_{s})})^{n} x = 1^{n} x = x$
Hashing: $z = h (x)$
Signering: $w = z^{b_{s}}$
Validering: $w^{a_{s}} mod p_{s} q_{s} = (z^{b_{s}})^{a_{s}} = z^{a_{s} b_{s}} = z^{n Φ (p_{s} q_{s}) + 1} = z$

5.28

\begin{aligned} 132 & = 2 \cdot 66 \\ = 2^{2} \cdot 3 \cdot 11 \end{aligned}

\begin{aligned} Φ (132) & = Φ (2^{2}) Φ (3) Φ (11) \\ = 2 \cdot 2 \cdot 10 \\ = 40 \end{aligned}

\begin{aligned} 1121 & = 132 \cdot 8 + 65 \\ 132 & = 65 \cdot 2 + 2 \\ 65 & = 2 \cdot 32 + 1 \end{aligned}

$sgd (1121, 132) = 1$
$1121 = 40 \cdot 28 + 1$

\begin{aligned} m & \equiv 1121^{1121} mod 132 \\ \equiv (1121^{40})^{28} \cdot 1121 mod 132 \\ \equiv 1^{28} \cdot 1121 mod 132 (Eulers sats) \\ \equiv 1121 mod 132 \\ \equiv 132 \cdot 8 + 65 mod 132 (Faktorisering ovan) \\ \equiv 65 mod 132 \end{aligned}

$m = 65 \cdot 132 n n \in Z$

Minsta positiva $m = 65$ då $n = 0$

Svar: $Φ (132) = 40, m = 65$