Podstawy teorii informacji

- teoria informacji
- teoria kodowania (kody optymalne, korekcyjne)
- podstawy kryptografii

Teoria informacji

Co jest nośnikiem, co zawartością (dane, informacja, wiadomości)

⇒ pojęcia podstawowe

należy wyróżnić.

• wiadomość //nośnik//

syntaktyka
słowo, zdanie
dane
nazwa

• informacja //zawartość//

semantyka
treść słowa, zdania
interpretacja danych
pojęcia

Przetwarzanie wiadomości:

α - przekształcenie

2

1

1

1

W

W

⎯

⎯ ⎯

←

⎯

⎯ →

⎯

−

α

α

o

- odwracalne, bez straty informacji

2

1

2

W

W

⎯

⎯ →

⎯

α

o

- ze stratą informacji

Elementy teorii grafów

Euler chciał przejść przez każdy most w Kaliningradzie dokładnie raz.

Grafem nazywamy trójkę

Γ=(E, K, r), gdzie:

E - niepusty zbiór, którego elementy nazywamy wierzchołkami (węzłami) grafu

K - zbiór, którego elementy nazywamy krawędziami grafu

r - relacja incydencji przypisująca każdej krawędzi co najmniej jeden i co najwyżej

dwa wierzchołki

Przedstawienia grafu:

• graficzne

• zbiór par

(

) (

) (

)

{

}

k e

k e

k e

1

1

2

1

2

3

,

;

,

;

,

;... , gdzie k

i

oznacza i-tą krawędź a e

j

j-ty wierzchołek

• macierz incydencji

e

e

e

e

e e e e

1

2

3

4

1

2

3

4

1 1 1 0
1 0 1 1
1 1 0 1
0 1 1 0

⎡

⎣

⎢

⎢

⎢

⎢

⎤

⎦

⎥

⎥

⎥

⎥

- tu nie rozróżniamy krawędzi

k

k

k

e e e e

1

2

3

1

2

3

4

1 0 0 0
1 0 1 0

M

⎡

⎣

⎢

⎢

⎢

⎢

⎤

⎦

⎥

⎥

⎥

⎥

Krawędź, z którą jest incydentny dokładnie jeden wierzchołek nazywamy pętlą.

Rzędem (stopniem) wierzchołka

nazywamy liczbę incydentnych z nim krawędzi, przy

czym pętle liczymy dwukrotnie.

Drogą

w grafie nazywamy ciąg, w którym występują na przemian wierzchołki i krawędzie;

wierzchołki i krawędzie sąsiadujące są incydentne. Drogą zamkniętą nazywamy drogę, w
której pierwszy wierzchołek jest też ostatnim. Rozróżniamy również drogę otwartą. Droga
prosta

to taka na której wierzchołki nie powtarzają się. Długością drogi nazywamy liczbę

krawędzi do niej należących.

Drogę, w której wszystkie krawędzie są różne nazywamy łańcuchem. Łańcuch, który jest
drogą zamkniętą to cykl.

Drogą Eulera

nazywamy cykl zawierający wszystkie krawędzie grafu. W grafie istnieje taka

droga, gdy wszystkie wierzchołki mają parzysty stopień. Drogą jednobieżną lub otwartą
drogą Eulera

nazywamy łańcuch, który nie jest cyklem, zawierający wszystkie krawędzie

grafu. W grafie istnieje taka droga, gdy dokładnie dwa wierzchołki mają nieparzysty stopień.

Łańcuch Hamiltona to

droga prosta zawierająca wszystkie wierzchołki grafu.

Graf jest spójny wtedy gdy dla dowolnych dwóch wierzchołków istnieje droga, w której
wierzchołki te są wierzchołkami początkowym i końcowym.

Graf nazywamy zorientowanym lub skierowanym jeżeli każdej krawędzi
przyporządkujemy wierzchołek początkowy i końcowy.

• relacje incydencji

( )

(

)

( )

{

}

k e

k e

k e

1

1

1

2

2

2

,

;

,

;

,

;... , przy czym e

i

oznacza, że wierzchołek jest

początkowy, natomiast e

i

że jest końcowy

• macierz:

k

k

k

a

b

a

b

b

a

e e e

1

2

3

1

2

3

0

0

0

⎡

⎣

⎢

⎢

⎢

⎤

⎦

⎥

⎥

⎥

i a oznacza wierzchołek początkowy, b oznacza końcowy, p.

oznacza początkowy i końcowy jednocześnie, a 0 oznacza, że jest nieincydentny

Grafy ważone

to grafy, w których krawędziom przyporządkowane są liczby rzeczywiste

(wagi).

Grafy spójne zawierające co najmniej jedną krawędź i nie zawierające cykli nazywamy
drzewem

.

Graf zorientowany nazywamy drzewem zorientowanym gdy zawiera on dokładnie jeden
węzeł, który nie jest węzłem końcowym żadnej krawędzi (korzeń), a każdy z pozostałych
węzłów jest węzłem końcowym dokładnie jednej krawędzi. Poziomem węzła nazywamy
długość drogi od korzenia do tego węzła.

Jeżeli liczba krawędzi wychodzących z każdego węzła jest ograniczona z góry liczbą r to
drzewo nazywamy r-narnym. Jeżeli poziomy wszystkich węzłów końcowych są jednakowe i
równe h to drzewo nazywamy drzewem h-poziomowym. Jeżeli w drzewie r-narnym z
każdego węzła nie będącego liściem wychodzi dokładnie r krawędzi to drzewo nazywamy
drzewem pełnym

.

Nierówność Krafta

: Liczby naturalne m

1

, m

2

, ..., m

n

, są poziomami końcowymi drzewa r-

narnego gdy:

r

m

i

n

i

−

=

∑

≤

1

1

Zbiory wiadomości

Rodzaje zbiorów:

• prosty:

{

}

W

w w

w

n

=

1

2

,

,...,

, gdzie w

i

- wiadomość elementarna

• złożony: zbiór wiadomości zawiera ciągi

{

}

w w

w

i

i

ik

1

2

,

,...,

, gdzie w

W

ij

∈

Przykład

{

}

W

= 01

9

, ,..., , k = 4,

(

) (

)

0000

9999

−

• wielowymiarowy: A A

A

m

1

2

,

,...,

- zbiory proste, m wymiarowym zbiorem wiadomości

określonym na zbiorach prostych A A

A

m

1

2

,

,...,

nazywamy iloczyn kartezjański

A

A

A

m

1

2

×

× ×

...

Przykład

{

}

D

= 1 2

31

, ,...,

{

}

M

I II

XII

= , ,...,

{

}

L

= 0000 0001

9999

,

,...,

np. 12 X 1995, UWAGA! D M L

L

M

D

×

× ≠ ×

×

Ilość informacji. Źródło wiadomości.

Ilość informacji to wielkość związana z prawdopodobieństwem pojawienia się,
wygenerowania tej informacji. Im większe prawdopodobieństwo, tym mniejszą ilość
informacji niesie wiadomość.

{

}

W

w w

w

n

=

1

2

,

,...,

Def.

( )

( )

I w

p w

r

i

r

i

= log

1

.

Ilość informacji wyrażamy w jednostkach r-narnych. Np. gdy r = 2 to jednostką jest bit, a gdy
r = e to jednostką jest nat.

Jeżeli dane są zbiór wiadomości

{

}

W

w w

w

n

=

1

2

,

,...,

i prawdopodobieństwa wygenerowania

