Podstawy matematyczne i algorytmiczne

1. Półgrupa

Niech G będzie niepustym zbiorem. Gdy w zbiorze G określimy operację dwuargumentową „_°”, spełniającą prawo łączności, tzn. a_° (b_°c)=(a_° b_{) °} c dla każdego a.b.c∈G, to wówczas układ (G, _°) nazywamy półgrupą.

Półgrupę (G, _°) z wyróżnionym elementem e∈G nazywamy grupą, jeśli spełnia dodatkowe warunki:

1. a _° e = e _° a = a dla a∈G,

2. dla każdego a∈G istnieje, a'∈G, takie że a _° a` = a` _° a = e.

Jeśli ponadto dla dowolnych a,b∈G mamy a _° b = b _° a to grupę nazywamy przemienną albo abelową.

W grupie G dla dowolnego a istnieje tylko jeden element a' spełniający warunek (a); Taki element nazywamy elementem odwrotnym do a. Jeśli „_°” jest działaniem addytywnym „+”, to element odwrotny do a notujemy jako -a, a element jednostkowy e zapisujemy w postaci 0. Jeśli „_°” jest działaniem multiplikatywnym „_°”, to element odwrotny zapisujemy jako a^-1 ,natomiast e notujemy w postaci 1. W tym ostatnim przypadku zamiast pisać a_°b, piszemy a*b albo po prostu ab.

Dowód: Istnieje tylko jeden element odwrotny

a', a” - elementy odwrotne

a _° a' = a' _° a = e

a _° a” = a” _° a = e

a' = a' _° e = a' _° a _° a” = (a' _° a) _° a” = e _° a” = a” ÿ

Dowód: Istnieje element odwrotny

(a _° b) ^-1 = b^-1 _° a^-1

(a _° b) ^-1 = b^-1 _° a^-1 = a _° b _° b^-1 _° a^-1 = a _° e _° a^-1 = e ÿ

1. Podgrupa

Grupa (H, _°) jest podgrupą grupy (G, _°), jeśli H⊆G, e∈H oraz dla dowolnych a,b∈H, a_°b∈H. Jeśli H jest najmniejszą podgrupą grupy grupy G zawierającą zbiór X, to H nazywamy podgrupą generowaną przez X, a X - zbiorem generatorów podgrupy H. Jeśli X jest jednoelementowy, X={a}, to grupę generowaną przez ten zbiór nazywamy cykliczną i niekiedy oznaczamy jako (a).

Dla elementu a∈G potęgę aⁿ o dowolnym wykładniku całkowitym n określamy następująco a⁰ = 1 i indukcyjnie aⁿ = aa^n-1 dla n≥1. Ponadto a^-n = (aⁿ)^-1 dla n≥1.

Jeśli G=(a) jest grupą cykliczną z działaniem multiplikatywnym, to G={aⁿ | n∈Z}. Co do grupy (Z, _°), to możemy wykazać, że każda jej podgrupa jest cykliczna.

Układ (R,+,*,0,1) nazywamy pierścieniem (przemiennym z jedynką), jeśli:

1. (R,+) jest grupą przemienną,

2. dla dowolnego a,b,c∈R

• ab=ba

• a(bc)=(ab)c

• a1=1a=a

• a(b+c)=ab+ac, (a+b)c=ac+bc.

Jeśli nie będzie prowadzić to do nieporozumień, to zamiast (R,+,*,0,1) będziemy po prostu pisać R.

Ciałem nazywamy pierścień(przemienny z jedynką), w którym 0≠1 i każdy elemnt różny od zera jest odwracalny.

1. Problem generowania elementu pierwotnego (wg normy ANSI X9.12)

Będziemy wybierali element g (el. pierwotny). Generuje on podgrupę q-elementową grupy multiplikatywnej GF(p) (p - liczba pierwsza, GF - Galois Field). Element g jest więc rzędu q. Oprócz tego q|p-1.

Algorytm:

Wejście: p,q

Wyjście: generator (el. pierwotny) rzędu q.

Metoda:

1. j:=(p-1)/q

2. Przyjmij g równe dowolnej liczbie naturalnej 1<g<p-1 różne od dotychczas przebadanych.

3. g:=g ^j mod p

4. if g=1 then przejdź do p-tu 2.

5. zwróć g.

Przykład:

p=7, q=3

