\documentclass[a4paper]{article}
\usepackage{t1enc}
\usepackage[utf8]{inputenc}
\usepackage[magyar]{babel}
\frenchspacing
\sloppy
\pagestyle{empty}

\setlength\marginparsep{0cm}
\setlength\oddsidemargin{0cm}
\setlength\evensidemargin{0cm}
\setlength\topmargin{-15mm}
\addtolength\textwidth{5.6cm}
\addtolength\hoffset{-0.9cm}
\addtolength\textheight{5cm}
\setlength\tabcolsep{2pt}
\setlength\arraycolsep{2pt}

\usepackage{amssymb}

\begin{document}

\begin{center}
{\LARGE Bevezetés a számításelméletbe II.}
\\\vspace*{1mm}
13. gyakorlat, 2007. május 9.
\\\vspace*{1mm}
{\footnotesize Koblinger Egmont \texttt{<egmont@cs.bme.hu>}}

\vspace*{12mm}
\textbf{\LARGE Csoportok III. – Titkosírás}
\end{center}

\vspace*{9mm}

\begin{enumerate}
\setcounter{enumi}{130}

\item Mutasd meg, hogy ha egy $G$ csoport azon elemei, melyek önmaguk inverzei, részcsoportot alkotnak, 
akkor ez egyben normálosztó is. Igaz-e mindig, hogy ez a halmaz részcsoport?

\item Határozzuk meg a megadott $G$ csoportok $H$ részcsoportja szerinti bal-
és jobboldali mellékosztályait, majd döntsük el, hogy $H$ normálosztó-e.
Ha igen, határozzuk meg a $G/H$ faktorcsoportot!

\begin{enumerate}
\item[a) ] $G$ a $\{0, 1, \dots, 11\}$ számok csoportja a modulo 12 összeadásra nézve, $H = \{ 0, 4, 8 \}$.
\item[b) ] $G = S_3$ és $H = \{I,(12)\}$.
\item[c) ] $G$ a nemszinguláris mátrixok a mátrixszorzással, $H$ az 1 determinánsú mátrixok.
\item[d) ] $G$ az egész számok az összeadással, $H$ a $2007$-tel oszható egészek.
\item[e) ] $G$ az $\{1, 2, \dots, 10\}$ halmaz összes részhalmazainak halmaza a szimmetrikus differencia műveletével,
$H$ azon részhalmazokból áll, melyek a 9-et és a 10-et nem tartalmazzák.
\item[f) ] $G = D_n$, $H=\{I, t_1\}$.

\end{enumerate}

\item Legyen $G$ véges csoport és $N \lhd G$ normálosztó. 
Mutasd meg, hogy a $G / N$ faktorcsoport $gN$ elemének a rendje a legkisebb olyan $k$ pozitív egész, 
melyre $g^k \in  N$.

\item Legyen $G$ csoport, $H \leq G$ és $N \lhd G$. Bizonyítsd be, hogy $H \cap N$ normálosztója $H$-nak!

\item Aliz és Béla telefonon keresztül sakkoznak. Ha a játszma függőben marad,
az utolsó lépést „borítékolni” kell. Hogyan oldjuk meg ezt?

\item A nyilvános kulcsú titkosírás dekódoló kulcsának működése a következő állításon alapszik:
ha $x$ és $N$ adottak, akkor
$$ x^{k \cdot \varphi(N)+1} \equiv x \qquad (\textrm{mod } N)$$
tejesül minden $k$ pozitív egészre. Ez az állítás könnyen bizonyítható, ha az Euler-Fermat tételből nyert
$x^{\varphi(N)} \equiv 1 (\textrm{mod } N)$ összefüggést a $k$-adik hatványra emeljük,
majd $x$-szel szorozzuk.
Azonban az Euler-Fermat tétel alkalmazásához szükség van arra is, hogy $(x,N)=1$ teljesüljön.
Bizonyítsuk be, hogy ha $N$ két különböző prím szorzata (ez a nyilvános kulcsú titkosításnál fennáll), akkor a fenti állítás teljesüléséhez nem kell, hogy $(x,N)=1$ igaz legyen!

\item Fehérkém 5 titkos információval rendelkezik, amelyek közül az egyiket
szívesen eladná Feketekémnek. Az információkat Fehérkém egy-egy borítékban
tartja, mindre fel van írva, hogy miről szól. Feketekém az egyik borítékot
szívesen megvenné, de fél, hogy másnap Fehérkém már 6 borítékot árulna,
az utolsót azzal a felirattal, hogy „Mi érdekli Feketekémet?”. Ajánljunk
nekik olyan eljárást, mellyel Feketekém hozzájut pontosan egy boríték
tartalmához, de Fehérkém nem tudja, melyikhez!

\end{enumerate}

\end{document}