tych wiadomości

( ) ( )

( )

p w

p w

p w

n

1

2

,

,...,

to mamy określone źródło wiadomości.

Def. Źródło nazywamy źródłem bezpamięciowym jeżeli prawdopodobieństwo

(

)

( )

( )

p w w

p w

p w

i

j

i

j

,

=

⋅

.

Inaczej:

(

) ( )

p w

w

p w

j

i

j

/

=

dla i,j = 1,2,...,n

Umowa: co wcześniej, co później

(

)

w w

i

j

,

- to oznacza, że pojawiła się wiadomość w

i

przed

w

j

.

Def. Średnią ilość informacji przypadającą na wiadomość generowaną przez źródło
nazywamy entropią źródła.

( )

( ) ( )

( )

( )

H W

p w

I w

p w

p w

r

i

r

i

i

n

i

r

i

i

n

=

⋅

=

⋅

=

=

∑

∑

1

1

1

log

( )

p w

p

i

i

=

, r

= 2

( )

H W

p

p

r

i

i

i

n

=

⋅

=

∑

log

1

1

Tw.

Entropia przyjmuje wartość maksymalną, gdy p

p

p

n

n

1

2

1

=

= =

=

...

i równa jest

log

r

n

Identyfikacja źródła wiadomości.

W={ w

1

, w

2

, ..., w

n

}, p

1

, p

2

, ..., p

n

Aby wiedzieć jaką wiadomość wysyła to źródło to mamy zestaw pytań r-narnych. Nazywa się
to systemem identyfikacji źródła wiadomości.

Każdej wiadomości w systemie identyfikacji odpowiada pewna liczba zapytań, oznaczamy ją
przez

i

l , dla wiadomości

i

w . Jakość systemu identyfikacji określa wtedy średnia liczba

pytań przypadająca na wiadomość.

( )

E s

p l

r

i

i

i

n

=

⋅

=

∑

1

Kody - podstawowe pojęcia.

Zbiór wiadomości - W, alfabet, zbiór liter alfabetu - X.

Def. Kodem nazywamy dowolne przyporządkowanie, w którym każdemu ciągowi
wiadomości ze zbioru W odpowiada ciąg liter alfabetu ze zbioru X.

Przykład.

{

}

W

w w w w

=

1

2

3

4

,

,

,

{ }

X

= 01

,

albo

w

1

0 0

w

2

1 00

w

3

0 11

w

4

1 00

Kod nazywamy blokowym jeśli każdej wiadomości w

i

ze zbioru W odpowiada ciąg x

i

(ciąg

kodowy

, słowo kodowe) ze zbioru X.

Def. Kod blokowy nazywamy kodem nieosobliwym jeżeli słowa kodowe są parami różne.

Przykład.

albo

w

1

00 0

w

2

01 00

w

3

11 1

w

4

10 11

Def. K-krotnym rozszerzeniem kodu blokowego nazywamy kod, w którym każdemu
ciągowi wiadomości (w

i1

, w

i2

, ..., w

ik

) ze zbioru W odpowiada ciąg liter alfabetu (x

i1

, x

i2

, ...,

x

ik

) gdzie x

ij

- słowo kodowe odpowiadające wiadomości w

ij

.

Przykład.

(

)

( )

w w

1 1

00

→

(

)

(

)

w w

1

2

000

→

(

)

( )

w w

1

3

01

→

..................

(

)

(

)

w w

4

4

1111

→

Def. Kod blokowy nazywamy kodem jednoznacznie dekodowalnym wtedy, gdy k-krotne
rozszerzenie tego kodu jest kodem nieosobliwym dla dowolnego k.

Przykład.

{

}

W

w w w w

=

1

2

3

4

,

,

,

K

1

K

2

w

1

00 0

w

2

01 01

w

3

10 011

w

4

11 0111

Def. Kod blokowy nazywamy kodem jednoznacznie dekodowalnym bez opóźnienia,
wtedy, gdy żadne słowo kodowe nie jest przedrostkiem żadnego innego słowa kodowego.
Kod jest kodem równomiernym, gdy słowa kodowe są równej długości.

Konstrukcja kodów jednoznacznie dekodowalnych bez opóźnienia

Źródło

{

}

W

w w

w

n

=

1

2

,

,...,

i p p

p

n

1

2

, ,...,

System identyfikacji, r = 3
Znając r-narny system identyfikacji źródła wiadomości kodujemy r-narny kod jednoznacznie
dekodowalny bez opóźnienia za pomocą następującej procedury:

1. Krawędzie wychodzące z każdego węzła drzewa oznaczamy różnymi literami alfabetu.
2. Spisujemy litery oznaczające krawędzie należące do drogi od korzenia do każdego węzła

końcowego. Ciągi liter odpowiadające poszczególnym węzłom końcowym są słowami
kodowymi wiadomości przyporządkowanych tym węzłom.

Def. Kod

r-narny zbudowany zgodnie z podaną procedurą jest kodem jednoznacznie

dekodowalnym bez opóźnienia.

Znając kod r-narny jednoznacznie dekodowalny bez opóźnienia można zbudować r-narny
system identyfikacji źródła wiadomości stosując następującą procedurę:

1. Budujemy h-poziomowe r-narne drzewo pełne, w którym h równe jest maksymalnej

długości słowa kodowego danego kodu.

2. Krawędzie wychodzące z każdego węzła oznaczamy różnymi literami alfabetu.
3. Redukujemy drzewo pozostawiając wyłącznie krawędzie, które tworza drogi od korzenia

do węzłów końcowych oznaczone literami zgodnymi ze słowami kodowymi kodu.

4. Węzły końcowe zredukowanego drzewa oznaczamy odpowiednimi wiadomościami a

pozostałym węzłom przyporządkowujemy odpowiednie pytania r-narne

1.

( ) ( )

l w

d w

i

i

=

dla i = 1,2,...,k

( )

E s

p l

r

i

i

i

n

=

⋅

=

∑

1

; średnia liczba pytań r-narnych

( )

E k

d l

r

i

i

i

n

=

⋅

=

∑

1

; średnia długość słowa kodowego

2.

( )

( )

E s

E k

r

r

=

Dane jest źródło

2

1

2

W

W

⎯

⎯ →

⎯

α

o

i p p

p

n

1

2

, ,...,

Mówimy, że kod K

1

jest lepszy od kodu K

2

jeżeli średnia długość słowa kodowego

( )

( )

E K

E K

r

r

1

1

<

Kod K nazywamy kodem optymalnym, jeżeli dla każdego kodu K'

( )

( )

E K

E K

r

r

≤

'

Używana jest również nazwa kod zwięzły.

Źródło rozszerzone

- zbiór złożony
- kod rozszerzony (k - krotne rozszerzenie kodu)

{

}

W

w w

w

n

=

1

2

,

,...,

i p p

p

n

1

2

, ,...,

- źródło bezpamięciowe

k - krotnie rozszerzone

{

}

W

w w

w

k

k n

=

⋅

1

2

,

,...,

, gdzie

(

)

w

w w

w

i

i

i

ik

=

1

2

,

,...,

, w

W

ij

∈ , dla j = 1,...,k

( ) ( ) ( ) ( )

p w

p w

p w

p w

i

i

i

ik

=

⋅

⋅ ⋅

1

2

...

Entropia tego źródła:

( )

( )

( )

H W

p w

p w

r

k

i

r

i

i

n

i

n

i