1. j=(p-1)/q =2

2. 1<g<6

3. sprawdzamy g∈{2,3,4,5}

4. dla g=2 mamy:

2² mod 7 = 4

Wygenerujmy podgrupę grupy zadanej:

2¹ mod 7 = 2

2² mod 7 = 4

2³ mod 7 = 1 czyli H={1,2,4}

2⁴ mod 7 = 2

2⁵ mod 7 = 4

2⁶ mod 7 = 4

1. Permutacja

Permutacja zbioru A jest to jednoznaczne odwzorowanie tego zbioru na siebie.

p:A->A

Zbiór jest skończony, czyli liczność zbioru card(A)=n, czyli |A|.

Elementami zbioru A są A={0,1,...,n-1}. Permutacją jest przekształcenie p, takie, że:

0 1 ... n-1

p =

p(0) p(1) ... p(n-1)

Przykład:

0 1 2 3 0 1 2 3

p = p^-1 = p* p^-1 ≠ p^-1* p

1 3 0 2 2 0 3 1

np.:

0 1 2 3 0 1 2 3

qp = qp[2] = 1 qp[2] ≠ pq[2]

1 2 3 0 1 3 0 2

0 1 2 3 0 1 2 3

pq = pq[2] = 2

1 3 0 2 1 2 3 0

e- element jednostkowy

0 1 ... n-1

e =

0 1 ... p(n-1)

Zbiór wszystkich permutacji zbioru n-elementowego z operacją składowania permutacji tworzy grupę symetryczną S_n.

Przykłady permutacji

Założenie: A={0, 1, ..., n-1}

1. y=f_k (x) = (k+x) mod n => f ^-1_k (y) = (y-k) mod n bo f _k(f ^-1_k (x)) = (k+x-k) mod n = x.

To przekształcenie jest permutacją.

Czy to przekształcenie tworzy grupę?

Jeżeli dla każdego dowolnego przekształcenia, złożenie dwóch przekształceń, będzie miało wynik w grupie, to takie przekształcenie tworzy grupę (symetryczną).

f_k (x) = (k+x) mod n

