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