n

k

=

⋅

=

=

=

∑

∑

∑

L

log

1

1

1

1

2

1

( )

( )

( )

H W

p w

p w

r

k

i

r

i

W

k

=

⋅

∑

log

1

Można wykazać, że

( )

( )

H W

k H W

r

k

r

= ⋅

Źródło ciągów Markowa

{

}

W

w w

w

n

=

1

2

,

,...,

Mówimy, że źródło W jest źródłem ciągów Markowa m - tego rzędu, jeżeli znane są
prawdopodobieństwa warunkowe:

(

)

P w

w

w

w

i

j

j

jm

/

,

,...,

1

2

(

) (

)

(

)

(

) (

)

(

)

(

) (

)

(

)

P

w

w

w

p w

w

p w

w

p w

w

p w

w

p w

w

p w

w

p w

w

p w

w

p w

w

w

w

w

n

n

n

n

n

n

n

n

=

⎡

⎣

⎢

⎢

⎢

⎢

⎢

⎤

⎦

⎥

⎥

⎥

⎥

⎥

1

2

1

1

2

1

1

1

2

2

2

2

1

2

1

2

M

L
L

M

M

O

M

L

L

/

/

/

/

/

/

/

/

/

( ) (

) (

)

(

)

p w

p w w

p w w

p w w

n

1

1

1

2

1

1

=

+

+ +

,

,

...

,

( ) (

) ( ) (

) ( )

(

) ( )

p w

p w

w

p w

p w

w

p w

p w

w

p w

n

n

1

1

1

1

1

2

2

1

=

⋅

+

⋅

+ +

⋅

/

/

...

/

(

)

( )

w w

1

3

01

→

Ilość informacji pod warunkiem, że źródło w określonym stanie:

(

)

(

)

I w

w

w

w

p w

w

w

w

r

i

j

j

jm

r

i

j

j

jm

/

,

,...,

log

/

,

,...,

1

2

1

2

1

=

Średnia ilość informacji zawartej w wiadomości wygenerowanej w określonym stanie:

(

)

(

) (

)

∑

=

⋅

=

n

i

jm

j

j

i

r

jm

j

j

i

jm

j

j

r

w

w

w

w

I

w

w

w

w

p

w

w

w

w

H

1

2

1

2

1

2

1

,...,

,

/

,...,

,

/

,...,

,

/

A ogólnie , w dowolnym stanie:

( )

(

) (

)

∑

⋅

=

m

W

jm

j

j

r

jm

j

j

r

w

w

w

w

H

w

w

w

p

w

H

,...,

,

/

,...,

,

2

1

2

1

( )

(

)

(

) (

)

⎟

⎠

⎞

⎜

⎝

⎛

⋅

⋅

⎟

⎠

⎞

⎜

⎝

⎛

=

∑

∑

=

=

jm

j

j

i

r

n

i

jm

j

j

i

n

i

jm

j

j

r

w

w

w

w

I

w

w

w

w

p

w

w

w

p

w

H

,...,

,

/

,...,

,

/

,...,

,

2

1

1

2

1

1

2

1

( )

(

) (

)

(

)

H w

p w

w

w

p w

w

w

w

p w

w

w

w

r

j

j

jm

i

j

j

jm

W

r

i

j

j

jm

m

=

⋅

⋅

+

∑

1

2

1

2

1

2

1

1

,

,...,

/

,

,...,

log

/

,

,...,

{

}

W

w w

w

n

=

1

2

,

,...,

- źródło bezpamięciowe generujące wiadomości z

prawdopodobieństwami równymi prawdopodobieństwom ergodycznym źródła Markowa m -
tego rzędu. Nazywamy je źródłem stowarzyszonym.

( )

( )

H w

H w

r

r

≥

równość ta ma miejsce wtedy i tylko wtedy gdy prawdopodobieństwa:

(

)

( )

p w

w

w

w

p w

i

j

j

jm

i

/

,

,...,

1

2

=

dla wszystkich stanów.

Kody optymalne

{

}

W

w w

w

n

=

1

2

,

,...,

; p p

p

n

1

2

, ,...,

;

( )

k

E k

r

−

Tw.

( )

( )

E k

H w

r

r

≥

- żeby zapisać wiadomość ze źródła W potrzeba zorganizować

przynajmniej tyle ile wynosi średnia ilość informacji

Tw. Dla dowolnego źródła wiadomości

{

}

W

w w

w

n

=

1

2

,

,...,

; p p

p

n

1

2

, ,...,

można zbudować

kod jednoznacznie dekodowalny bez opóźnienia taki, że:

( )

( )

( )

H w

E k

H w

r

r

r

≤

<

+1

(jedna jednostka r-narna)

• Algorytm wyznaczania r-narnego kodu dla źródła

{

}

W

w w

w

n

=

1

2

,

,...,

;

p p

p

n

1

2

, ,...,

;

1. Rozszerzać źródło wiadomości dodając wiadomości z prawdopodobieństwami

równymi 0, aż liczba wiadomości będzie równa

(

)

r

k

r

+ ⋅ −1

, k N

∈ .

2. Uporządkować wiadomości wg niemalejących wartości prawdopodobieństw.
3. Zastąpić r wiadomości z najmniejszymi prawdopodobieństwami jedną wiadomością z

prawdopodobieństwem równym sumie prawdopodobieństw wiadomości
zastępowanych.

4. Sprawdzić czy liczba wiadomości jest równa 1. Jeśli nie, to wykonać czynność 2.

Jeżeli tak to czynność 5.

5. Zbudować r-narne drzewo, w którym węzły odpowiadają wiadomościom, a krawędzie

łączą węzły (wiadomości) za zastępujące z wiadomościami zastępowanymi.

6. Zbudować r-narny kod zgodny z drzewem otrzymanym (r-narnym) tj.

b)

oznaczyć krawędzie literami alfabetu

c)

ustalić ciągi liter na drogach od korzenia do liści

Tw. Kod wyznaczony zgodnie z powyższym algorytmem jest kodem optymalnym

Tw. (Shannona) Dla kodu

K

k

(źródła k-krotnie rozszerzonego) spełniającego warunek

( )

( )

( )

H W

E K

H W

r

k

r

k

r

k

≤

<

+1

zachodzi zależność:

( )

( )

lim

k

r

k

r

E K

k

H W

→∞

=

Jeżeli zbudujemy taki kod to dla kolejnych rozszerzeń źródła wiadomości mamy ciąg, którego
granicą jest średnia entropia źródła wiadomości.

Metody kompresji

Jak przedstawić krócej wiadomości niż zostały przedstawione?
Jeśli

( )

( )

E K

H W

r

r

=

, to nie da się krócej zapisać ciągu.

Jeśli

( )

( )

E K

H W

r

r

≠

, to ciąg z nadmiarem.

( )

( )

µ

=

H W

E K

r

r

- sprawność kodu,

0

1

< ≤

µ

( )

( )

( )

λ

µ

= − =

−

1

E K

H W

E K

r

r

r

- rozwlekłość (redundancja) kodu

l

wej

- długość ciągu początkowego

l

wyj

- długość ciągu po zastosowaniu kompresji

k

l

l

wej

wyj

=

- jakość kompresji (współczynnik)

Metody kompresji dzielimy na:
a) bez straty informacji (odwracalne)
b) ze stratą informacji (nieodwracalne)

• Kompresja ciągów binarnych

1. Bezpośrednie kodowanie runów

