blob: 846738f02d47c29a900eec88c5605d06d0c8cb4c (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
%
% 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*}
\uncover<2->{&& a{\color{blue}b} &\equiv 1 \mod p}
\\
\uncover<3->{&\Leftrightarrow& a{\color{blue}b}&=1 + {\color{blue}n}p}
\\
\uncover<4->{&&a{\color{blue}b}-{\color{blue}n}p&=1}
\end{align*}
\uncover<5->{Wegen
$\operatorname{ggT}(a,p)=1$ gibt es
$s$ und $t$ mit
\[
{\color{red}s}a+{\color{red}t}p=1
\Rightarrow
{\color{blue}b}={\color{red}s},\;
{\color{blue}n}=-{\color{red}t}
\]}
\uncover<6->{%
$\Rightarrow$ Die Inverse kann mit dem euklidischen Algorithmus
berechnet werden}
\end{block}
\end{column}
\begin{column}{0.48\textwidth}
\uncover<7->{%
\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&\uncover<8->{ 0}& 0& 1\\
1&\uncover<9->{ 1291& 47}&\uncover<11->{ 27}&\uncover<10->{ 1& 0}\\
2&\uncover<12->{ 47& 22}&\uncover<14->{ 2}&\uncover<13->{ -27& 1}\\
3&\uncover<15->{ 22& 3}&\uncover<17->{ 7}&\uncover<16->{ 55& -2}\\
4&\uncover<18->{ 3& 1}&\uncover<20->{ 3}&\uncover<19->{{\color{red}-412}&{\color{red}15}}\\
5&\uncover<21->{ 1& 0}& &\uncover<22->{ 1291& -47}\\
\hline
\end{tabular}
\end{center}
\uncover<23->{%
\[
{\color{red}-412}\cdot 47 +{\color{red}15}\cdot 1291 = 1
\uncover<24->{\;\Rightarrow\;
47^{-1}={\color{red}879}}
\]}
\end{block}}
\end{column}
\end{columns}
\end{frame}
|
