\documentstyle[11pt,fullpage]{article} \catcode`\"=13 \def"#1{\v #1}
\setlength{\topmargin}{-1.5cm}            % \topskip=15truept
\setlength{\oddsidemargin}{-0.5cm}        % \hoffset=15truept
\setlength{\evensidemargin}{-0.5cm}
\setlength{\textheight}{24cm}          % \vsize=217truemm
\setlength{\textwidth}{17cm}           % \hsize=148truemm
\hfuzz=10pt
\def\mmod{{\rm mod\ }}
\def\Z{{\rm Z\!\! Z}}

\begin{document} \pagestyle{empty}

\centerline {{\bf Kriptografija in teorija kodiranja -- 4. doma"ca naloga}
                  (do petka 19. december, 2003)}

\vspace{.1in}
\hrule%--------------------------------------------------------------

% \centerline
% {\small\bf Odgovori in re"sitve naj bodo jasne, pregledne in 
           % utemeljene z ra"cunom ali besedo!}

\hrule%--------------------------------------------------------------

\vspace{.25in}
\begin{enumerate}
\item[1.] Naj bodo $a$, $b$ in $n$ naravna "stevila za katere velja
          $b \le a \le n$.
          Spomnimo se, da pri Evklidovem algoritmu za ra"cunanje 
	  najve"cjega skupnega delitelja $D(a,b)$ "stevil $a$ in $b$
	  najprej delimo $a$ z $b$. "Ce je ostanek enak $0$, potem je 
	  $D(a,b)=b$, sicer pa delimo zadnji delitelj z zadnjim ostankom
	  in to ponavljamo vse dokler ne pridemo do ostanka $0$. 
	  Potem je zadnji od ni"c razli"cen ostanek najve"cji skupni 
	  delitelj "stevil $a$ in $b$.
	  Ta proces lahko predstavimo z naslednjimi ena"cbami
          \begin{eqnarray*}
	  a       &=& q_1 b   + r_1, \ \ \ 0 <  r_1 <  b,   \\
	  b       &=& q_2 r_1 + r_2, \ \ \ 0 <  r_2 <  r_1, \\
	  r_1     &=& q_3 r_2 + r_3, \ \ \ 0 <  r_3 <  r_2, \\
	          &\vdots&                                   \\
	  r_{k-3} &=& q_{k-1} r_{k-2} + r_{k-1}, 
	  \ \ \ 0 <  r_{k-1} <  r_{k-2}, \\
	  r_{k-2} &=& q_{k}   r_{k-1} + r_{k}, 
	  \ \ \ 0 <  r_{k}   <  r_{k-1}, \\
	  r_{k-1} &=& q_{k+1} r_{k} + 0,  \\
	  \end{eqnarray*}
	  %
	  in je $D(a,b)=r_k$.
          \begin{description}
          \item{(a)} Doka"zi, da je  $r_{i+2} < {1\over 2} r_i$
	             za vsak $1 \le i \le k-2$.
          \item{(b)} Iz (a) izpelji, da je 
	             "casovna zahtevnost Evklidovega algoritma 
		     ${\cal O}((\log_2 n)^3)$ bitnih operacij.
          \end{description}

\bigskip % \bigskip
\item[2.] \begin{description}

          \item{(a)} Za "stevilo $a$ in zaporedje $q_1,\dots,q_{k+1}$
          iz 1. naloge doka"zi, da velja $\Pi^{k+1}_{i=1}\, q_i \le a$.

          \item{(b)} Naj bosta $a$ in $b$ naravni "stevili in $a\ge b$.
	             Doka"zi, da je "casovna zahtevnost obi"cajnega
		     deljenja velikih "stevil pri katerem ra"cunamo
		     "stevili $q$ (kvocijent) in $r$ (ostanek) za kateri
		     velja
		     $$
		     a = qb + r, \ \ \ 0 \le r < b,
		     $$
		     ${\cal O}((\log_2 b)(\log_2 q)$ bitnih operacij.

          \item{(c)} Doka"zi, da je "casovna zahtevnost Evklidovega
	             algoritma ${\cal O}((\log_2 n)^2)$ bitnih operacij
	             (to je seveda bolj"sa ocena kot v 1. nalogi). 
          \end{description}

\bigskip % \bigskip
\item[3.] Spomnimo se naslednjih lastnosti Legendrovega simbola.
          "Ce sta $p$ in $q$ lihi pra"stevili, potem je 
	  \begin{description}
          \item{(a)} $\Bigl({-1 \over p}\Bigr) = (-1)^{(p-1)/2}$
          \item{(b)} $\Bigl({2 \over p}\Bigr) = (-1)^{(p^2-1)/8}$
          \item{(c)} $\Bigl({p \over q}\Bigr) = 
	              \Bigl({q \over p}\Bigr) (-1)^{(p-1)(q-1)/4}$
          \end{description}
	  Naj bo $n \ge 3$ liho naravno "stevilo.
	  \begin{description}
          \item{(a)} Poka"zi, da za lihi naravni "stevili $n_1$ in 
	  $n_2$ velja
	  $$
	  {n_1n_2-1 \over 2} \equiv 
	  {n_1-1 \over 2} + {n_2-1 \over 2}\ (\mmod 2).
	  $$
	  Od tod izpelji 
          $\Bigl({-1 \over n}\Bigr) = (-1)^{(n-1)/2}$.

          \item{(b)} Poka"zi, da za lihi naravni "stevili $n_1$ in 
	  $n_2$ velja
	  $$
	  {n_1^2n_2^2-1 \over 8} \equiv 
	  {n_1^2-1 \over 8} + {n_2^2-1 \over 8}\ (\mmod 2).
	  $$
	  Od tod izpelji 
          $\Bigl({2 \over n}\Bigr) = (-1)^{(n^2-1)/8}$.
	  
          \item{(c)} Poka"zi, da za liho naravno "stevilo $a\ge 3$,
	  velja 
          $\Bigl({a \over n}\Bigr) \Bigl({n \over a}\Bigr) = 
	  (-1)^{(a-1)(n-1)/4}$.
          \end{description}

\bigskip % \bigskip
\item[4.] Doka"zi, da imamo pri poljubnem RSA sistemu vsaj 9 "cistopisov
          za katere je $E_k(M)=M$.

\bigskip % \bigskip
\item[5.] \begin{description}
          \item{(a)} S pomo"cjo lastnosti Jacobijevih simbolov 
	             izra"cunaj $\Bigl({43691 \over 65537}\Bigr)$.
          \item{(b)} Naj bo \\
\centerline{
$ \!\!\!
\!\!\!\!\!\!\!\!
\!\!\!\!\!\!\!\!
\!\!\!\!\!\!\!\!n=${\tiny % scriptsize
65706677346410716693277290133297748787629461731187083886926467723500222615379581578876215678872009742417817845623}.}
\\
%624142660586694101446291308147581805825611279851037995772020202145871$.
Preveri ali $n$ je ali ni pra"stevilo (lahko uporabi"s MAPLE/MATEMATICA).
Doka"zi svoj odgovor in opi"si kako bi lahko jaz (zlahka) preveril
tvoj dokaz. Kopijo "stevila $n$ boste na"sli na doma"ci strani. 
          \end{description}

\bigskip % \bigskip
\item[6.] \begin{description}
          \item{(a)} Naj bo $p$ liho pra"stevilo in $n$ naravno 
	             "stevilo. Doka"zi, da je "stevilo re"sitev ena"cbe
		     $$
		     x^a \equiv 1 \ (\mmod p)
		     $$
		     v $\Z_p$ enako $D(a,p-1).$
          \item{(b)} Naj bosta $p$, $q$ lihi pra"stevili in $n=pq$.
	             Naj bo $f(x)$ polinom s celo"stevil"cnimi 
		     koeficienti. 
		     Naj bo $S_n$ (zaporedoma $S_p$ in $S_q$)
		     mno"zica re"sitev iz $\Z_n$ 
		     (zaporedoma $\Z_p$, $\Z_q$) ena"cbe 
		     $f(x) \equiv 0 \ (\mmod n)$ 
		     (zaporedoma $(\mmod p)$, $(\mmod q)$). \\
		     Doka"zi $|S_n|\, = \, |S_p|^.|S_q|$.
	             
          \item{(c)} Naj bo $n=pq$ produkt dveh lihih razli"cnih 
	             pra"stevili in $n=pq$ in naj bo $1 \le a \le n-1$.
		     "Ce je $a^{n-1} \equiv\!\!\!\!\! /\ 1\ (\mmod n)$, 
		     potem imenujemo $a$ {\bf Fermatova pri"ca} za $n$,
		     sicer pa mu pravimo {\bf Fermatov la"znjivec} za 
		     $n$.
		    Poi"s"ci formulo za "stevilo Fermatovih la"znjivcev
		    za $n$.
          \end{description}

% \bigskip % \bigskip
% \item[7.] 

\end{enumerate}

% \vfill
\end{document}

1452576797467245679578072652478346947812236457568758356737347637*4523456347435
7261361571761612345123451345161657979