Runem nazywamy dowolny skończony podciąg binarny. Będziemy wyróżniać runy tzw.
zerowe i jedynkowe. Runy zerowe to ciąg złożone z zer i zakończonych jedynką, a
jedynkowe na odwrót.

Runy zerowe

(1)

(01) (001) (00...001)

Runy jedynkowe (0)

(10) (110) (11...110)

Ciąg zerowy

(00...00)

Ciąg jedynkowy (11...11)

Podany ciąg binarny dzielimy na runy; wyznaczamy prawdopodobieństwa występowania
tych runów; wtórnie kodujemy;

Przykład.
01 001 1 001 01 01 1 01 000 01 000 01 1
n - maksymalna długość runu i również długość ciągu zerowego

3

=

n

1 - 3

( )

13

3

1

=

p

1

w

01 - 6

( )

13

6

01

=

p

2

w

001 - 2

( )

13

2

001

=

p

3

w

000 - 2

( )

13

2

000

=

p

4

w

2. Metoda Golomba

n - parametr

n

k

= 2

, czyli n = 2,4,8,...

Każdemu runowi przyporządkowany jest ciąg binarny złożony z rdzenia, separatora i
końcówki.
• rdzeń - ciąg złożony wyłącznie z liter 1, których liczba jest równa części całkowitej

l

n

−1

, gdzie l - długość runu

• separator - zawsze litera 0

• końcówka - ciąg będący resztą z dzielenia

l

n

−1

zapisany na

log n

pozycjach

3. Rozrzedzanie ciągów

Dzieli się ciąg binarny na podciągi o określonej długości i ponownie koduje dając temu,
który występuje najczęściej same zera.

• Kompresja obrazów

1. Kompresja obrazów czarno-białych

ƒ

Przedstawienie za pomocą wyrażenia z nawiasami

k

k

2

2

×

k

2

k

2

(O) = ((I)(II)(III)(IV)) = (0(101(0(0101)01))(0(1100)0(1011))1)
1 - pole czarne
0 - pole białe

{

}

1

,

0

),

