\documentclass[a4paper, 10pt]{article}
\usepackage[estonian]{babel}
\usepackage[utf8]{inputenc}
\usepackage{t1enc}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{amssymb}

\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 2022} \smallskip %
\vspace{2em}



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

\end{center}

\bigskip\bigskip

\large

\bigskip

\noindent 1. Uurida Fermat' testi abil, kas $115901$, $115911$, $115921$ ja $115931$ on alg- või kordarvud.

\bigskip

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

\bigskip

\noindent 3. Kasutades loengukonspekti näites 9.8 toodud skeemi ja avalikku võtit $(6887,3439)$, \mbox{tuvastada} digiallkirja õigsus tekstil {\normalsize $5381 1838 5904 6333 0754$}, mille originaal on \mbox{ PRESIDENT}. 

\bigskip

\noindent 4. Kasutades loengukonspekti näites 9.8 toodud skeemi 16-täheliste (st. 32-numbriliste) blokkide jaoks ja mooduli väiksust, dekodeerida avaliku võtmega \linebreak $(47680685109997991128832650923197,666666667)$ kodeeritud RSA sõnum {\small $$330193354303598810258081764967602000527180985951324043176516093200500476527460859657338782260996.$$}

\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}$, seejuures $n=96312883$. Salajase võtme $v$ leiate Diffie-Hellmani võtmevahetuse abil, valides rühmaks $\Z_{97165291}$ ja algjuureks arvu 2. Te olete saanud ühissaladuse leidmiseks sõnumi $42655264$ ja otsustate võtta oma astendajaks arvu $3003$. Dekodeerida salasõnum {\normalsize $$77447652 64437359 60547750 70647050 78436846 77506241 70587161 77586953 79587256 74587253.$$}

\noindent 6. Olgu $n$ kordarv, mis {\bf ei} läbi Milleri-Rabini testi alusel $1<a<n$. Leida vähemalt üks arvu $n$ tegur, mis ei ole 1 ega $n$ ise.

\bigskip

\noindent 7. Tõestada \emph{Korselti kriteerium}: {\bf kord}arv $n$ on Carmichaeli arv parajasti siis, kui ta on ruuduvaba ja iga $p\in\P$, $p\mid n$, korral kehtib $(p-1)\mid(n-1)$. Carmichaeli arvude ruuduvabadust võib eeldada ilma seda tõestamata. Ruuduvabaduse tõestamisel tahvlile vabatahtlikkuse alusel: +1 punkt.

\bigskip

\noindent 8. Arvutuslikel põhjustel on RSA avaliku võtmena $e$ populaarsed Fermat' algarvud. Miks ei ole hea mõte võtta $e$ väärtuseks alla $F_4 = 65537$? 

\bigskip

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

\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}