From a04efb8ee3eef6ec32b1381801ee244744db1201 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Andreas=20M=C3=BCller?= <andreas.mueller@ost.ch>
Date: Tue, 2 Mar 2021 10:23:02 +0100
Subject: division in F_p

---
 vorlesungen/slides/4/division.tex | 62 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 62 insertions(+)
 create mode 100644 vorlesungen/slides/4/division.tex

(limited to 'vorlesungen/slides/4/division.tex')

diff --git a/vorlesungen/slides/4/division.tex b/vorlesungen/slides/4/division.tex
new file mode 100644
index 0000000..aeab1e3
--- /dev/null
+++ b/vorlesungen/slides/4/division.tex
@@ -0,0 +1,62 @@
+%
+% division.tex
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\begin{frame}[t]
+\frametitle{Division in $\mathbb{F}_p$}
+\setlength{\abovedisplayskip}{5pt}
+\setlength{\belowdisplayskip}{5pt}
+\vspace{-20pt}
+\begin{columns}[t,onlytextwidth]
+\begin{column}{0.48\textwidth}
+\begin{block}{Inverse {\bf berechnen}}
+Gegeben $a\in\mathbb{F}_p$, finde $b=a^{-1}\in\mathbb{F}_p$
+\begin{align*}
+&& a{\color{red}b} &\equiv 1 \mod p
+\\
+&\Leftrightarrow& a{\color{red}b}&=1 + {\color{red}n}p
+\\
+&&a{\color{red}b}-{\color{red}n}p&=1
+\end{align*}
+Wegen
+$\operatorname{ggT}(a,p)=1$ gibt es
+$s$ und $t$ mit
+\[
+sa+tb=1
+\Rightarrow
+{\color{red}b}=s,\;
+{\color{red}n}=-t
+\]
+$\Rightarrow$ Die Inverse kann mit dem euklidischen Algorithmus
+berechnet werden
+\end{block}
+\end{column}
+\begin{column}{0.48\textwidth}
+\begin{block}{Beispiel in $\mathbb{F}_{1291}$}
+Finde $47^{-1}\in\mathbb{F}_{1291}$
+%\vspace{-10pt}
+\begin{center}
+\begin{tabular}{|>{$}r<{$}|>{$}r<{$}>{$}r<{$}|>{$}r<{$}|>{$}r<{$}>{$}r<{$}|}
+\hline
+k& a_k& b_k&q_k&  c_k& d_k\\
+\hline
+ &    &    &   &    1&   0\\
+0&  47&1291&  0&    0&   1\\
+1&1291&  47& 27&    1&   0\\
+2&  47&  22&  2&  -27&   1\\
+3&  22&   3&  7&   55&  -2\\
+4&   3&   1&  3&{\color{red}-412}&{\color{red}15}\\
+5&   1&   0&   & 1291& -47\\
+\hline
+\end{tabular}
+\end{center}
+\[
+{\color{red}-412}\cdot 47 +{\color{red}15}\cdot 1291 = 1
+\;\Rightarrow\;
+47^{-1}={\color{red}879}
+\]
+\end{block}
+\end{column}
+\end{columns}
+\end{frame}
-- 
cgit v1.2.1