(,

=

W

( 00
) 01

0 10
1 11

ƒ

przedstawienie za pomocą drzewa czwórkowego

2. obrazy z gradacją kontrastu

k

k

2

2

×

p - pole

x

- piksel

( )

x

s

- stopień szarości

k

- liczba pikseli należących do p

( )

p

s

- średni stopień szarości pola p

( )

( )

∑

∈

=

p

x

x

s

k

p

s

1

( )

p

δ

- odchylenie standardowe stopnia szarości pikseli w polu p

( )

( ) ( )

(

)

k

x

s

p

s

p

p

x

∑

∈

−

=

2

δ

δ - wartość progowa odchylenia standardowego stopnia szarości pikseli

Kanały informacyjne

Nadawca:
- generowanie wiadomości
- kodowanie
- modulacja

NADAWCA

KANAŁ

ODBIORCA

Kanał
- przesyłanie

Odbiorca
- odbiór
- demodulacja
- dekodowanie

Kanał informacji to:
1. Źródło wiadomości

{

}

W

w w

w

n

=

1

2

,

,...,

;

p p

p

n

1

2

,

,...,

2. Macierz kanału (kanał)
3. Zbiór informacji odebranych:

{

}

Z

z z

z

m

=

1

2

, ,...,

;

( ) ( )

( )

p z

p z

p z

m

1

2

,

,...,

Macierz kanału P jest macierzą prawdopodobieństw warunkowych

(

)

p z

w

j

i

/

, gdzie

i =1,2,...,n, j = 1,2,..,m

P

w

w

w

p

p

p

p

p

p

p

p

p

z

z

z

n

m

m

n

n

nm

m

=

⎡

⎣

⎢

⎢

⎢

⎢

⎤

⎦

⎥

⎥

⎥

⎥

1

2

11

12

1

21

22

2

1

2

1

2

M

L
L

M

M

O

M

L

L

,

(

)

p

p z

w

ij

j

i

=

/

Kanał definiujemy też jako macierz P. Musi ona spełniać warunki:

(

)

p z

w

p

j

i

j

n

ij

j

m

/

= ⇔

=

=

=

∑

∑

1

1

1

1

Przykład.

P

=

⎡
⎣

⎢

⎤
⎦

⎥

1

2

1

4

1

8

1

8

1

3

1

3

1

3

0

0

0

, to może być macierz kanału

Interpretacja: jeżeli była nadana jakaś wiadomość, to musi być odebrana jako jakaś
wiadomość ze zbioru Z.

Typy kanałów:
1. Kanał idealny

(W i Z równoliczne)

( )

( )

card W

card Z

=

oraz

(

)

p z

w

j

i

/

= ∨

0 1

2. Kanał odwracalny

(ogólniejszy)

( )

( )

card W

card Z

≤

; Na podstawie odebranej wiadomości jednoznacznie

wiemy, co nadano.

3. Kanał deterministyczny

( )

( )

card W

card Z

≥

; Wiemy jaka wiadomość będzie odebrana, jeśli wiemy jaką

nadaliśmy.

1. Kanał binarny (symetryczny)

P

p

p

p

p

=

−

−

⎡
⎣

⎢

⎤
⎦

⎥

1

1

Parametry kanału informacyjnego

(

)

[

]

P

p z

w

j

i

=

/

;

(

)

p w

z

i

j

/

?

=

Mamy źródło wiadomości

{

}

W

w w

w

n

=

1

2

,

,...,

; p p

p

n

1

2

,

,...,

(

) ( ) ( )

p w

z

p z

p w z

i

j

j

i

j

/

,

⋅

=

(

)

( )

(

)

p z

w

p w

p w z

j

i

i

i

j

/

,

⋅

=

← kolejność nie jest istotna

⇓

(

) ( ) (

)

( )

p w

z

p z

p z

w

p w

i

j

j

j

i

i

/

/

⋅

=

⋅

(

) (

)

( )

( )

p w

z

p z

w

p w

p z

i

j

j

i

i

j

/

/

=

⋅

( ) (

)

( )

(

)

( )

(

)

( )

p z

p z

w

p w

p z

w

p w

p z

w

p w

j

j

j

j

n

n

=

⋅

+

⋅

+ +

⋅

/

/

...

/

1

1

2

2

⇓

( )

(

)

( )

p z

p z

w

p w

j

j

i

i

i

n

=

⋅

=

∑

/

1

( )

(

)

[

]

P

p w

z

i

j

−

=

1

/

- macierz kanału odwróconego, macierz prawdopodobieństw odwrotnych

•

(

)

(

)

I w

z

p w

z

r

i

j

r

i

j

/

log

/

=

1

; w idealnym

I

r

= 0

, jak różne to warto się zapytać o średnią

•

(

)

(

) (

)

(

)

(

)

H w z

p w

z

I w

z

p w

z

p w

z

r

j

i

j

r

i

j

i

n

i

j

r

i

j

i

n

/

/

/

/

log

/

=

⋅

=

⋅

=

=

∑

∑

1

1

1

(

)

( ) (

)

H W Z

p z

H W z

r

j

r

j

j

m

/

/

=

⋅

=

∑

1

(

)

( )

(

)

(

)

( ) (

)

(

)

H W Z

p z

p w

z

p w

z

p z

p w

z

p w

z

r

j

i

j

r

i

j

i

n

j

m

j

i

j

r

i

j

j

m

i

n

/

/

log

/

/

log

/

=

⋅

⋅

⎛

⎝

⎜

⎜

⎞

⎠

⎟

⎟ =

⋅

⋅

=

=

=

=

∑

∑

∑

∑

1

1

1

1

1

1

(

)

(

)

(

)

H W Z

p w z

p w

z

r

i

j

r

i

j

j

m

i

n

/

,

log

/

=

⋅

=

=

∑

∑

1

1

1

i to się nazywa stratą informacji w kanale

•

(

)

I W Z

r

,

- średnia ilość informacji przekazywanych przez kanał informacyjny

•

( )

H W

r

- średnia po stronie nadawcy

( )

(

)

(

)

H W

H W Z

I W Z

r

r

r

−

=

/

,

⇓

(

)

( )

(

)

( )

( )

(

)

(

)

I W Z

H W

H W Z

p w

p w

p w z

p w

z

r

r

r

i

r

i

i

n

i

j

r

j

m

i

j

i

n

,

/

log

,

log

/

=

−

=

⋅

−

⋅

=

=

=

∑

∑

∑

1

1

1

1

1

a ponieważ:

( )

(

)

( )

p z

p z

w

p w

j

j

i

i

j

n

=

⋅

=

∑

/

1

( )

(

) ( )

p w

p w

z

p z

i

i

j

j

j

n

=

⋅

=

∑

/

1

||

(

)

p w z

i

j

i

n

,

=

∑

1

mamy więc:

(

)

(

) ( )

( )

(

)

(

)

(

)

( )

(

)

(

)

(

)

(

)

( )

I W Z

p w

z

p z

p w

p w z

p w

z

p w z

p w

p w z

p w

z

p w z

p w

z

p w

r

i

j

j

j

m

r

i

i

n

i

j

r

j

m

i

j

i

n

i

j

r

i

j

m

i

n

i

j

r

j

m

i

j

i

n

i

j

r

i

j

i

j

m

i

n

,

/

log

,

log

/

,

log

,

log

/

,

log

/

=

⋅

⎛
⎝

⎜

⎞
⎠

⎟ ⋅

−

⋅

=

=

⋅

−

⋅

=

=

⋅

=

=

=

=

=

=

=

=

=

=

∑

∑

∑

∑

∑

∑

∑

∑

∑

∑

1

1

1

1

1

1

1

1

1

1

1

1

1

1

ale zauważmy:

(

) ( ) ( )

p w

z

p z

p w z

i

j

j

i

j

/

,

⋅

=

, a stąd

(

) (

)

( )

p w

z

p w z

p z

i

j

i

j

j

/

,

=

⇓

(

)

(

)

(

)

( )

( )

∑∑

=

=

⋅

⋅

=

n

i

m

j

j

i

j

i

r

j

i

r

z

p

w

p

z

w

p

z

w

p

Z

W

I

1

1

,

log

,

,

I tu symetria, przestawiamy w

i

z z

j

i to ma praktyczną INTERPRETACJĘ:

H

r

(W|Z)

H

r

(Z|W)

H

r

(W)

H

r

(Z)

I

r

(W,Z)

H

r

(W,Z)

Def. Przepustowość kanału

( )

(

)

(

)

C

I W Z

W

r

= max

,

Π

//ustalona poprzez dobieranie prawdopodobieństw wiadomości generowanych przez źródło//

( )

(

)

Π W

p p

p

p

n

i

i

n

=

=

⎧

⎨

⎩

⎫

⎬

⎭

=

∑

1

2

1

1

,

,...,

:

,

( )

p

p w

i

i

=

//bardzo złożony algorytm wyznaczania tego//
Interpretacja:

[

]

(

)

(

)

[

]

[

]

P

p z

w

n m

j

i

n m

×

×

=

/

n - wierszy, m - kolumn

Reguły decyzyjne

Pozwalają określić jaka wiadomość została nadana

z

j

- wiadomość odebrana

w * - wiadomość przyjęta z a nadaną (ustalona jako nadana)

Miara błędu, jaki popełniamy:

( )

(

)

p e z

p w

z

j

j

/

* /

= −

1

Średni błąd decyzji:

( )

( )

( )

p e

p e z

p zj

j

j

m

=

⋅

=

∑

/

1

Dobre decyzje - gdy minimalizujemy tę sumę, czyli gdy przyjmiemy taką wiadomość w
każdym przypadku, aby błąd konkretnej decyzji wiadomości był minimalny:

(1.)

(

) (

)

p w

z

p w

z

j

i

j

* /

/

≥

, gdzie i = 1,2,...,n

Czyli bierzemy teraz macierz kanału odwróconego

( )

P

−1

. Sposób wyboru decyzji nazywamy

regułą decyzyjną

. (1.) nazywana jest regułą największego prawdopodobieństwa.

Przykład.

{

}

W

w w w

=

1

2

3

,

,

,

{

}

Z

z z z

=

1

2

3

, ,

, p

1

0

= ,2 , p

2

0

= ,7 , p

3

0 1

= ,

P

w

w

w

z z z

=

⎡

⎣

⎢

⎢

⎢

⎤

⎦

⎥

⎥

⎥

1

2

3

1

2

3

0 1 0

0

0 8 0 1 0 1

0 1 0

0 5

,

,2

,7

,

,

,

,

,4

,

i na tej podstawie, na podstawie macierzy kanału nie da się tego

określić!!

Napiszmy tę samą regułę inaczej:

(2.)

(

)

( )

( )

(

)

( )

( )

p z

w

p w

p z

p z

w

p w

p z

j

j

j

i

i

j

/ *

*

/

⋅

≥

⋅

i tu widzimy jak obliczać ale jeszcze inaczej:

(3.)

(

)

( )

(

)

( )

p z

w

p w

p z

w

p w

j

j

i

i

/ *

*

/

⋅

≥

⋅

Jeśli nie znamy prawdopodobieństw p p

p

n

1

2

,

,...,

i nie mamy żadnych innych przesłanek to

przyjmuje się, że:

p

p

p

n

1

2

=

= =

...

(Największej wiarygodności)

⇓

(4.)

(

) (

)

p z

w

p z

w

j

j

i

/ *

/

≥

, dla i = 1,2,...,n

Mówimy, że określona jest reguła decyzyjna jeżeli wiemy jaką wiadomość przyjąć za
nadaną, gdy znamy wiadomość odebraną.

Przykład.

{

}

Z

z z

z

=

1

2

5

, ,...,

,

{

}

W

w w w

=

1

2

3

,

,

Z

z

1

z

2

z

3

z

4

z

5

W

w

2

w

3

w

1

w

2

w

3

Z

{ }

z

3

{

}

z z

1

4

,

{

}

z z

2

5

,

W

w

1

w

2

w

3

Reguła decyzyjna jest określona przez funkcję:

f

W

:Z

→

, gdzie Z jest podziałem zbioru wiadomości odebranych Z, czyli

{

}

Z

= z z

z

k

1

2

, ,...,

,

gdzie z

Z

i

⊆ dla i = 1,2,...,k; z

z

i

j

∩

= 0 dla i

j

≠ ;

z

Z

i

i

k

=

=

1

U

Strata i ryzyko

Przykład.

(

)

R w w

i

*,

- funkcja strat, gdzie:

w

i

-wiadomość rzeczywiście nadana

w * - wiadopmość ustalona jako nadana

• ogólny przykład definiowania:

{

}

W

w w

=

1

2

,

, R - w dowolnych jednostkach

1)

