A.
1. Wykazać, że zbiór liczb pierwszych jest nieskończony.
2. Znaleźć wszystkie rozwiązania układu kongruencji
\(\displaystyle{ x \ \equiv \ 3 \ mod \ 5}\)
\(\displaystyle{ x \ \equiv \ 5 \ mod \ 6}\)
3. Rozłożyć na czynniki pierwsze liczbę \(\displaystyle{ n = 596947}\)
4. Obliczyć \(\displaystyle{ \varphi(270)}\).
5. Obliczyć \(\displaystyle{ \mu(6*7*11)}\).
6. Znaleźć największy wspólny dzielnik wielomianów \(\displaystyle{ f = X^4 + 1}\) i \(\displaystyle{ g = X^4 + X^3 + X + 1}\) należących do pierścienia \(\displaystyle{ \mathbb{F}_2[X]}\), oraz współczynniki \(\displaystyle{ a,b \in \mathbb{F}_2[X]}\), takie aby, \(\displaystyle{ NWD(f,g) = a*f+b*g}\).
7. Które z elementów ciała \(\displaystyle{ \mathbb{F}_{13}}\) są generatorami grupy multiplikatywnej \(\displaystyle{ \mathbb{F}_{13}^{*}}\) .
8. Znaleźć wszystkie jedności w pierścieniu \(\displaystyle{ \mathbb{Z}/15\mathbb{Z}}\).
B.
1. Wykazać, że zbiór liczb pierwszych jest nieskończony.
2. Sprawdzić, czy 127 jest liczbą złożoną? Omówić algorytm postępowania.
3. Znaleźć wszystkie rozwiązania układu kongruencji
\(\displaystyle{ x \ \equiv \ 1 \ mod \ 7}\)
\(\displaystyle{ x \ \equiv \ 2 \ mod \ 6}\)
mieszczące się w zakresie liczb \(\displaystyle{ 1 \leq x \leq 42}\). Ile jest takich rozwiązań i dlaczego?
4. Dane są funkcje \(\displaystyle{ F, f \ : \ \mathbb{N} \rightarrow \mathbb{C}}\). Wykazać, że dla dowolnego \(\displaystyle{ n \in \mathbb{N}}\) z równości
\(\displaystyle{ F(n) = \sum _{d|n} \ f(d)}\)
wynika równość
\(\displaystyle{ f(n) = \sum _{d|n} \mu(\frac{n}{d}) \ F(d)}\)
gdzie \(\displaystyle{ \mu}\) jest funkcją Möbiusa,
5. Jak zadana jest funkcja szyfrująca i funkcja deszyfrująca w systemie kryptograficznym RSA?
Dany jest iloczyn \(\displaystyle{ n = 551}\) dwóch liczb pierwszych oraz liczba \(\displaystyle{ e = 5}\), taka że \(\displaystyle{ 1 < e < \varphi(n)}\), \(\displaystyle{ (e, \varphi(n)) = 1}\). Zaszyfrować element \(\displaystyle{ a = 7}\) ze zbioru jednostek tekstu jawnego.
6. Niech R będzie pierścieniem przemiennym z jedynką. Podać definicję elementu odwracalnego w R. Wykazać, że odwrotność elementu odwracalnego w R jest wyznaczona jednoznacznie.
7. Podać przykład wielomianów \(\displaystyle{ f, g \in R[X]}\), gdzie R jest dowolnym pierścieniem, aby
\(\displaystyle{ deg(f \ + \ g) \ < \ max \ {deg(f), deg(g)}}\) .
8. Skonstruować tabelkę mnożenia dla ciała \(\displaystyle{ \mathbb{F}_3[X]/X^2 +1.}\)
9. Wiadomo, że macierz
\(\displaystyle{ G = \left( \begin{array}{cccccc}
1 & 3 & 1 &0&0&0\\
0 & 2 & 2 &3&1&0\\
0 & 2 & 0&1&0&1 \\
\end{array}\right)}\)
nad ciałem \(\displaystyle{ \mathbb{Z}_5}\) jest macierzą generującą pewnego kodu liniowego. Znaleźć macierz kontroli parzystości kodu dualnego.
C.
1. Omówić algorytm Euklidesa znajdowania największego wspólnego dzielnika.
Znaleźć \(\displaystyle{ NWD(529,-437)}\).
2. Wykorzystując metodę faktoryzacji Fermata rozłożyć na czynniki pierwsze \(\displaystyle{ n = 574425}\).
3. Mając dany iloczyn \(\displaystyle{ n = pq = 899}\) liczb pierwszych \(\displaystyle{ p, q}\) oraz wartość funkcji Eulera \(\displaystyle{ \varphi(899) = 840}\), znaleźć liczby \(\displaystyle{ p, q}\).
4. Znaleźć resztę z dzielenia liczby \(\displaystyle{ 4^{1000000}}\) przez \(\displaystyle{ n = 91 = 7*13}\).
Uwaga: Zastosować optymalną metodę.
5. Omówić algorytm szybkiego potęgowania. Wykorzystując ten algorytm obliczyć \(\displaystyle{ 3^{13}}\).
6. -
7. Niech R będzie pierścieniem przemiennym z jedynką. Podać definicję elementu odwracalnego w R. Wykazać, że odwrotność elementu odwracalnego w R jest wyznaczona jednoznacznie.
8. Podać definicję pochodnej dowolnego wielomianu z R[X], gdzie R jest dowolnym pierścieniem przemiennym z jedynką. Z definicji udowodnić, że \(\displaystyle{ (f+g)' = f' + g'}\).
D.
1. Zdefiniować funkcję Eulera i wykazać, że dla \(\displaystyle{ p \in P, k \in \mathbb{N}}\) zachodzi równość \(\displaystyle{ \varphi(p^k)=p^k - p^{k-1}}\)
2. Dane są funkcje \(\displaystyle{ F, f \ : \ \mathbb{N} \rightarrow \mathbb{C}}\) Wykazać, że jeśli spełniony jest warunek
\(\displaystyle{ \forall n \in \mathbb{N} \ :\ F(n)= \sum_{d|n} f(d)}\)
to implikuje on własność
\(\displaystyle{ \forall n \in \mathbb{N} \ :\ f(n)= \sum_{d|n}\mu (\frac{n}{d})\ F(d)}\)
gdzie \(\displaystyle{ \mu}\) jest funkcją Möbiusa.
3. Wykazać, że jeśli \(\displaystyle{ (l, N) = 1}\), to istnieje dokładnie jedna taka liczba \(\displaystyle{ k \ \in \ \mathbb{N}}\) z zakresu \(\displaystyle{ 1 \ < \ k \ < \ N-1}\), taka że \(\displaystyle{ lk \ \equiv \ 1 \ mod \ N}\).
4. Wykazać, że \(\displaystyle{ a \in \mathbb{K}}\)jest pierwiastkiem wielomianu \(\displaystyle{ f \in \mathbb{K}[X]}\) wtedy i tylko wtedy, gdy \(\displaystyle{ X-a | f}\).
5. Zdefiniować pochodną wielomianu f o współczynnikach z pierścienia przemiennego z jedynką.
Na podstawie tej definicji wykazać, że \(\displaystyle{ (f + g)' = f' + g'}\).
6. Dany jest wielomian nierozkładalny \(\displaystyle{ f \in \mathbb{F}_{23}[X]}\) stopnia \(\displaystyle{ k = 11}\). Ile elementów będzie miało ciało \(\displaystyle{ \mathbb{F}=\mathbb{F}_{23}[X]/f}\) ? Odpowiedź uzasadnić.
7. Zdefiniować kod MDS.
8. Wykazać, że jeśli \(\displaystyle{ H = (A, I_{n-k})}\) jest macierzą kontroli parzystości kodu liniowego \(\displaystyle{ C \subset \mathbb{F}^n_q}\)wymiaru k, to macierz \(\displaystyle{ G = (I_k, -A^T)}\) jest macierzą generującą tego kodu.
9. Zdefiniować syndrom słowa \(\displaystyle{ y \in \mathbb{F}^n_q}\)
10. Wiadomo, że macierz
\(\displaystyle{ H= \left( \begin{array}{cccccc}
1 & 3 & 1 &0&0&0\\
0 & 2 & 2 &3&1&0\\
0 & 2 & 0&1&0&1 \\
\end{array}\right)}\)
nad ciałem \(\displaystyle{ \mathbb{Z}_7}\) jest macierzą generującą pewnego kodu liniowego. Znaleźć macierz kontroli parzystości kodu.
Z góry dzięki! Będę wdzięczny za pomoc
Pozdrawiam, Maciek
