diff options
author | Andreas Müller <andreas.mueller@ost.ch> | 2021-03-02 10:23:02 +0100 |
---|---|---|
committer | Andreas Müller <andreas.mueller@ost.ch> | 2021-03-02 10:23:02 +0100 |
commit | a04efb8ee3eef6ec32b1381801ee244744db1201 (patch) | |
tree | 7d3ac94373d0c4ad7e5fa01b24152742851a2357 /vorlesungen/slides/4/division.tex | |
parent | add slides (diff) | |
download | SeminarMatrizen-a04efb8ee3eef6ec32b1381801ee244744db1201.tar.gz SeminarMatrizen-a04efb8ee3eef6ec32b1381801ee244744db1201.zip |
division in F_p
Diffstat (limited to 'vorlesungen/slides/4/division.tex')
-rw-r--r-- | vorlesungen/slides/4/division.tex | 62 |
1 files changed, 62 insertions, 0 deletions
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} |