\documentclass[a4paper, 10pt]{article}
\usepackage[estonian]{babel}
\usepackage[utf8]{inputenc}
\usepackage{t1enc}
\usepackage{srcltx}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{amscd}
\usepackage{amssymb}
\usepackage{amscd}
\usepackage{lscape}
\usepackage{array}
\newtheorem{defi}{Definitsioon}[section]
\newtheorem{lemma}[defi]{Lemma}
\newtheorem{lause}[defi]{Lause}
\newtheorem{teoreem}[defi]{Teoreem}
\newtheorem{jareldus}[defi]{J\"areldus}

\def\b#1{\textsl{\textbf{#1}}}
\def\c{\cdots}
\def\l{\ldots{}}
\def\q{\hfill\square}
\def\toe{\textsc{T\~oestus.}$\;$}
\def\t{\textsc{Tarvilikkus.}$\;$}
\def\p{\textsc{Piisavus.}$\;$}
\def\inb#1{\in\mathbf{#1}}
\def\Xa{X_{\alpha}}
\def\xa{x_{\alpha}}
\def\ha{h_{\alpha}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\ind}{\mathrm{ind}}
\renewcommand{\P}{\mathbb{P}}

\topmargin-4em
\oddsidemargin0cm
\textwidth16cm
\textheight27cm
\evensidemargin-2cm

\begin{document}

\pagestyle{empty}

\Large

{\hfill{Kevad 2020} \smallskip %
\vspace{2em}



\begin{center}
{\LARGE Arvuteooria 15. praktikumi ülesanded:\\ 
\vspace{1em}
{\LARGE Krüptograafia.}
}

\end{center}

\bigskip\bigskip


\bigskip

\noindent 1. Uurida Fermat' testi abil, kas $15841$, $15871$ ja $15881$ on alg- või kordarvud.

\bigskip

\noindent 2. Kontrollida eelmise ülesande tulemust Miller-Rabini testi abil. 

\bigskip

\noindent 3. Kasutades loengukonspekti näites 9.8 toodud skeemi ja avalikku võtit $(9523,13)$, tuvastada digiallkirja õigsus tekstil $1400 5247 5486 8259$, mille originaal on SALATÕBI. 

\bigskip

\noindent 4. Kasutades loengukonspekti näites 9.8 toodud skeemi neljatäheliste (st. kaheksa\-numbriliste) blokkide jaoks ja mooduli väiksust, dekodeerida avaliku võtmega $(93122201,91)$ kodeeritud RSA sõnum $$61234207 84879029 01383160 43954689 90016412 42724757 89574723.$$ 


\noindent 5. Te olete salakirjade saatmiseks kokku leppinud loengukonspekti näitega 9.8 sarnase, aga sümmeetrilise ning neljatäheliste blokkidega skeemi, kus arvu\-tused $c=s^d\pmod{n}$ ja $s=c^e\pmod{n}$ on asendatud arvutustega $c=s-v\pmod{n}$ ja $s=c+v\pmod{n}$. Salajase võtme $v$ leiate Diffie-Hellmani võtmevahetuse abil, valides rühmaks $\Z_{31111123}$ ja algjuureks arvu 2. Mooduliks võtate $n=31111123$. Te olete saanud ühissaladuse leidmiseks sõnumi $19874654$ ja otsustate võtta oma astendajaks arvu $666$. Dekodeerida salasõnum $21683015 08552292 25694015 25702930 01552497$.

\bigskip

\noindent 6. Olgu $(n,5)$ RSA avalik võti, kus $p,q\in \P$, $p>5$ ja $q=2p-3$. Tõestada, et $p\equiv 3\pmod{5}$ ja $(n,\frac{(p-1)(q-1)+1}{5})$ sobib vastavaks salajaseks võtmeks. 

\bigskip

\noindent 7. Tõestada, et arv 2 ei ole ühegi Fermat' arvu (st arvu kujul $F_n=2^{2^n}+1$) jaoks Fermat' tunnistaja. 

\bigskip

\noindent 8. Tõestada, et 561 on vähim Carmichaeli arv. Tõestuseta võib kasutada fakte, et Carmichaeli arvud on paaritud, ruuduvabad (st nende algtegurid on kõik erinevad) ja et neil on vähemalt kolm algtegurit. 

\bigskip

\noindent 9${^*}$. Öeldakse, et sõnum $s$ on RSA süsteemi \emph{püsipunkt}, kui $m^e\equiv m\pmod{n}$, kus $(n,e)$ on avalik võti. Leida RSA süsteemi püsipunktide arv. 

\bigskip

\noindent 10${^{**}}$. Olgu $p\in\mathbb{P}$ ja $k>1$. Tõestada, et kui leidub polünomiaalne (suuruse $\log p$ suhtes) algoritm diskreetse logaritmi leidmiseks korpuses $\Z_p$, siis leidub ka polünomiaalne (suuruse $\log(p^k)$ suhtes) algoritm diskreetse logaritmi leidmiseks korpuses $\Z_{p^k}$. (Niisugust algoritmi õnneks küll teada ei ole).  

\end{document}