(

)

(

)

R w w

R w w

1

1

1

1

2

2

0

,

,

=

=

(

)

(

)

R w w

R w w

1

1

2

1

2

1

1

,

,

=

=

2)

R

c w

w

i

2

=

−

*

, gdzie w

w

w

w

w

w

i

j

i

j

i

j

−

=

=

≠

⎧

⎨

⎩⎪

0

1

gdy

gdy

3)

{

}

W

w w

w

n

=

1

2

,

,...,

( )

R

c w

w

i

3

=

−

*

• Ustalona jest reguła decyzyjna r i funkcja strat

(

)

R w w

i

*,

Średnia strata przy stosowaniu reguły r określa wówczas funkcja:

(

)

(

)

r

R w w

p w z

i

i

j

j

m

i

n

=

⋅

=

=

∑

∑

*,

,

1

1

Kody korekcyjne

Przestrzeń wektorowa

( )

r

GF

n

W przestrzeni wektorowej

( )

2

n

GF

elementami są ciągi (wektory) binarne.

Należy określić operacje dodawania wektorów i mnożenia wektora przez skalar.

Oznaczenia: a, b, c - skalary, u, v, w - wektory

Dodawanie:

(

)

n

u

u

u

u

,...,

,

2

1

=

,

(

)

n

v

v

v

v

,...,

,

2

1

=

(

)

n

n

v

u

v

u

v

u

v

u

⊕

⊕

⊕

=

⊕

,...,

,

2

2

1

1

,

gdzie

⎩

⎨

⎧

≠

=

=

⊕

i

i

i

i

i

i

v

u

v

u

v

u

gdy

1

gdy

0

, czyli

(

)

2

mod

i

i

i

i

v

u

v

u

+

=

⊕

Kody liniowe - struktura i własności

Def. Zbiór

słów kodowych oznaczać będziemy przez

( )

K n k

, - kod liniowy, w którym n -

długość słowa kodowego, k - liczba pozycji informacyjnych niezbędnych do rozróżnienia 2

k

kodowanych wiadomości

Def. Odległością

( )

d u v

, słów kodowych u i v kodu

( )

K n j

,

nazywamy liczbę pozycji, na

których wartości w ciągach u i v są różne.

Def. Wagą słowa

( )

w v

słowa kodowego v nazywamy liczbę jedynek występujących w tym

słowie.

Def. Minimalną odległością słów kodowych kodu K nazywamy liczbę

( )

d

d u v

u v K
u v

=

∈

≠

,

min

,

,

liczba d nazywana jest również minimalną odległością kodu K

Tw. Minimalna odległość kodu K jest równa minimalnej wadze słowa kodowego v, gdzie

v

K

∈ i v ≠ 0

( )

d

w v

v K
v

=

∈

≠

min

0

Tw.

W kodzie liniowym spełniona jest nierówność d

n

k

≤ − +1

Przykład.

(

)

v

= 10111

(

)

v'

= 11101

(

) (

) (

)

v

v

e

v

'

'

=

+

=

10111

01010

11101

Tw. Jeżeli znamy wektor błędów e to możemy ustalić wektor v na podstawie odebranego
wektora v’, a mianowicie: v v e

= +

'

Przykład.

(

)

v'

= 11101

(

)

e

= 01010

(

)

v

= 10111

• Opis kodu za pomocą macierzy

Zauważmy, że kod liniowy (podprzestrzeń

( )

GF

n

2 ) jest jednoznacznie określony przez

macierz złożoną z wektorów tworzących podprzestrzeń. Macierz tę nazywamy macierzą
generującą kod liniowy, oznaczoną literą G.

Przykład. n

= 5 , k = 5 ,

( )

GF

5

2 zawiera 2

5

wektorów

G

=

⎡

⎣

⎢

⎢

⎢

⎤

⎦

⎥

⎥

⎥

1
0
0

0
1
0

0
0
1

1
0
1

1
1
0

Macierz generującą można przekształcić zamieniając kolumny i zastępując niektóre wiersze
kombinacjami liniowymi.

Przykład.

G'

=

⎡

⎣

⎢

⎢

⎢

⎤

⎦

⎥

⎥

⎥

1
1
0

0
1
0

0
0
1

1
0
1

1
0
0

G''

=

⎡

⎣

⎢

⎢

⎢

⎤

⎦

⎥

⎥

⎥

0
1
0

1
1
0

0
0
1

1
0
1

1
0
0

Kody generowane przez tak przekształcone macierze nazywamy kodami równoważnymi.

Mówimy, że macierz G generująca kod K jest macierzą w postaci kanonicznej jeżeli:

[

]

(

)

[

]

[

]

G

I

P

k k

k

n k

=

×

× −

M

i macierz z przykładu jest w postaci kanonicznej.

Skoro kod K jest podprzestrzenią przestrzeni

( )

GF

n

2 zatem istnieje podprzestrzeń, która jest

ortogonalnym dopełnieniem przestrzeni K. Oznaczamy ją przez K

⊥

. K

⊥

jest kodem liniowym

(bo każda podprzestrzeń

( )

GF

n

2 jest kodem liniowym)

Kody K i K

⊥

nazywamy kodami dualnymi

Niech H będzie macierzą generującą kod K

⊥

.

Zauważmy, że jeżeli K jest kodem (n, k) to K

⊥

jest kodem (n, n-k). Zatem macierz H ma

rozmiar

(

)

[

]

n

k

n

−

× . Wynika stąd, że:

v H

T

⋅

= 0 (wektor zerowy o długości n-k) Á v ∈K

i G H

T

⋅

= 0 (macierz zerowa)

Tw. Macierz

H generującą kod dualny K

⊥

nazywamy macierzą kontrolną kodu K i

odwrotnie: macierz G nazywać będziemy macierzą kontrolną kodu K

⊥

.

Tw. Jeżeli macierz G jest w postaci kanonicznej, to

(

)

[

]

(

) (

)

[

]

[

]

H

P

I

n k

k

n k

n k

=

− ×

− × −

M

Dowód:

G H

T

⋅

= 0,

[ ]

G H

I P

P

I

P

P

T

⋅

=

×

⎡

⎣

⎢

⎢

⎢

⎤

⎦

⎥

⎥

⎥

= + =

M

L

0

Przykład.

G

=

⎡

⎣

⎢

⎢

⎢

⎤

⎦

⎥

⎥

⎥

1
0
0

0
1
0

0
0
1

1
0
1

1
1
0

M
M
M

H

=

⎡
⎣

⎢

⎤
⎦

⎥

1
1

0
1

1
0

1
0

0
1

M
M

H

T

=

⎡

⎣

⎢

⎢

⎢

⎢

⎢

⎢

⎢

⎤

⎦

⎥

⎥

⎥

⎥

⎥

⎥

⎥

1

1

0

1

1

0

1

0

0

1

L L

G H

T

⋅

=

⎡

⎣

⎢

⎢

⎢

⎤

⎦

⎥

⎥

⎥

+

⎡

⎣

⎢

⎢

⎢

⎤

⎦

⎥

⎥

⎥

=

+

+

+

+

+

+

⎡

⎣

⎢

⎢

⎢

⎤

⎦

⎥

⎥

⎥

=

1 1
0 1
1 0

1 1
0 1
1 0

1 1 1 1

0 0 1 1

1 1 0 0

0

Kodowanie i dekodowanie

G

, H ,

( )

n k

,

2

k

- wiadomość

