\documentclass[12pt,a4paper]{article}
\usepackage{enumitem}
\usepackage[czech]{babel}
\usepackage[utf8]{inputenc}

\textwidth=170mm
\hoffset=-14mm
\voffset=-20mm
%\textwidth=170mm
%\hoffset=-14mm

%\hoffset -24mm
%\voffset -20mm
%\textwidth 170mm
%\textheight 230mm

\usepackage[all]{xy}
\usepackage{amsfonts}

%\usepackage{czech}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{xcolor}

\newcommand{\mezera}{}%\vskip .3cm}
\newcommand{\hvezda}{${}^\ast$}%\
\def\vect #1{{\overrightarrow{#1}}}
\DeclareMathOperator{\tg}{tg}

\newcounter{prik}%[section]
\renewcommand{\theprik}{\arabic{prik}}
\newcommand{\priklad}[1]{\refstepcounter{prik} 
                         \paragraph*{Příklad \theprik:} #1}
\newcommand{\prikladhvezda}[1]{\refstepcounter{prik} 
                         \paragraph*{Příklad \theprik${}^\ast$:} #1}

                         \newcommand{\matice}[4]{\begin{pmatrix} #1 & #2 \\ #3 & #4\end{pmatrix} }

\newcommand{\cviceni}[2]{{\section{#1}} Cvičení konané #2 2021. \\ \vskip 0.2cm}   
%\newcommand{\cvicenii}[2]{{\section{#1}} Cvičení konané #2 2021. \\ \vskip 0.2cm}   

\def\N{\mathbb N}
\def\Z{\mathbb Z}
\def\Q{\mathbb Q}
\def\R{\mathbb R} 
\def\C{\mathbb C}      
             
\newcommand{\ondra}[1]{{\color{red} #1}}   
\newcommand{\josef}[1]{{\color{blue} #1}}   
          

                         
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%  PREPINANI VERZI %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\rezervnipriklad}[1]{\refstepcounter{prik} 
                         \paragraph*{Příklad \theprik:} #1}

%\newcommand{\rezervnipriklad}[1]{}

% Priprava
\newcommand{\vysledekbez}[1]{[{\it Řešení: #1}]}
\newcommand{\vysledek}[1]{\\ \noindent [{\it Řešení: #1}]}
\newcommand{\napoveda}[1]{{\it Nápověda: #1}}
\newcommand{\poznamka}[1]{{\it Poznámka: #1}}

% Zadani 
%\newcommand{\vysledekbez}[1]{}\newcommand{\vysledek}[1]{}\newcommand{\napoveda}[1]{{\it Nápověda: #1}}\newcommand{\poznamka}[1]{{\it Poznámka: #1}}

% Reseni
%\newcommand{\vysledekbez}[1]{[Řešení: #1}\newcommand{\vysledek}[1]{[Řešení: #1]}\newcommand{\napoveda}[1]{}\newcommand{\poznamka}[1]{}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\hlavicka}{
\newpage
\begin{center}
{\large MIN401 Matematika IV - jaro 2022}
\end{center} 
}

\begin{document}
\pagestyle{empty}

%\hlavicka



\centerline{\bf 4. cvičení z MIN401 -- soustavy kongruencí, }  

\priklad{Vyřešte následující kongruence:
\begin{enumerate}[label=(\roman*)]
\item $210x \equiv 40 \ (\!\!\!\!\mod 212)$.
\item  $325x\equiv 694\ (\!\!\!\mod 471)$.
\end{enumerate}
}


\priklad{Vyřešte následující soustavy kongruenci:
\begin{enumerate}[label=(\roman*)]
\item $2x \equiv 3 \pmod {7}$, \  $x \equiv 8 \pmod {15}$.
\item $x \equiv 3 \pmod{10}$, \ $x \equiv 8 \pmod{15}$, \ $x \equiv 5 \mod{84}$.
\item $21x\equiv 27 \pmod{24}$, \ $26x\equiv  10 \pmod{25}$, \ $27x\equiv 30 \pmod{17}$.
\end{enumerate}
}


\priklad{
Najděte inverzní prvek k číslu  $157$ modulo $2475$.
 }

\priklad{[10.32, 10.33] Najděte primitivní kořeny modulo $8$, $11$, $20$, $26$, $41$ a $41^2$}.

\priklad{ 
Šifrou RSA s veřejným klíčem $n=95$ a $e=55$ bylo posláno číslo $Z=42$. Šifru prolomte a určete zaslanou zprávu $M\in\{1,2,\dots,94\}$.
}

\priklad{Veřejný klíč Honzy pro RSA šifru je $(91,23)$. Zachytili jste jemu určenou zprávu $3$. Dekódujte ji.}

\priklad{ 
V šifrovacím systému RSA s veřejným klíčem skládajícím se z modulu $n=2021$ a exponentu $e=11$ došlo k prozrazení faktorizace $n = p \cdot q=43\cdot 47$. S její pomocí dešifrujte zprávu $c = 21$. Při výpočtu mocniny $c^d \mod{2021}$ počítejte zvlášť modulo $43$ a modulo $47$ a tyto mezivýsledky pak dejte dohromady.
}
\vysledek{ $d=527$, $c^d\equiv 11 \mod 43$, $c^d\equiv 34 \mod 47$, zpráva je $269$.
}

\priklad{
V ElGamalově šifrovacím systému si Alice zvolila veřejný klíč sestávající z~prvočísla $p = 41$, primitivního kořene $g=11$ a jeho mocniny $g^a$ (kde exponent $a = 10$ je soukromý). Bob  poslal Alici  svůj veřejný klíč $g^b=22$ a zašifrovanou zprávu $c=6$. Pomozte Alici zprávu dešifrovat?
}
\vysledek{ $g^{ab}\equiv 22^a=22^{10}\equiv 32 \mod 41$. Inverze k $32$ $\mod 41$ je $d\equiv 9$. Zpráva je $m=6\cdot 9\equiv 13 \mod 41$.
}

\priklad{
V ElGamalově šifrovacím systému si Alice zvolila veřejný klíč sestávající z~prvočísla $p = 997$, primitivního kořene $g=11$ a jeho mocniny $g^x$ (kde exponent $x = 23$ je soukromý). Bob si pro komunikaci s Alicí zvolil soukromý klíč $y = 25$ a poslal jí svůj veřejný klíč $g^y$. Pomocí společného soukromého klíče $g^{xy}$ pak zašifroval zprávu $m$ a výslednou zprávu $c=20$ poslal Alici. Jak ji bude Alice dešifrovat?
}
\vysledek{ Při počítání $\mod 997$ je $g^x\equiv 11^{23}\equiv 659$, $g^y\equiv 11^{25}\equiv 976$, $g^{xy}\equiv (g^y)^x\equiv 976^{23}\equiv 950$, inverze k němu je $-297$, $m\equiv c\cdot (-297)\equiv 42$.
}



\end{document}

