\documentclass{article}
\usepackage{a4wide}
\usepackage[utf8x]{inputenc}
\usepackage[english]{babel}
%\usepackage{graphicx}
%\usepackage{clrscode}
\usepackage{fancyhdr}
\pagestyle{fancy}
\newcounter{priklad}
\newcommand{\pr}{\newpage\noindent\stepcounter{priklad}}
\headheight 23.2pt
\fancyfoot{}
\lhead{Jiří Slabý, 98734}
\chead{\textbf{Error-correcting codes, cryptography and \\ cryptographical
protocols (IV054)}}
\rhead{Exercise 1.\arabic{priklad}}
\renewcommand{\baselinestretch}{1.17}
\renewcommand{\labelenumi}{(\alph{enumi})}
\begin{document}
\pr % 1. priklad
\begin{enumerate}
\item $A_q(n,d)\,???\,A_q(\frac{n}{2},\frac{d}{2})$. If we consider
division as integral operator (i. e. 3/2 = 1), we can't choose
neither $\leq, =$ nor $\geq$. Let's say, that we can, then: \\
If we get $A_2(4,3)$ and $A_2(2,1)$,
the first result is 2 (e. g. 0000, 0111), the second equals to 4 (00,
01, 10, 11). So the relation is $\leq$. \\
But when we get $A_2(4,2)=8$ and $A_2(2,1)=4$, the relation is $\geq$.
In that case, the relation should be $=$, but (for example) $A_2(4,2)
\neq A_2(2,1)$ and it's odd. This is an argument against ``that we
can''. \\
On the other hand, if we consider only even numbers, the relation is
$\geq$. The worst case is $A_2(2,2)$ and $A_2(1,1)$, which equals. Next,
when we get any higher numbers, we get $>$ relation that is clear to
prove.
\item $A_q(n,d) \leq A_q(n+2,d+1)$. If $d$ is odd, then
$A_q(n,d)=A_q(n+1,d+1)$ and $A_q(n+2,d+1)=A_q(n+1,d)$. Hence $A_q(n,d)
\leq A_q(n+2,d+1)$ in this case. If $d$ is even, it's not easy to prove,
I don't know.
\item $A_q(2n,2d+1) \leq A_q(n,d)$. Proof unknown )-:
\item $A_q(n,d) \leq A_{2q}(n,d)$. If $C$ is some $A_q(n,d)$ code, let $C'$
be $A_{2q}(n,d)$. It is clear, that without constraints, $C'$ does have
much more words. But if the (same) constraint applied on both, it is
clear, that $C'$ does have more words, so $A_q(n,d) \leq A_{2q}(n,d)$.
\item $A_q(n,d) \leq q^{(n-d+1)}$ (Singleton bound)
\end{enumerate}
\pr % 2. priklad
\begin{enumerate}
\item $A_2(5,3)=4$ (proof in scripts, page 24) \\
$4\leq A_3(5,3)\leq22$ \\
$9\leq A_4(5,3)\leq64$ (bounds are Gilbert-Varshamov's and Hamming's)
\item $A_2(3,1)=2^3=8$ (Theorem (a), page 32) \\
$A_2(4,2)=A_2(3,1)=2^3=8$ (Corollary, page 26 and Theorem (a), page 32)
\item $A_2(10,1)=2^{10}=1024$ (Theorem (a))\\
$A_2(10,2)=A_2(9,1)=2^9=512$ (Corollary, Theorem)
\item $A_2(11,10)=2$ -- because of Lemma, page 22, we can assume, that one
word is 00 000 000 000 (without spaces). In that case, next acceptable
word has to be with 10 ›1‹, e. g. 00 111 111 111, some permutation is
allowed by equivalency definition on page 22. But that
means, that no other word is allowed, because, there is no other word,
which could be different in 10 symbols from both words. \\
$A_2(12,10)=2$ -- arguments are similar. There is one word with all
zeroed symbols. Next, there is word with 10 ones. Finally, there is no
other way to create another word, so the result is 2.
\end{enumerate}
\pr \indent % 3. priklad
Skrinka s demonem. And now, how I found that out. Because in the text was
written, that the data could appear somewhere on the disk, I used
\texttt{file(1)} UN*X
utility. (Indeed, after I cut \& pasted the source text to the stdin of a perl
script, which converts hexa numbers to standard characters). And it wrote:
\begin{verbatim}
$ tr '\n' ' '|perl -e'$/=" ";while(<>){printf q(%c),hex;}'|file -
50 4b 03 04 14 00 01 00 00 00 c6 b0 32 33 c3 e4
c4 30 1d 00 00 00 11 00 00 00 0d 00 00 00 34 6e
75 6d 61 6c 70 68 61 2e 74 78 74 0f 2b f9 68 0c
42 d2 c3 76 f2 c1 a3 55 eb 9f 23 d6 da a0 3d 65
be 95 79 cc 0d 6a 33 8b 50 4b 01 02 14 00 14 00
01 00 00 00 c6 b0 32 33 c3 e4 c4 30 1d 00 00 00
11 00 00 00 0d 00 00 00 00 00 00 00 01 00 20 00
00 00 00 00 00 00 34 6e 75 6d 61 6c 70 68 61 2e
74 78 74 50 4b 05 06 00 00 00 00 01 00 01 00 3b
00 00 00 48 00 00 00 00 00
/dev/stdin: Zip archive data, at least v2.0 to extract
\end{verbatim}
So now, we know where the data comes from -- some kind of zip utility. So
let's try to unzip it (it isn't native UN*X utility, so it can't read from
stdin, it doesn't matter, we'll redirect it to some tempfile and will read it
later):
\begin{verbatim}
$ tr '\n' ' '|perl -e'$/=" ";while(<>){printf q(%c),hex;}' >/tmp/my.zip; \
unzip /tmp/my.zip
50 4b 03 ... 00 00 00
Archive: /tmp/my.zip
4numalpha.txt: ucsize 17 <> csize 29 for STORED entry
continuing with "compressed" size value
[/tmp/my.zip] 4numalpha.txt password:
\end{verbatim}
Oops, passphrase needed. Hm, what about ›crypto‹, ›iv054‹ or ›4numalpha‹.
Nothing. Wait, wait, wait, 4numalpha? Do they mean 4 numeric-alphabetic
chars? But
some cracker is needed. So I'll try that, which I have been using for a
long time in windows. AZPR. After some time, I got it. It was ›g8q3‹.
So the one-liner, which should give you the result is:
\begin{verbatim}
tr '\n' ' '|perl -e'$/=" ";while(<>){printf q(%c),hex;}' >/tmp/my.zip; \
unzip -c /tmp/my.zip
\end{verbatim}
\pr \indent % 4. priklad
If no, only 1, 2 or 3 symbols are damaged, we can repair the word,
because we know, that 0 can't become 1 and vice versa. So, if we have at
least one transferred symbol not being *, we know, that the word was full of
that symbol. The only case, when the reparation machine could be confused is
when all 4 symbols would be damaged by the transfer. \\ \indent
In that case the probability is: \\
$P=p^4{4\choose4}=p^4$ (probability of all symbols being damaged is $p^4$)
\\ \indent
If we consider, that $p<1$, than $p^4$ is very small number, since the
probability of all symbols in the word being damaged is very small.
\pr \indent % 5. priklad
We can write \\
$\sum_{i=1}^{10}(11-i)x_i=$ \\
/* $(11-1)x_1+(11-2)x_2+\ldots+(11-10)x_{10}=$ \\
$(11x_1-1x_1)+(11x_2-2x_2)+\ldots+(11x_{10}-1x_{10})=$ \\
$11(x_1+x_2+\ldots+x_{10})-(1x_1+2x_2+\ldots+10x_{10})=$ */ This wasn't
really needed to write, but\ldots \\
$11\sum_{i=1}^{10}x_i-\sum_{i=1}^{10}ix_i$ \\ \indent
Now, the ``$ix_i\Rightarrow(11-i)x_i$ way'' is clear, because the first sum
in subtraction is $0\,(mod\ 11)$ (because of 11 before it), the second, from
assumption, is $0\,(mod\ 11)$ too. If we consider, that subtraction of two
numbers, which are dividable by 11 is dividable by 11 too. So the one
way of equivalency is done. \\ \indent
The ``$(11-i)x_i\Rightarrow ix_i$ way'': if we know, that the sum on the
first line is dividable by 11 and get the two sums in the end of equality,
we can assume, that the $\sum_{i=1}^{10}ix_i$ is dividable by 11, because
the first sum in subtraction is $0\,(mod\ 11)$ always and the second is
$11k$ (where $k$ is integral number) to satisfy
$\sum_{i=1}^{10}(11-i)x_i=0\,(mod\ 11)$. But that's it, the sum is also
dividable by 11 and it is that, what we need to prove. \\ \indent
Since both ways are true, equivalency is also true.
\pr \indent % 6. priklad
For a long time I didn't know where is this code from. 77 symbols, it isn't
product of 2 -- not computer code. Then I tried to make some groups of
symbols. Because the number 77 is dividable only by 7, groups seem like:
\begin{verbatim}
0011000 or 00110000011
0011000 00011111111
1111111 01100100110
1011001 01001100101
0011001 11100010010
0011001 00100100010
0111100 01001100110
0100100
0100100
0100100
1100110
\end{verbatim}
In the first case, there seems to be something, I tried to change 0 into \_ to
distinguish the symbols better:
\begin{verbatim}
__11___
__11___
1111111
1_11__1
__11__1
__11__1
_1111__
_1__1__
_1__1__
_1__1__
11__11_
\end{verbatim}
Now I see, that there is a man with one arm twice shorter than the other. So
try to delete \_ form the picture and replace 1 by X for better result:
\begin{verbatim}
$ tr -d '\n'|sed -e 's/0/ /g' -e 's/1/X/g' -re 's/.{7}/&\n/g'
0011000001100011111111011001001100100110010111100
0100100010010001001001100110
XX
XX
XXXXXXX
X XX X
XX X
XX X
XXXX
X X
X X
X X
XX XX
\end{verbatim}
\end{document}