\documentclass[12pt]{amsart} 
\usepackage[dvips]{graphics, color}
\theoremstyle{plain}

\newtheorem{theorem}{Theorem}[section]
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}

\theoremstyle{lemma}
\newtheorem{lemma}[theorem]{Lemma}
\theoremstyle{exempel}
\newtheorem{exempel}[theorem]{Exempel}
\theoremstyle{corollary}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{proposition}
\newtheorem{proposition}[theorem]{{Proposition}}
\theoremstyle{clam}
\newtheorem{clam}[theorem]{Claim}
\theoremstyle{conjecture}
\newtheorem{con}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{re}[theorem]{{Remark}}
\newtheorem{no}[theorem]{Notation}



\newtheorem{quest}[theorem]{Question}

\newtheorem{problem}[theorem]{Problem}





\newtheorem{worning}[theorem]{{\rm W\sc orning}}

\newtheorem{para}[theorem]{}

\newtheorem{examp}[theorem]{Example}

\newtheorem{exercise}[theorem]{Exercise}

\newcommand\pn[1]{{\mathbb P}^{#1}}
\newcommand\cal[1]{\mathcal {#1}}
\newcommand\cL{\mathcal L}
\newcommand\cZ{\mathcal Z}
\newcommand\cO[1]{\cal{O}_{\cal{{#1}}}}
\newcommand\X[1]{X^{[{#1}]}}
\newcommand\zed{{\mathbb Z}}
\newcommand\nat{{\mathbb N}}
\newcommand\rat{{\mathbb Q}}
\newcommand\real{{\mathbb R}}
%\newcommand\a{{\aa}}
\textwidth16cm
\textheight20cm
\oddsidemargin-0.3cm
\evensidemargin0.4cm
%\pagestyle{plain} 
\newtheorem{Definition}{\sf Definition}
\begin{document}
{\sf KTH Matematik}
\begin{center} 
 {\bf 5B1118 Diskret Matematik \\
Kontrollskrivning 5 \\
Tisdagen den 18 May, 2004 \\}
\end{center}

\vspace{.3in}

\begin{itemize}
\item {\it Skrivtid:}{\bf 09:15-10:15.}
\item {\it Till{\aa}tna hj\"alpmedel: Minir\"aknare med sifferdisplay.}
\item {\it Motivering kr\"avs!}
\item {\it F\"or godk\"ant resultat kr\"avs minst 5 po\"ang.}
\end{itemize}

\vspace{.1in}

\noindent\framebox[15cm]{Personnummer:\hspace{12cm}}\\
\framebox[15cm]{Namn:\hspace{12cm}}\\

\vspace{.1in}

\begin{enumerate}
\item (3p) Betrakta den linjära koden med checkmatris:
\[ M=\left[ \begin{array}{ccccc}
1&0&0&1&1\\
0&1&0&1&1\\
0&0&1&0&1
\end{array} \right]\]
\begin{enumerate}
\item Skriv alla ord i koden.

Ska l\"osa systemet:
\[ \begin{array}{ccccccc}
x_1&+&x_4&+&x_5&=&0\\
x_2&+&x_4&+&x_5&=&0\\
&&&&x_3&=&0
\end{array} \]
Orden \"ar $\{00000,11101,11010,00111\}$.
\item Hur m\aa nga fell kan koden r\"atta?
$\delta(C)=3$ d{\aa} kan koden r\"atta ett fel.
\item R\"atta det felaktiga ordet 11001, om ett fel skedde.
L\aa t $x=11001$. Multiplicationen $Mx$ ger  kolumnen [001].
Ordet r\"attas som $11101$.
\end{enumerate}


\vspace{.2in}

\item(3p) Skriv checkmatrisen av en kod av l\"angd $7$ som r\"attar precis ett fel. 

$ 7=2^3-1$, s{\aa} kan man skriva en Hamming kod med $r=3$. Matrisen $M$ har $3$ rader och $7$ kolumner, som best\aa r av alla ickenoll sekvenser av $3$ element i $\zed_2$:
\[ M=\left[ \begin{array}{ccccccc}
1&0&0&1&1&0&1\\
0&1&0&1&0&1&1\\
0&0&1&0&1&1&1
\end{array} \right]\]
\vspace{.2in}

\item(3p) Kryptera meddelandet $4$ i ett RSA-system med krypteringsnyckel $n=91$, $e=47$.


Meddelandet $4$ krypteras som $4^{47}$ mod $91$.


$$47=2^5+2^3+2^2+2+1\,\,\, 4^{47}=4^{32}\cdot 4^{8}\cdot 4^4\cdot 4^2\cdot 4$$
Man r\"aknar att
$$4^4=256\equiv_{91}74\,\,4^8=5476=91\cdot 60+16 \equiv_{91} 16\,\,,4^{16}=16\cdot 16\equiv_{91} 74 
\,\, 4^{32}\equiv_{91} 16 $$
$$ 4^{47}=\equiv_{91} 16\cdot 16\cdot \cdot 74 \cdot 16\cdot 44\equiv_{91} 23$$
\end{enumerate}

\vspace{.3in}



\end{document}