v

K

∈ , v

i

- część informacyjna

Elegancka metoda kodowania

v

v G

i

= ⋅

( )

w

GF

n

∈

2

i sprawdzanie:

w H

T

⋅

= 0 to w K

∈ , w v

=

w H

T

⋅

≠ 0 to

przyjmujermy,

że nadane zostało słowo kodowe najblizsze odebranemu

ciągowi w (czyli v, jak dobrze przygotowany ciąg liczy się odległość i trzeba policzyć do
każdego ale w praktyce: )

Przykład.

(

) (

)

w k

,

,

= 100 50

słów

( )

2

2

10

10

50

10 5

35

15

⋅

≈

=

, czyli po stwierdzeniu, że to nie jest słowo kodowe to

porównanie jest potężnie złożone, ale jest bardziej racjonalna metoda (UNIWERSALNA)

Niech v

v v

v

k

1

2

3

2

0

= , , ,...,

będą słowami kodowymi kodu

( )

n k

,

( )

GF

n

2 2

n

wektorów i to

możemy rozwiązać, bo może się pojawić któryś z nich:
// l

n

- wektor o długości l zawierający jedynkę na n-tej pozycji

1 warstwa

v

1

0

=

v

2

v

3

...

v

k

2

2 warstwa

0

1

+ l

v

2

+ l

1

v

3

+ l

1

v

k

2

+ l

1

3 warstwa

0

2

+ l

v

2

+ l

2

v

3

+ l

2

v

k

2

+ l

2

//żaden z tych ciągów nie jest równy poprzedniemu, bo jedynka na innej pozycji, jak się

skończy to 2 jedynki i znów na innej pozycji i tych warstw będzie: //

2

n k

−

warstwa

0

2

1

+

−

−

l

n k

v

2

+

−

−

l

n k

2

1

v

3

+

−

−

l

n k

2

1

v

k

2

+

−

−

l

n k

2

1

//nowa warstwa będzie już powtórzeniem, ta tablica 2

n k

−

warst zawiera wszystkie wektory

przestrzeni

( )

GF

n

2 //

Iloczyn s v H

T

= ⋅

, gdzie

( )

v

GF

n

∈

2 nazywamy syndromem błędów (wskaźnikiem błędów)

Zauważmy, że jeżeli ciągi v i v' należą do tej samej warstwy to syndromy błędów dla tych
ciągów są sobie równe

Wprowadzenie do kryptografii

M - tekst jawny

C

- tekst niejawny

E - algorytm szyfrowania
D - klucz szyfrowania

k

E - przekształcenie szyfrujące

k

D przekształcenie deszyfrujące

( )

M

E

C

k

=

( )

( )

(

)

M

E

D

C

D

M

k

k

k

=

=

M

C

M

k

E

k

D

M

C

M

k

E

k

D

1.

- poufność danych

2.

- autentyczność danych

( )

(

)

( )

(

)

M

D

E

M

E

D

M

k

k

k

k

=

=

Szyfr - sposób zapisania danych taki, aby był on utajniony

Szyfry dzielimy na:
• przestawieniowe
• podstawieniowe

Przestawieniowe (zmiany pozycji poszczególnych znaków)
• sztachetowe
• macierzowe albo tablicowe, kolumnowe

Przykład: KRYPTOGRAFIA
1) zapisujemy w postaci tablicy

[

]

2

3

×

←

parametr

⎥

⎥

⎦

⎤

⎢

⎢

⎣

⎡

⎥

⎥

⎦

⎤

⎢

⎢

⎣

⎡

A

I

F

A

R

G

O

T

P

Y

R

K

2) odczytujemy kolumnami KYTRPOGAIRFA

Klucz może być w postaci

[

]

1

,

2

,

2

3

×

, gdzie cyfry następujące po wymiarze tablicy są

kolejnością czytania kolumn

• permutacyjne

f: X

→

X

i = (123)
f(i) = (231)
KRY PTO GRA FIA

→

RYK TOP RAG IAF

Podstawieniowe
• 1 - 1 monoalfabetyczne
• 1 - n
• m - n poligramowe

a) ABCDEFGHIJKLMNOPQRSTUWXYZ //Cezara k=2
np. BAL

⇒

DCN

//zmodyfikowany Cezar
SZYFRABCDEG...
SZYFR to klucz, musi być jednoznaczny

//uogólniony i trudniejszy
1.

( ) (

)

n

k

a

a

f

mod

+

=

, gdzie a - numer litery, n - liczba liter

wyrażenie deszyfrujące ma postać:

( )

( ) (

)

n

k

c

c

f

mod

1

−

=

−

2.

( ) (

)

n

k

a

a

f

mod

⋅

=

, gdy

( )

1

,

=

n

k

NWD

wtedy jednoznacznie

wyrażenie deszyfrujące ma postać:

( )

( )

(

)

n

k

c

c

f

mod

1

1

−

−

⋅

=

Arytmetyka modularna (resztowa)

Liczby całkowite a i b nazywamy liczbami kongruentnymi (przystającymi) według modulo n
(całkowite)

⇔

n jest dzielnikiem (a - b)

Zapisujemy to: a

b

n

≡

lub

(

)

a

b

m

≡ mod

Liczbę b nazywamy residium liczby a mod n i odwrotnie.

Zbiór liczb całkowitych

{

}

r r

r

n

1

2

, ,...,

nazywamy zupełnym zbiorem residiów modulo n

(względem modulo n)

⇔

dla dowolnej liczby całkowitej a istnieje w tym zbiorze dokładnie

jedna liczba r

i

, taka, że a

r

n

i

≡

.

W szczególności zbiór

{

}

01

1

, ,..., n

− jest zbiorem zupełnym residiów modulo n.

Jeśli przyjmiemy przedział [0, n-1] jako zbiór zupełny residów to piszemy:

r

a

n

i

= mod .

Jeżeli ograniczymy się do zbioru liczb całkowitych dodatnich, to residium liczby a jest reszta
z dzielenia tej liczby przez moduł n.

Dane są liczby a i n.

Operację wyznaczania residium modulo n liczby a nazywamy redukcją liczby a modulo n

Operacja redukcji liczb (ze zbioru) z pierścienia liczb całkowitych (można wykazać, że zbiór
liczb zredukowanych z operacjami

+ − ⋅

, , jest pierścieniem przemiennym) w pierścień liczb

całkowitych modulo n jest przekształceniem homomorficznym, czyli dla dowolnych liczb
całkowitych a i b i dowolnej operacji

{

}

⊗ ∈ + − ⋅

, , mamy równość:

(

)

(

) (

)

[

]

a

b

n

a

n

b

n

n

⊗

=

⊗

mod

mod

mod

mod

Przykład:
n = 9

356947 7

-154715 -5

2 2

Zredukowanym zbiorem rezidiów modulo n nazywamy podzbiór zbioru {0,1,..., n-1}
zawierający liczby względnie pierwsze z n.

Przykład:
n = 10 {1,3,7,9} - residium zredukowane, {0,...,9} - rezydium zupełne
n = 12 {1,5,7,11}

Liczbę elementów zredukowanych zbiorów rezidiów modulo n określa tzw. Funkcja Eulera
Φ(n).

Jeżeli n

p

p

p

e

e

k

e

k

=

⋅

⋅ ⋅

1

2

1

2

...

, to

( )

(

)

Φ n

p

p

i

e

i

i

k

i

=

⋅

−

−

=

∏