f_k f ^-1_k (x) = [(k+k')+x] mod n = (k”+x) mod n

f ^-1_k (x) = (k'+x) mod n

2. y=f_k (x) = (k*x) mod n => f ^-1_k (y) = k^-1y mod n

To przekształcenie jest permutacją, jeśli NWD(k,n)=1.

3. Skrzynka o n wejściach i n spermutowanych wyjściach

0 1 n-1

...

...

0 1 n-1

Przykład:

WE

x₁ x₂ x₃ x₁x₂x₃ y₁y₂y ₃

0 000 000 0

1 001 100 4

2 010 010 2 0 1 2 3 4 5 6 7 3 011 110 6 => p =

4 100 001 1 0 4 2 6 1 5 3 7 5 101 101 5

y₁ y ₂ y ₃ 6 110 011 3

7 111 111 7

4. y=f_k (x) = k ⊕ x => f ^-1_k (y) = k ⊕ y ⊕ - suma mod 2 - bitowa

x

⊕ k

y

5. Algorytm stosowany w szyfrze DES - Przekształcenie Feistell'a (P_k)

A=2⁶⁴

- permutacja z punktu (4)

- permutacja identycznościowa

- permutacja z punktu (3)

W systemie DES mamy 16 różnych permutacji:

P_k⁽¹⁾ * P_k⁽²⁾ * ... * P_k⁽¹⁶⁾ = P_k

Możnaby znaleźć zamiast 16 kroków permutacji, jeden krok dający w wyniku 16-krotną permutację. Udowodniono jednak, że powyższe równanie jest sprzeczne, co dowodzi, że DES nie tworzy grupy.

6. Liczba Bluma

Liczbą Bluma nazywamy liczbę całkowitą postaci n=pq, gdzie p i q są różnymi liczbami pierwszymi, a każda kongruentna do 3 modulo 4.

p ≡ 3(mod 4) => p mod 4= 3

Niech p,q - liczby Bluma, to:

y = f(x) = x² mod n, gdzie n=pq

jest permutacją.

Przekształcenie odwrotne ma postać:

f ^-1(y) = y ^{((p-1)(q-1)+4) / 8} mod n

Dowód: f ^-1(f(x)) = x, dla liczb Bluma

f ^-1(f(x)) = f ^-1(f(x)) = f ^-1(x² mod n) = (x² mod n) ^{((p-1)(q-1)+4) / 8} mod n = x ^{2*((p-1)(q-1)+4) / 8} mod n =

= x ^{((p-1)(q-1)) / 4 +1} mod n = x ^{ϕ(n)/4 +1} mod n = (x ^ϕ(n)) ^-4* x mod n = 1^-4* x mod n = x

1. ϕ(n)=(p-1)(q-1)

2. 
   
   z zał.

p mod 3 = 4 p = 3 + k₁*4

q mod 3 = 4 q = 3 + k₂*4

k_1, k₂ ∈ N.

3. z p-tów 1 i 2 mamy:

(p-1)(q-1) = (3 + k₁*4 -1) (3 + k₂*4 -1) = (2 + 4* k₁) (2 + 4* k₂) =

= 4 + 8(k₁+k₂) + 16 k₁k₂ ∈ N ÿ

1. Kongruencje

Założenie: zbiór liczb całkowitych Z = {..., -2, -1, 0, 1, 2, ...}

Niech a,b będą liczbami całkowitymi, a n∈ N. Mówimy, że a i b przystają do siebie według modułu n (lub po prostu modulo n) i zapisujemy ten fakt w postaci a ≡ b(mod n), jeżeli n|a-b. Relację ≡ nazywamy kongruencją.

a ≡ b (mod n) n|a-b , n>0

Przykładowo 17 ≡ 8 (mod 9), 21 ≡ -6 (mod 27), -5 ≡ 9 (mod 7).

1.5.1. Własności relacji kongruencji

1. a ≡ a (mod n) - zwrotność;

2. a ≡ b (mod n) b ≡ a (mod n) - symetryczność

3. a ≡ b (mod n) i b ≡ c (mod n) ⇒ a ≡ c (mod n) - przechodność

Dowód na przechodność relacji kongruencji

1. n|a-b

2. (a-b)/n = k₁ ⇒ a-b = n*k₁

3. (b-c)/n = k₂ ⇒ b-c = n*k₂

4. Z punktów 2 i 3 mamy:

a - b + b - c = n*k₁ + n*k₂ = (k₁ + k₂)*n czyli n|a-c ÿ

Z powyższych własności wynika, że dla ustalonego n relacja kongruencji jest relacją równoważności, a więc określa podział zbioru Z na klasy równoważności zwane klasami reszt modulo n, postaci

[s] = { t ∈Z | s ≡ t (mod n)}.

Klasa [s] będzie reprezentowana przez resztę z podzielenia s przez n, zapisywaną jako s mod n. Tak więc każda klasa równoważności relacji kongruencji modulo n ma jednego i tylko jednego reprezentanta w zbiorze Z_n = {0, 1, ..., n-1}. Jest to grupa addytywna. Zbiór Z_n^*=Z_n\ {0}={0, 1, ..., n-1} tworzy grupę multiplikatywną. Jeżeli p∈P to Z_p nazywamy Ciałem Galois (GP(p) - Galois Field).

Dla ustalonego modułu n kongruencję można dodawać, odejmować i mnożyć. Jeśli a ≡ b (mod n) i c ≡ d (mod n), to:

4. a ± c ≡ b ± d (mod n) i ac ≡ bd (mod) - zatem zbiór Z_n wraz z operacjami dodawania i mnożenia tworzy pierścień przemienny z jedynką.

5. a ≡ b (mod n) => a ≡ b (mod r) dla dowolnego dzielnika r liczby n,

6. a ≡ b (mod m), a ≡ b (mod n) i NWD(m,n) => a ≡ b (mod mn).

Nie każdy element zbioru Z_n ma element odwrotnny ze względu na mnożenie. Odwrotności istnieją tylko dla elementów względnie pierwszych z n. Innymi słowy, jeśli NWD(a,n)=1, to istnieje takie b, że ab ≡ 1 (mod n). Wynika stąd następna własność relacji kongruencji:

7. jeśli a ≡ b(mod n) i c ≡ d(mod n), a ponadto NWD(c,n) ≡1 (w tym przypadku także NWD(d,n)=1), to ac^-1 ≡ bd^-1(mod n), przy czym c^-1 i d^-1 oznaczają liczby całkowite odwrotne ze względu na mnożenie, odpowiednio, do c i d.

Z powyższego wynika, że pierścień Z_n jest ciałem gdy n jest liczbą pierwszą.

Kongruencji nie można dzielić stronami, lecz

8. jeśli d jest wspólnym dzielnikiem liczb a,b,n, to z kongruencji a ≡ b (mod n) wynika kongruencja a/d ≡ b/d (mod n/d)

1. Twierdzenie Eulera-Fermata

Dla każdego a∈Z_n

a^ϕ(n) ≡ 1 (mod n)

Funkcją Eulera nazywamy funkcję ϕ:N->N, taką, że ϕ(n) jest liczbą mniejszą od n i względnie pierwszą z n.

ϕ(n) = card({b | 0≤b≤n i NWD(b,n)=1}).

Własności funkcji Eulera:

1. ϕ(p) = p-1;

2. ϕ(p^a) = p^a-1 (p-1), a∈N;

3. ϕ(pq) = (p-1)(q-1);

4. jeśli n₁, n₂, n₃,..., n_t są liczbami naturalnymi, z których każde dwie są względnie pierwsze to:

ϕ(n₁, n₂, n₃,..., n_t) = ϕ(n₁)ϕ(n₂)ϕ(n₃),...,ϕ(n_t)

5. Niech m=p₁^e1 p₂^e2 ... p_r^er będzie rozkładem liczby m na czynniki pierwsze. Wówczas:

ϕ(m)=m (1- 1/p₁) (1- 1/p₂)... (1- 1/p_r)

6. Dla każdej liczby naturalnej m≥5 mamy:

ϕ(m) > m/(6 ln ln m)

Z powyższych własności funkcji Eulera wynika:

1. a^ϕ(n) ≡ 1 (mod n) => a ^p-1 ≡ 1 (mod n) => a ^p ≡ a (mod n), jeżeli p - liczba pierwsza, a∈Z_p;

2. jeśli NWD(a, n)=1 i jeśli m' jest najmniejszą nieujemną resztą m modulo ϕ(n), to

a ^m ≡ a^m'(mod n);

3. jeśli NWD(a,n)=1, to

a ^-1 ≡ a^m'(mod n);

2. Algorytny wyznaczania NWD(a,b)

1. Algorytm Euklidesa wyznaczania największego wspólnego dzielnika

Wejście: a,b∈N, a<b;

Wyjście: NWD(a,b);

Metoda:

1. Podziel b przez a; Przyjmij b=qa+r, r<a.

2. while r≠0 do

b:=a; a:=r;

podziel b przez a; przyjmij b=qa+r, r<a.

3. NWD(a,b):=a.

2. Rozszerzony algorytm Euklidesa

W algorytmie tym używany jest symbol [x], oznaczający największą liczbę całkowitą nie większą od x.

Wejście: a,b∈N; a≥b;

Wyjście: d=NWD(a,b), a także liczby całkowite x, y, spełniające równość ax+by=d;

Metoda:

1. if b=0 then

d:=0; x:=1; y:=0;

zwróć (d,x,y);

2. x₂:=1; x₁:=0; y₂:=0; y₁:=1;

3. while b>0 do

q:=[a|b];

r:=a-qb;

x:= x₂ - q x_1;

y:=y₂ - qy₁;

a:=b; b:=r; x₂:= x₁; x₁:=x; y₂:= y₁; y₁:=y;

4. d:=a; x:= x₂; y:= y₂

5. zwróć (d,x,y).

Przykład:

a=4864

b=3458

NWD(a,b)=NWD(4864, 3458)=38

Wg rozszerzonego algorytmu Euklidesa:

NWD(a,b) = 4864*32+3458*(-45) = 38

2. Chińskie twierdzenie o resztach

Jeśli liczby n₁, n₂, ... , n_k są parami względnie pierwsze to układ kongruencji

x ≡ a₁ (mod n₁)

x ≡ a₂ (mod n₂)

...

x ≡ a_k (mod n_k)

ma dokładnie jedno rozwiązanie modulo n = n₁ n₂ ... n_k.

3. Algorytm Gaussa.

Wejście: Układ kongruencji zdefiniowany w powyższym twierdzeniu.

Wyjście: Wartość x.

Metoda:

1. for i=1 to k do

S_i := n/n_i ,

T_i := S_i^-1 mod n_i.

_k

2. x := ∑ a_i S_i T_i mod n.

ⁱ⁼¹

Przykłady:

1. Stosując algorytm Gaussa dla układu kongruencji

x ≡ 3 (mod 7)

x ≡ 7 (mod 13)

otrzymujemy:

S₁ = (7*13)/7 = 13 => T₁ = 13 ^-1 mod 7 =6

S₂ = (7*13)/13 = 7 => T₂ = 7 ^-1 mod 13 = 2

Na tej podstawie x = (a₁ S₁ T₁ +a₂ S₂ T₂ ) mod n₁n_2.

Zatem:

x = (3*13*6 + 7*7*2) mod 91 = 332 mod 91 = 59

2. Obliczamy 2⁹⁵⁸⁴⁰³ mod 55. W tym celu skorzystamy z chińskiego twierdzenia o resztach i twierdzeniu Eulera-Fermata.

1. 55=5*11, zatem można zapisać układ równań

x ≡ 2⁹⁵⁸⁴⁰³ (mod 5)

x ≡ 2⁹⁵⁸⁴⁰³ (mod 11)

2. ϕ(5)=4 => 958403 = 10*95840 + 3

ϕ(11)=10 => 958403 = 4*239600 + 3

3. x ≡ 2⁹⁵⁸⁴⁰³ ≡ 2 ^{4*239600 + 3} ≡ 2^{ϕ(5)*239600 + 3} ≡ 2^ϕ(5)*239600 * 2³ ≡ 2³ ≡ 2³ (mod 5)

2³ = 3 (mod 5)

x ≡ 2⁹⁵⁸⁴⁰³ ≡ 2 ^{10*95840 + 3} ≡ 2^{ϕ(11)*239600 + 3} ≡ 2^{ϕ(11)*239600} * 2³ ≡ 2³ ≡ 2³ (mod 11)

2³ = 8 (mod 11)

4. rozwiązaniem jest x=8.

5. Potęgowanie dyskretne

Mając dany moduł n i potęgę a rozwiążemy problem obliczania dla danego x reszty x^a mod n. Metoda opisana poniżej jest potęgowaniem poprzez podnoszenie do kwadratu i mnożenie.

Istnieje algorytm wielomianowy A, który dla danych wejściowych x, a, n daje w wyniku x^a mod n.

Algorytm:

Wejście: x, a, n∈N.

Wyjście: w = x^a mod n.

Metoda:

1. Przedstaw liczbę a w postaci dwójkowej: a:= (a_ma_m-1, ..., a₀)_2.

2. w:=1;

for i:=m downto 0 do

w:=w²mod n;

if a_i =1 then w:=wx mod n.

5. Pierwiastki kwadratowe

Resztę kwadratową modulo n nazywamy takie x∈Z_n, że x ≡ y²(mod n) dla pewnego y∈Z_n. Jeśli x∈Z_n nie jest resztą kwadratową, to mówimy, że jest nieresztą kwadratową modulo n. Przyjmijmy, że p jest nieparzystą liczbą pierwszą. W Z_p dokładnie (p-1)/2 elementów jest resztami kwadratowymi i tyleż samo nieresztami kwadratowymi. Niech QR_n (odpowiednio QNR_n) będzie zbiorem wszystkich reszt (odpowiednio niereszt) kwadratowych, np. QR₇={1, 4, 2}, natomiast QNR₇={3, 5, 6}.

1.7.1. Symbol Legendre'a

Niech x∈Z i niech p>2 będzie liczbą pierwszą. Wówczas symbol Legendre'a (x|p) dla modułu p definiujemy następująco:

0 jeśli p|x

(x | p) = 1 jeśli x∈QR_p

-1 jeśli x∈QNR_p

Symbol Legendre'a służy więc do identyfikacji reszt i niereszt kwadratowych.

Własności symbolu Legendre'a:

1. (a | p) = (a mod p | p),

2. (ab | p) = (a | p) (b | p),

3. jeśli p | b, to (b² | p) =1

4. jeśli a | p, to (a | p ) ≡ a ^(p-1)/2 (mod p),

5. (1 | p) =1 i (1 | -p)=(-1) ^(p-1)/2

1 jeśli p ≡ ±1(mod 8)

6. (2 | p) = (-1) ^{(p^2-1)/8} =

-1 jeśli p ≡ ±3(mod 8)

1. Prawo wzajemności reszt kwadratowych.

Niech p, q będą dwiema nieparzystymi liczbami pierwszymi. Wówczas

-(p |q) jeśli p ≡ ±1 (mod 8)

(q | p) = (-1)^{(p-1)(q-1) / 4} (p | q) =

(p |q) jeśli p ≡ ±3 (mod 8)

Przykłady:

p=13

QR₁₃ = {1, 3, 4, 9, 10, 12}

QNR₁₃ = {2, 5, 6, 7, 8, 11}

1. Sprawdżmy, czy np. 4 rzeczywiście powinno znajdować się w zbiorze QR₁₃

4 ≡ y² (mod 13) => y=11 lub y=2

2. Obliczmy symbol Legendre'a:

(4 | 13) = (2 | 13)(2 | 13) = (2 | 13)² = -1² = 1

(3 | 13) = (13 | 3)(-1) ⁶ = (13 | 3) = (13 mod 3 | 3) = (1 | 3) = 1 (druga iteracja wykorzystuje Tw. z p-tu 1.7.2.

2. Symbol Jacobiego

Definicję symbolu Legendre'a można rozszerzyć na wszystkie nieparzyste liczby naturalne m i wszystkie x∈Z. Niech m = p₁^e1 p₂^e2...p_r^er będzie rozkładem nieparzystej liczby m>3 na czynniki pierwsze. Wówczas symbol Jacobiego (x | m) definiujemy następująco:

(x | m) = (x | p₁)^e1(x | p₂)^e2... (x | p_r)^er

Należy zauważyć, że jeżeli:

1. m jest liczbą pierwszą, to symbol Jacobiego jest symbolem Legendre'a,

2. (a | m) = 1, przy czym m jest liczbą złożoną, to m nie musi być resztą kwadratową. Np. (11 | 21) = (3 | 2)(7 | 4) = (1 | 2)(3 | 4) = (4 | 3) = (1 | 3) =1, lecz nie istnieje liczba x, taka, że x² ≡ 11 (mod 21).

Właściwości Symbolu Jacobiego:

Niech m>3 i n>3 będą nieparzystymi liczbami całkowitymi, a ponadto niech a,b∈Z.

1. ( a | m) = 0, 1, -1. Ponadto (a | m) = 0 gdy NWD(a, m) ≠ 1.

2. (ab | m) = (a | m)(b | m). Stąd jeśli a∈Z^*_n , to (a² | m)=1.

3. (a | mn) = (a | m)(a | n).

4. Jeśli a ≡ b(mod m), to (a | m) = (b | m).

5. (1 | m) =1.

6. (-1| m) = (-1)^(m-1)/2. Zatem (-1 | m) =1, jeśli n ≡ 1(mod ) i (-1| m) = -1, jeśli n ≡ 3(mod 4)

7. (2 | m) = (-1)^{(m^2-1)/8}. Stąd (2 | m) =1, jeśli n ≡ 1 lub 7 (mod 8) i (2 | m) = -1, jeśli n ≡ 3 lub 5 (mod 8).

8. (m | n) = (-1) ^(m-1)(n-1)/4 (n | m).

Przykład :

Z^*₂₁= {1, 2, ..., 20};

y	2	4	5	17	19
y^2 mod 21	4	16	4	16	4
(y | 3)	-1	1	-1	-1	1
(y | 7)	1	1	-1	-1	-1
(y | 21)	-1	1	1	1	-1

W przeciwieństwie do symbolu Legendre'a symbol Jacobiego (x | m) nie pozwala na stwierdzenie czy x jest, czy nie jest resztą kwadratową modulo m. Jest prawdą, że jeśli x∈QR_m, to (x | m) =1, Jednakże (x | m) =1 nie implikuje x∈QR_m.

2. Algorytm obliczania symbolu Jacobiego i Legendre'a

(a | n) = Jacobi (a,n).

Wejście: nieparzysta liczba całkowita n>3 i liczba naturalna a, 0≤a≤n-1.

Wyjście: symbol Jacobiego (a|n), symbol Legendre'a gdy n jest pierwsza.

Metoda:

1. if a=0 then Jacobi(a,n):=0.

2. if a=1 then Jacobi(a,n):=1.

3. Zapisz a w postaci a=2^ea₁, gdzie a₁ jest liczbą nieparzystą.

4. if e jest parzysta then t:=1 else

if n ≡ 1 lub 7(mod 8) then t:=1;

if n ≡ 3 lub 5(mod 8) then t:= -1.

5. if n ≡ 3(mod 4) i a ≡ 3(mod 4) then t:= -t;

6. n₁:=n mod a₁.

7. Jacobi(a,n):=t×Jacobi(a₁,n₁).

7. Logarytmy dyskretne

Liczbę g∈Z_n nazywamy elementem pierwotnym modulo n, jeśli Z_n^*={g, g² mod n, ... , g^ϕ(n) mod n}. Jeśli istnieje element pierwotny modulo n, to grupa Z_n^* jest cykliczna i vice versa.

Niech p będzie liczbą pierwszą, a g - elementem pierwotnym modulo p. Zatem Z_p^*={g⁰ mod n, g¹ mod n, ... , g^{p^ -2} mod n}. Dla każdego x∈ Z_p^* definiuje się logarytm dyskretny liczby x przy podstawie g jako taką liczbę m ≤ p - 2, dla której x ≡ g^m(mod p). Jeśli m jest logarytmem dyskretnym określonym w powyższy sposób, to piszemy m=log _p,g x. W poniższej tabeli przedstawiono wartości funkcji log_13,2 x.

x	1	2	3	4	5	6	7	8	9	10	11	12
log13,2 x	0	1	4	2	9	5	11	3	8	10	7	6

Łatwo z powyższej tabelki zauważyć, że QR₁₃ przyjmuje wartości parzyste. QR₁₃={1, 3, 4, 9, 10, 12}.

1. Związek pomiędzy resztą kwadratową a logarytmem dyskretnym

Niech p będzie nieparzystą liczbą pierwszą, a g - elementem pierwotnym modulo p. Wówczas dla każdego x∈Z_p

x∈QR_p log _p,g x jest liczbą parzystą.

Istotnym problemem jest zagadnienie obliczania wartości logarytmów dyskretnych. Nie jest znany algorytm wielomianowy rozwiązujący ten problem. Jednakże dla p∈P, w przypadkum gdy znany jest rozkład liczby p-1 na czynniki pierwsze, istnieje algorytm wielomianowy logarytmowania dyskretnego. W tym przypadku wykorzystuje się algorytm Pohlinga-Hellmana.

2. Twierdzenie Pohlinga-Hellmana.

Dla dowolnego wielomianu w(x) istnieje taki algorytm A, że jeśli:

1. p jest liczbą pierwszą spełniającą warunek, że wszystkie czynniki pierwsze p₁ p₂ ...p_r liczby p-1 są nie większe od w(|p|),

2. q jest elementem pierwotnym (generatorem) grupy Z_p,

3. y∈ Z_p,

to A(p, g, p₁, p₂ ...p_r, y)=log _{p, g} y. Ponadto złożoność czasowa logarytmu A jest wielomianowa w funkcji |p|.

7. Algorytmy testowania liczb pierwszych

Liczby pierwsze odgrywają szczególną rolę w kryptografii. Ze względu na to, iż liczb pierwszych jest nieskończenie wiele, użyteczne są algorytmy badania, czy dana liczba jest pierwsza. W dalszym ciągu zostaną omówione niektóre z nich.

1. Sito Eratostenesa

Technikę zwaną sitem Eratostenesa stosuje się wówczas. Gdy chcemy wyznaczyć wszystkie liczby pierwsze nie większe od danej liczby naturalnej n. Polega to na wypisaniu kolejnych liczb naturalnych od 2 do n. Pierwszą wypisaną liczbą jest 2. Pozostawiamy ją i wykreślamy wszystkie dalsze liczby podzielne przez 2, gdyż są one liczbami złożonymi. Z pozostałych najmniejszą jest 3. Jest to liczba pierwsza, zatem pozostawiamy ją i wykreślamy wszystkie liczby większe od 3 i podzielne przez 3. W ogólności po wykonaniu r-tego kroku otrzymujemy ciąg 2,3,5,7,11,13,...,p,...,n, gdzie p jest r-tą liczbą pierwszą. Można wykazać, że proces przedstawiony powyżej wystarczy wykonać do r-tego kroku, w którym p jest liczbą pierwszą spełniającą warunek p≤√n.

Mechanizmy kryptograficzne - podstawy matematyczne

1

1

---