Rozdział Elementy teorii złożoności



Pobieranie 1,74 Mb.
Strona4/19
Data23.02.2018
Rozmiar1,74 Mb.
1   2   3   4   5   6   7   8   9   ...   19

Pomimo tych niepewności i zastrzeżeń znaleziono funkcje, co do których zachodzi podejrzenie, że są jednokierunkowe oraz które mają praktyczne zastosowanie w kryptografii. Dwa przykłady takich funkcji podane zostaną w dalszej części niniejszej pracy w trakcie omawiania konkretnych protokołów szyfrujących.












  1. Rozdział 2

  2. Elementy algebry i teorii liczb




          1. Algorytm Euklidesa

Często stosowanym narzędziem w niniejszej pracy będzie rozszerzony algorytm Euklidesa, który dla liczb całkowitych dodatnich a i b oblicza d = (a, b) – największy wspólny dzielnik liczb a i b oraz wyznacza takie liczby całkowite u i v, że d = ua + vb.


Niech ba. Najpierw wykonujemy następujące obliczenia:
a = q0b + r1, 0 < r1 <b,

b = q1r1 + r2, 0 < r2 <r1,

r1 = q2r2 + r3, 0 < r3 <r2,

...................., ...........,



rj1 = qjrj + rj+1, 0 < rj+1 < rj,

...................., ............,



rk2 = qk1rk1 + rk, 0 < rk < rk1,

rk1 = qkrk + rk+1, 0 < rk+1 < rk,

rk = qk+1rk+1,
gdzie rk+1 = d, a następnie wyliczamy:
d = rk+1

= rk1qkrk

= vkrk + uk1rk1 vk:= –qk, uk1:= 1,

= vk1rk1 + uk2rk2 vk1:= uk1 qk1vk, uk2:= vk,

............................., ...........................................,

= vjrj + uj1rj1 vj:= ujqjvj+1, uj1:= vj+1,

............................, ...........................................,

= v1r1 + u0b v1:= u1q1v2, u0:= v2,

= vb + ua. v:= u0q0v1, u:= v1.
Złożoność czasową rozszerzonego algorytmu Euklidesa można wyrazić przez O(ln2 a).

  1. Definicja 2.1


Niech a, b będą dodatnimi liczbami całkowitymi. Jeżeli (a, b) = 1 to a i b nazywamy liczbami względnie pierwszymi.

          1. Rozkład kanoniczny liczb naturalnych

Jedną z ważniejszych własności liczb naturalnych jest możliwość jednoznacznego przedstawienia ich w postaci iloczynu czynników pierwszych. W niniejszej pracy własność ta będzie bardzo często wykorzystywana.


Twierdzenie 2.1 (o rozkładzie na czynniki pierwsze)

Każdą liczbę naturalną złożoną można jednoznacznie przedstawić w postaci iloczynu liczb pierwszych z dokładnością do porządku czynników.


Dowód

„Istnienie”

Niech n będzie liczbą naturalną i złożoną, więc istnieje najmniejsza liczba naturalna p1 taka, że p1|n. Oczywiście p1 musi być liczbą pierwszą. Otrzymujemy więc n = p1n1. Jeżeli n1 jest liczbą pierwszą to dowód twierdzenia jest zakończony. Jeżeli n1 jest złożona, to powtarzamy powyższe rozumowanie aż do otrzymania pełnego rozkładu.

„Jednoznaczność”

Załóżmy nie wprost, że mN jest najmniejszą liczbą, która ma dwa istotnie różne rozkłady tzn.: m = p1p2...ps = q1q2...qt oraz piqj­ dla 1  is i 1 jt.

Niech q1 > p1, wtedy:



m > (q1p1)q2…qt = q12…qtp1q2q3...qt = p1p2...psp1q2q3...qt = p1(p2p2...psq2q3...qt).

Otrzymaliśmy więc dwa różne rozkłady liczby mniejszej od m, więc sprzeczność.


      1. Wniosek


Każdą liczbę nN, n > 1 można zapisać w postaci rozkładu kanonicznego, tzn.: n = p11p22...pss, gdzie dla 1  is pi są liczbami pierwszymi oraz iN.
Definicja 2.2

Funkcję : N→N, która liczbie nN przyporządkowuje ilość liczb naturalnych mniejszych od n i względnie pierwszych z n nazywamy funkcją Eulera.


Funkcja posiada między innymi następujące własności:


  1. Jeżeli p i q są liczbami pierwszymi, to:

  • (p) = p – 1,

  • (p) = p–1(p),

  • (pq) = (p)(q) = (p – 1)(q – 1).




  1. Jeżeli n = p11p22...pss, gdzie pi są pierwsze dla 1  is to:

(n) = p111(p1)p221(p2)...pss1(ps) = n.


                  1. Kongruencje


Definicja 2.3

Niech x i y będą liczbami całkowitymi oraz n > 1 będzie liczbą naturalną. Wtedy oznaczamy xy mod n, jeżeli n|xy. Relację „” nazywamy kongruencją.


Twierdzenie 2.2

Kongruencja jest relacją równoważności, tzn.:



  1. aZ aa mod n,

  2. a, bZ ab mod nba mod n,

  3. a, b, cZ (ab mod nbc mod n)  ac mod n.





1   2   3   4   5   6   7   8   9   ...   19


©operacji.org 2017
wyślij wiadomość

    Strona główna