Zaczniemy na dzisiejszych ćwiczeniach od arytmetyki modularnej i na poczateku nieco teorii. Na poczatek dzielenie z resztą. Przyjmijmy pewne oznaczenia:
(moduł), oraz a calkowite. Podzielić liczbę a przez n to znaczy dokonać takiego przedstawienia, że
, gdzie q (liczba wyznaczająca ile n się mieści w a) i r (reszta z dzielenia) są całkowite oraz
, gdzie
. Inaczej takie dzielenie można zapisac jako

r = a mod n. Jeśli mamy dwie liczby calkowite a i b, to wówczas:

Teraz jakie mamy własności relacji
przystawania mod n. Są trzy:

1.
- zwrotność

2.
- symetria

3.
- przechodniość

Relacja spełniająca te wszystkie własności nazywana jest relacją równoważności. I można tu dokonać takiej operacji abstrakcji, że tworzymy klasy relacji równoważności dzieląc zbiór Z przez tą relacje równoważności co zapisujemy:
. I ten zbiór
to są te wszystkie możliwe wartości tej reszty. I teraz w tym zbiorze
jeżeli określimy działanie dodawania
i przyjmiemy
, to
. Grupę (
,
) nazwiemy grupa abelową, jeśli działanie dodawania modularnego w tym zbiorze spełnia nastepujące cztery własności:

1.
- łączność

2.
, gdzie 0 to element neutralny

3.
, gdzie - a = n - a będzie elmentem przeciwnym

4.
- przemienność

Jeśli czwarty warunek nie będzie spełniony, a inne tak, to jest to zwykła grupa. Jeśli którykolwiek z pierwszych trzech warunków nie będize spełniony, to nie będize to grupa.

I teraz przejdźmy do przykładów kodowania słów w oparciu o tą właśnie arytmetykę modularną. Będziemy uzywali szyfrów przesuwających. Na początek zajmiemy się grupą
, gdzie
i n = 26. Oznacza to, że kodując jakis tekst bedziemy mieli do czynienia z alfabetem 26 znakowym, gdzie każdemu znakowi przypisana będzie okreslona pozycja. Plus oznacza, że kodując będziemy dokonywali pewnego przesunięcia pozycji w prawo. Zobaczmy najpierw, jak będzie wyglądał nasz alfabet składających się z n liter, gdzie każdej przypisana jest odpowiednia pozycja z zakresu od 0 do 26. Będzie to klasyczny alfabet literowy:

a b c d e f g h i j k l m n o p q r s t u v w x y z

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

I nasz klucz niech wynosi k = 7 co będzie oznaczać, że będziemy przesuwac w prawo każdą literke tekstu jawnego o 7. Będziemy zatem na każdej pozycji literki z tekst jawnego dokonywać takiej operacji:
. A zatem niech naszym tekstem jawnym, który będizemy szyfrowali będzie tekst obecnosc obowiazkowa. Zobaczmy, jakie pozycje będą przypisane każdej z tych liter słowa według alfabetu:

o b e c n o s c | o b o w i a z k o w a

14 1 4 2 13 14 18 2 | 14 1 14 22 8 0 25 10 14 22 0

No i teraz zakodujmy stosując działanie
:

v i l j u v z j | v i v d p h g r v d h

21 8 11 9 20 21 25 9 21 8 21 9 15 7 6 17 21 3 7

Teraz w jaki sposób rozszyfrować podany tekst. Zamiast odejmować 7, czyli przesyuwać w lewo, można to zrobić prościej. Wystarczy skorzystać z działania
. Zatem należy do tych pozycji co dodaliśmy dodać 19 i podzielić modularnie przez 26. Jeśli otrzymaliśmy znów tekst jawny, to wszystko w porzadku, natomiast jeśli tekst otrzymany nie zgadza się z tekstem jawnym to znaczy, ze pomylilismy się najprawdopodobniej w obliczeniach.

Przejdźmy teraz do zagadnienia związanego z mnożeniem modularnym. Będziemy operowali grupą
i dla tej grupy przyjmując a i b calkowite musza być spełnione takie własności, że
. I wykonamy trzy takie tabelki działań dla określonych zbiorów:
. Zbiór oznaczony gwiazdką oznaczać będzie zbiór z odjęciem jednego elementu - 0. W tabeli wymnożymy wszystkie elementy w nawiasie stosując wszystkie możliwe kombinacje i dzieląc każda z nich modulo n. A zatem:

	1	2	3	4
1	1	2	3	4
2	2	4	1	3
3	3	1	4	2
4	4	3	2	1

	1	2	3	4	5
1	1	2	3	4	5
2	2	4	0	2	4
3	3	0	3	0	3
4	4	2	0	4	2
5	5	4	3	2	1

Dla pierwszej tabeli stosujemy modulo 5, a dla drugiej - modulo 6. Jeśli a jest różne od 0 i b jest różne od 0, oraz a razy b jest równe 0 mod n to takie liczby nazywamy dzielnikami zera. Widzimy w pierwszym przypadku, że nie ma takich dzielników, zaś w drugim przypadku mamy cztery takie przypadki. No i jeszcze istnieje element odwrotny. W pierwszym przypadku są dwa takie przypadki, bo 1 razy 1 mod 5 = 1, oraz 4 razy 4 mod 5 = 1. W drugim też 2 - 1 razy 1 mod 6 = 1, oraz 5 razy 5 mod 6 = 1. Dla odwrotności musi być spełniony warynek, że a i b sa równe, oraz wynikiem działania na tych liczbach musi być zawsze 1.

Teraz takie zadanie domowe. Wszelkie zadania domowe mają zostać wykonane w osobnym zeszycie 32 - kartkowym i są obowiązkowe. Należy zbadać (
), oraz
) modularnie - wykonac tabelę, sprawdzić dzielniki i elementy neutralne. Podobnie dla (
), oraz
).

Teraz z kolei zajmiemy się szyfrem afinicznym będącym uogólnieniem szyfru przesuwającego, gdzie klucz k bedzie miał postać k = (a, b), gdzie
, oraz
. Zaszyfrowanie nie stanowi problemu, natomiast problem pojawia się przy deszyfracji. Wówczas przyjmujemy, że
, oraz:

, gdzie
.

I ostatnie zadanie domowe będzie polegało na zaszyfrowaniu jakiegoś teksu jawnego tą metodą i zdeszyfrowaniu zakodowanego tekstu przyjmując, że a będzie różne od 1, a b różne od 0.

---