1

1

1 .

Operacja odwrotna do mnożenia istnieje wtedy i tylko wtedy, gdy dla kazdej liczby a istnieje
liczba a

−1

taka, że:

a a

n

⋅

=

−1

1

mod

Twierdzenie Fermata. Jeżeli

( )

NWD ,

a p

= 1

, gdzie p - liczba pierwsza to a

p

p

mod

= 1.

Twierdzenie Eulera. Jeżeli

( )

NWD ,

a n

= 1, to

( )

a

n

n

Φ

mod

= 1

Wynika stad, że:

( )

a a

n

n

⋅

=

−

Φ

1

1

mod

, a więc

( )

a

a

n

n

−

−

=

1

1

Φ

mod

Czyli jak mamy pierścień, gdzie wszystkie wzajemnie pierwsze to każda ma odwrotną i staje
się ten zbiór ciałem.

Liczby naturalne m m

m

n

1

2

,

,...

są względnie pierwsze, jeżeli

(

)

NWD

,

,...,

m m

m

n

1

2

1

=

. Sa one

parami względne jeżeli

(

)

NWD

,

m m

i

j

= 1 dla każdej pary liczb i, j spełniającej

1

≤ < ≤

i

j

n .

Algorytm Euklidesa:

Dane są dwie liczby m m

N

1

2

,

∈ , gdzie m

m

1

2

≥

. Jeżeli m

2

jest dzielnikiem m

1

, to

(

)

NWD

,

m m

m

1

2

2

=

. Jeżeli m

2

nie jest dzielnikiem m

1

, to wykonujemy dzielenie z resztą m

1

przez m

2

. Niech q

2

będzie ilorazem, a m

3

- resztą z tego dzielenia. Mamy więc

m

q m

m

1

2

2

3

=

+

, gdzie m

m

3

2

<

. Jeżeli

m m

3

2

( m

3

jest dzielnikiem m

2

), to

(

)

NWD

,

m m

m

1

2

3

=

.

Jeżeli m

3

nie jest dzielnikiem m

2

, to wykonujemy dzielenie z resztą m

2

przez m

3

. Niech

q

3

będzie ilorazem, a m

4

- resztą z tego dzielenia, tzn m

q m

m

2

3

3

4

=

+

, gdzie m

m

4

3

<

.

Postępując analogicznie w dalszym ciągu otrzymujemy ciąg skończony m m m

m

m

n

n

1

2

3

1

,

,

,...,

,

−

,

w którym m

m

m

m

n

n

1

2

1

>

> >

>

−

...

, m m

2

1

/| , m m

3

2

/|

, ..., m

m

n

n

−

−

/

1

2

|

oraz m m

n

n

|

−1

. Wtedy

(

)

NWD

,

m m

m

n

1

2

=

.

Algorytm szybkiego potęgowania modularnego

Algorytm ten pozwala na obliczenie działania: a

n

b

mod , gdzie wszystkie liczby są liczbami

całkowitymi (a oraz b nieujemne a n dodatnie).

1. d

← 1

2. niech

b b

b

k

k

,

,...,

−1

0

będzie binarną reprezentacją b

3. for i

← k downto 0

4. do d

← (d·d) mod n

5.

if

b

i

= 1

6.

then d

← (a·d) mod n

7. return d

Algorytm RSA (Rivesta, Shamira i Adelmana)

Klucze jawny i tajny szyfru RSA są funkcjami pary dużych liczb pierwszych. W celu
wygenerowania kluczy odbiorca kryptogramu losuje dwie liczby pierwsze p i q oraz liczbę e.
Iloczyn n = pq oraz e stanowią publiczny klucz szyfrujący. Liczba e musi być względnie
pierwsza z funkcją Eulera

( )

ϕ

n

. Spełnione są więc zależności:

n

p q

= ⋅

( )

(

)(

)

ϕ

n

p

q

=

−

−

1

1

( )

(

)

NWD ,

e

n

ϕ

= 1

Do przeprowadzenia szyfrowania i deszyfrowania potrzebne są dwie takie pary:

( )

e d

,

oraz

(

)

e d

', ' , gdzie e wybieramy losowo (pamiętając o tym, że ma być względnie

pierwsza z

( )

ϕ

n

), natomiast d liczymy ze wzorów:

( )

(

)

( )

d

e

n

n

=

−

ϕ ϕ

ϕ

1

mod

(

)( )

(

)

(

)(

)

d

e

p

q

p

q

=

−

−

−

− −

ϕ

1

1

1

1

1

mod

Wiadomość zaszyfrowaną liczy się następująco:

(

)

C

M

n

n

d

e

=

mod

mod

'

Proces deszyfrowania przebiega bardzo podobnie:

(

)

M

C

n

n

d

e

=

'

mod

mod

Algorytm Pohliga-Hellmana

[

]

M

p

∈

−

0

1

,

C

M

p

e

=

mod M

C

p

d

=

mod

n

p

p

p

a

a

k

a

k

=

⋅

⋅ ⋅

1

2

1

2

...

( )

(

)

Φ n

p

p

i

a

i

k

i

i

=

−

−

=

∏

1

1

1

( )

Φ p

p

= −1

( )

e d

n

⋅

=

mod

Φ

1

( )

(

)

( )

d

e

n

n

=

−

ϕ ϕ

ϕ

1

mod

Algorytm Merklego-Hellmana

Klucz tajny jest generowany za pomocą generatora liczb losowych i zawiera ciąg
superrosnący (tzn. elementy tego ciągu są tak wybrane aby każdy element był większy od
sumy poprzedzajacych go elementów) oraz liczbę pierwszą u i liczbę losową w .

Klucz tajny: A

a

a

a

n

' ( ', ',..., ' )

=

1

2

Liczby u i w spełniają zależności:

u

a

i

i

n

>

=

∑

'

1

,

1

< <

w

u .

Dla liczby w liczbę odwrotną w

−1

oblicza się z zależności:

w w

u

⋅

=

−1

1

mod

Elementy klucza jawnego obliczane są z zależności:

a

a w

u

i

i

= ' mod

Szyfr Merklego - Hellmana jest szyfrem blokowym, szyfrującym ciągi binarne. Ciag
informacyjny m m

1

2

,

,... dzieli się na bloki

(

)

M

m m

m

n

=

1

2

,

,...,

, zawierajace po n bitów.

Szyfrowanie bloku odbywa się z udziałem klucza jawnego A według wzoru: C

a m

i

i

i

=

∑

.

W procesie deszyfrowania wykorzystuje się klucz tajny. Podczas deszyfracji najpierw oblicza
się C'

C

Cw

u

'

mod

=

−1

1)

Przygotowanie do szyfrowania

• Ustalamy ciąg superrosnący A

a

a

a

n

' ( ', ',..., ' )

=

1

2

• Ustalamy liczbę u

a

i

i

n

>

=

∑

'

1

• Wybieramy liczbę w względnie pierwszą z u
• Obliczamy w

u

−1

mod

• Przekształcamy wektor A' w wektor A : A w A

= ⋅ ' , czyli a

w a

u

i

i

= ⋅ ' mod

2)

Szyfrowanie

• C A M

= ⋅

, czyli C

a m

i

i

i

n

=

=

∑

1

3)

Deszyfrowanie

• A w A

u

'

mod

=

−1

• C w C

u

'

mod

=

−1

, gdzie C

A M

'

'

= ⋅

• Wyznaczamy M znajac A' i C'