ADS II

Bin. sčítání

• Std. algoritmus - pomalý. Bloky (0/1) - generuje, absorbuje, přenáší.
• 1.alg : určíme jednozn. kde je přenos & post. vlevo - tolik kroků, kolik je délka nejd. přenášejícího bloku. ( ∅ - log (BD), problém - komplementární čísla ).
• 2.alg (log) - ∀ blok rozdělím na 2 podbloky, spočítám A/G/P & kombinuji ( dělení jakkoliv, výběr trvá tolik kolik mám hladin - blok - log₂ ( |blok|) - celé číslo - ⌈ log₂(|celé číslo|) ⌉. - "carry-look-ahead" - ∀ bit 1 obvod & víc použití výsledků

      g1 || p1     g2 || p2 (obvody-potřeba 2
         vv           vv     dráty na 3 různé stavy)
       +-----------------+
       |                 |
       +-----------------+
           g  |   | p
              v   v
  

Diskrétní Fourierova transformace

• použití - JPEG, vzorkování signálu. předp. P_2π - stačí znát 1 periodu => vektor ( dimenze = počet vzorků / 2π ).
• FT --> kombinace const, sin kx, cos kx, DFT - netřeba vyšších násobků než n, aby se Fourierova řada shodovala fčními hodnotami v bodech x₀, .. x_n.
  
  f(x) = c + ∑₁^n/2-1 a_k sin kx + ∑₁^n/2 b_k cos kx
  
  (k:= nr + s, -n/2 < s ≤ n/2 --> sin 2π (1/n)kj = sin( 2π(nr+s)(1/n)j ) = ... = sin*cos + cos*sin = sin( 2π sj/n), cos podobně (cos*cos - sin*sin), cos 2kπ = 1, sin 2kπ = 0; cos sudá, sin lichá --> vyhodím i záporné s; sin 2π 0x = 0, cos 2π 0x = 1, sin 2π (n/2)(j/n) = 0 --> stačí n čísel.
• jednodušší počítání - v C: e^ix = cos x + i*sin x --> lin. kombinace e^{i*2π k/n}, e^{i2π n} = e⁰ - periodická - taky stačí n mocnin, nezáleží na rozmezí sumace ( -(n/2)+1...n/2 ekviv. 0...n-1 ). ω - ⁿ√ 1 = e^{2π i/n} - ω^kj - po dvojicích ortogonální vektory... tvoří bázi, ∀ vektor se dá jimi zapsat

   DFT:      
         n-1         n-1               n-1
    Aj =  ∑ αk eikxj = ∑ αk ei(2π/n)kj  = ∑ αk ωkj (O(n2))
         k=0         k=0               n=0
  
  

• spektr. rozklad - zpětná DFT - mám A_j, hledám α_k pro k = 0..n-1 - to samé: ( matice [W]_pq = ω^pq, A = W*a, a = ?, a = W^-1*A; W^-1_pq = (1/n)ω^-pq. W' : W'_pq := ω^-pq, a = (1/n)W'*A; (ω^-1)ⁿ = 1 => stejný alg.!! (někdy s odmocninami - úplně stejný výpočet)
• Důkaz:

      Wpq = ωpq, W'pq = ω-pq 
                n-1           n-1
      (W*W')pq = ∑ Wps *W'sq = ∑ ω(p-q)*s
                s=0           s=0
      p = q - ωi*(p-q) ... = ωi*0 = n.
      p ≠ q - Q := ωp-q : Q0 + ... + Qn-1 - geom. řada 
      - souč.1.n členů - a1(qn - 1)/(q - 1)
                  Qn-1+1 - 1            1 - 1
      ∑ Qj = ---------------- * Q0 =  --------- * 1 = 0  
                  Q - 1                Q - 1
      Qn = ω(p-q)*n = (ωn)(p-q) = 1p-q = 1
  

• alg - FFT (n log n) - liché & sudé sloupce (rozdělím), vyjádřím ω^k -> vše sudé:, 2. polovina řádek - mohu exponent o n snížit (vše sudé => 2.pol > n ), vyjdou stejná čísla

          n/2-1              n/2-1
    Ak  =  ∑  = a2l ω2lk + ωk ∑ a2l+1 ω2lk
          l=0                l=0
  
            n/2-1                 n/2-1
    Ak+n/2 = ∑  a2l ω2l(k+n/2) + ωk ∑ a2l+1 ω2l(k+n/2)
            l=0                  l=0
  

Hledání podřetězce

Aho-Corrasick

• 1 pattern - Knuth-Morris-Pratt
• víc patternů - Aho-Corrasick
• víc vzorů -> strom (podle dělení od zač.), λ := ""
• stav alg. = vrchol stromu. Může být víc poloh, kde se strom shoduje -> kontrola: ∀ vrchol vždy odkaz na nejdelší předponu, která je příponou slova v akt. stavu (nebo na λ) - fce "f".
• alg: posl. písmen t₁ - t_n, init: s (akt. stav alg.) := kořen:

   for i = 1 to n do { 
        while( s nemá následníka = ti && s není kořen )
            do s := f( s ); // zpětný odkaz
        if ( s má násl. = ti - "s1" ) then s:= s1;
      }
  

• trochu pomalejší než pro 1 vzor, ale lineární
• pro každý vrchol si pamatovat, jaký pattern jsem našel (i víc) ??? nebo: ∀ vrchol si pamatovat nejbližší koncový vrchol (& vracet se po nich) (jde vždy podél fce f)
• stavba fce f - po vrstvách - ∀ slova délky 1,2 ... - vždy pustit automat na suffix akt. zkoušeného slova (bez 1. znaku - (k-1)zn. celkem. Vždy se něco najde.) Pamatuju si předch. výsledky -> v lin. čase (∀ písmeno max. 2 kroky)
• lin. - skoků dozadu je ve stromě max. tolik co vpřed, těch je lineárně.

Rabin Kapp

• předp., že písmena jsou číslice, vzor porovnávám (číselně) s výsekem textu pevné délky, posouvám (jde paralelně do urč. délky)
• přepočítávání - Hornerovo schéma (pro abecedu velikosti 2^k bit-shifty) & modulo
• trik - ∀ délku hledaného možnost počítat paralelně - počítám modulo M - nutno ošetřit kolize (hashe - přepočítávání).
• w:= ( w*10 + c - b*10^l ) mod M, kde w - stav alg., c - načtené písmeno, b - 1. písmeno slova w, l - délka slova.

Třídící síť

• základ - komparátory, dají se rozčlenit do hladin, jejichž počet udává dobu výpočtu ( C* log N nejlépe, jednodušší - 1/2 log² N ( N = 2^k )).
• bitonická posloupnost - 2 monotonní úseky & cyklický posuv
• obvod:
  1. část - rekurzivně - 1/2 vstupu setřiď vzestupně, 2. sestupně
  2. část - třídí jen bitonické posl. (rozdělí biton. na 2 bitonické z větších a menších čísel, pak už rekurzivně ) - stačí jen n/2 komparátorů porvnávajících i-tý & i+(n/2)-tý prvek ( ukázat na kružnici - dojde jen k cykl. posuvu) (dá se dokázat pro posl. se 2 monotonními úseky, potom ukázat že cykl. posuv zadání způsobí jen cykl. posuv výstupu).
• počet vrstev:

      B(2) = 1, B(N) = 1 + B( N/2)   -> B(N) = log2 N
      T(N) = T(N/2) + B(N) = log N + log (N/2) + ... 
           = k + k-1 + ... = k(k+1) / 2
      T(N) = O(1/2 log2 N ). 

Konvexní obal v rovině

• ∀ 2 body: spojnice leží též v množině (obal - průnik všech konv. množin obs. body).
• v rovině mnohoúhelník, body na hranici lze cyklicky obejít
• Alg: přidávám body v pořadí podle x-osy (využívám cykl. usp.) Vezmu A (nejvíc vpravo), připojím cestu k dalšímu ( := B), vezmu bod (cykl.) po A ( := C). Změřím úhel BAC .... < 180° -> připojím výseč. jdu dál, testuji ∀ úhly, dokud nenajdu ≥ 180° & to samé na druhou stranu.
• měření úhlů - analytická geometrie - vektorový součin ( < > 180° se liší znaménkem )
• dá se dělat: pole: A[cykl.konv.obal .... (A)]B & porovnávám & vypouštím (v poli ten prostř.).
• lineární - ∀ bod - účet: +1 - přidání jako nový, porovnávání: úhel < 180° => špička úhlu + 1; > 180° - nově přidávaný bod.
• ∀ bod - +1 přidám nový, přidávám-li plochu, dostávají jiné vrcholy; po zastavení kroku - 3 (>180° na obou stranách). Bod na obvodu -> oddělení od horní & spodní části obvodu - +2 (h&s část - určeny bodem nejvíc vlevo & nejvíc vpravo), pak dál už není testován.
• tohle sice lineární, předp. ale setříděnost posl. vrcholů podle x-osy => vlastně n log n.

Voronoi diagram (konečné mn. bodů v R² )

• body := "místa", bod := ∀ bod roviny, kolem každého místa určit oblast, která je mu nejblíž & rozhraní.
• inkrementální alg. - podobný konv. obalu, půlící - rozdělí na 2 půlky, spočítá Voronoi & klikatou čáru, která 2 půlky dělí.

Sweep-line

• odspoda nahoru jdu s přímkou, body nad ní ignoruji & vyrábím křivku, pod kterou Voronoi znám (pohled 3D - šikmá rovina); křivka ~ paraboly - 1 místu může příslušet víc oblouků, průsečíky - nejblíže ≥ 2 místům => tvoří Voronoi.
• křivka - mn. bodů, co mají stejně blíko k přímce jako k nejbližšímu známemu místu.
• ∀ okamžik z pozice sweep-line & 2 míst - ohnisek parabol mohu spočítat styčné body parabol, tím i celou křivku.
• potřebuji jen hraniční body - vzniky & zániky úsečky (pro 1 úsečku - 2 polopřímky) => 2 typy událostí - místní - nově nalezený bod (vznik 2 polopř.) / kružnicová - setkání 2 parabol - vznik 1 polopř. (- setkání 2)
• místní událost - poloha sweepline - jednoduché
• kružnicová u. - v místě které leží v průsečíku 3 parabol - vždy od 3 míst ( příslušným 3 sousedním obloukům na beach-line, z nichž prostřední v okamžiku k. u. zmizí) je stejná vzd. jako od přímky => kružnice: tečna sweep-line, střed - místo zmizení oblouku. => ∀ 3 sousední oblouky zjišťuji, zda krajní oblouky paraboly vytlačí prostřední.
• kalendář událostí - místní; průběžně dopočítávám kružnicové, ∀ místní - předpočítám - zjistím, zda nevznikly nové 3 sousední vrcholy => kruž. událost; musím přepočítat ostatní - nové místo může vést ke vzniku/ zrušení jiné k.u.; k. u. - taky (vzniky/zániky oblouků parabol).
• n², rychlejší hledání vrcholů - n log n.
• užití - hledání nejbližšího místa k danému bodu (v log. čase) - vezmu styky 3 oblastí, rovinu podle nich rozdělím na pruhy, 1 pruh rozdělen do oblastí ( ∀ bod - v log. čase najde pruh & v log. čase oblast. ).

Toky v sítích

• síť - graf G; z,s - vrcholy, fce c: E(G) --> R⁺₀
• tok -

  	t: E(G) --> <0,∞), t.ž. ∀ e: 0 ≤ t(e) ≤ c(e),
  
  	∀ v ∈ V(G) z ≠ v ≠ s : ∑ t(e) = ∑ t(e)
                                 -->v      v-->
  

• přebytek toku: δ (t,v) = ∑_-->v t(e) - ∑_v--> t(e)
• velikost toku: |t| = δ(t,s)

Ford-Fulkerson

• najdu-li takovou cestu, že pro hrany ve směru od zdroje je t < c a ke zdroji t > 0, mohu zlepšit tok ( min( t(e) / c(e)-t(e)) ) - alg. opakuje takovýto krok, dokud to jde.
• Důkaz: řez A - mn. vrcholů: z ∈ A, s ∉ A. Velikost řezu = ∑_{e∈ E} c(e), kde e = (u,v), u ∈ A, v ∉ A. Velikost min. řezu ≥ max. tok ( nelze nikdy přenést víc ... ∀ řez C & tok t : δ(t,s) = δ(t,C) = δ⁺(t,C) - δ^-(t,C) ≤ |C| ).
• A := mn. { v | ze z do v vede zlepšitelná cesta }. Ve chvíli zastavení alg. je A řez., velikost stejná jako vel. toku:

          t(e) = c(e)
          -----------> && δ(v) = 0 v ≠ z => δ(z) = |A|
          <-----------
          t(e) = 0 
  

• problém - neřeší výběr => dost pomalý, může cyklit ( R \ Q )

Dinic

• vybírám nejkr. cestu ( Edmunds-Karp ); předzpr. - síť rezerv .... ∃ e(v,w) <= r := (c(v,w) - t(v,w) + t(w,v)) > 0. V síti rezerv zlepš. cesta odp. normální orientované cestě.
• zpět na tok z rezerv - BÚNO mám-li 2jici opač. hran, jednou neteče nic - tok je stejně velký - ∀ v,w: δ(v) = konst, δ(w) = konst --> neovlivní δ(z).
• rezerva: na zač. r := c.
• Fáze: vyhodí hrany, které nejsou na nejkr. cestě z --> s (2x BFS), opakuje nalezení & zprac. cesty z --> s & vyhození slepých cest, dokud ∃ cesta dané nejkr. délky z --> s.
• Fázi opakuje, dokud vůbec existuje nějaká cesta z --> s (test - BFS) v síti rezerv (jako F-F).
• fází max. n (1 fáze => nejkr. cesta se prodlouží o ≥ 1 ), BFS - O(m) (m≥n), cest v 1 fázi max. m (klesá počet hran v čisté síti) nalezení 1 cesty (jdu rovnou za nosem) - O(n), čištění - celkem max. O(m) za fázi (testuji jen hrany co vyhazuji & jejich koncové vrcholy, vyhodím max. m hran).
• Dohromady O( n² m).

Goldberg (preflow-push)

• nehledám cesty, v průběhu výpočtu není tok, ze zdroje teče vždy ≥ |max.tok|, když žádný vrchol nemá δ, dostávám (autom.max.) tok. ∀ vrchol - navíc - "výška". Preflow (vlna) - povoleny přebytky (δ); pracuje taky se sítí rezerv.
• init: h(z):= N; h(v | v ≠ z):= 0; ∀ e: t(e) := 0; ∀ v: δ(v):= 0; úvodní preflow: převede ze zdroje co se dá do přímých sousedů.
• cyklus:

   dokud ∃ v, v ≠ z, v ≠s : δ(v) > 0 : 
  	vezmi v, 
  	if( ∃ e =(v,w) nebo (w,v) : r(e)>0 (v daném směru) && h(v) ≥ h(w)){ 
  			převeď min( δ, r(e)) z v do w 
  	} 
  	else { h(v) := h(v) + 1 }.
  

• lemma1: e = (v,w), r(e) > 0 --> h(v) ≤ 1 + h(w). Po init - platí (ze zdroje - nemaj rezervu), převod toku - nejde porušit (hranám dolů rezervu jen odebírám), zvedání vrcholů - jen u vrcholů s δ > 0, vede-li z nich hrana dolů s rezevou, musím převést tok. => Tok je max. ( po zastavení tok ve výšce N, spotřebič 0 => lib. cesta překonává rozdíl (-2), taková hrana nesmí mít rezervu.
• lemma2: v ≠ z,s; δ(v) > 0 => v síti rezerv ∃ cesta v --> z. A:= {w | ∃ cesta z v do w v síti rezerv }, z ∈ A ??. Vím, že do A nic nevtéká (jinak by ∃ cesta v síti rezerv ven), vím, že δ(v) > 0. Ale ∑_{w∈ A} δ(w) ≤ 0 => z ∈ A (jiný vrchol nesmí mít δ(w) ≤ 0 ).
• ∀ v : h(v) ≤ 2N - 1. ( h(v) = 2N - 1 && δ v > 0 ) => podle L2 z v do z vede cesta tvořená hranami s kladnými rezervami, ∀ hrana podle L1 max. o 1 nahoru, hran max N - 1 => vrchol už nesmím zvednout.
• Složitost: - 3 činnosti - nasycené (δ ≥ r)/ nenasycené převední/ zvednutí vrcholu; vrchol zvednu max. 2N² - krát (celkem za všechny vrcholy) (viz výše)
• nasycené - abych přes hranu mohl opět převádět, musí mít opět kladou rezervu & vést z kopce (mezitím musím něco převést opačně, taky z kopce) => oba vrcholy musí být o ≥ 2 hladiny výš než předtím. ∀ hrana max. N-krát, celkem M*N akcí.
• nenasycené - def. fci f := ∑_{δ(v)>0,v≠z,s} h(v). Po init = 0, na konci = 0. Zvednutí vrcholu - zvedne f max. o 1, nasycené převedení zvedne max. o 2N (pokud cíl. vrchol neměl přebytek, ale teď má); nenasycené přev. vždy min. o 1 zmenší (ubude sčítanec & přibude někdy (aspoň o 1) menší ).
• přírůstky: max 2N² * 1 + 2N*(M*N) => 2 N²(M+1) max. => O(N²*M).

Teorie NP-úplnosti

Ekvivalence 3-SAT, 3-obarvitelnost, Existence nez.mny. velikosti k

• 3-SAT - norm. tvar ( a₁ || b₁ || c₁ ) && ... && ( a_k || b_k || c_k )
• 1 => 2 : gadget - 4 možnosti obarvení, vytvořím graf obarvitelný <=> je formule splnitelná.
  
  Funguje pro ∀ log. formuli - dá se převést.
• 2 => 3 : vyrobím 3 kopie grafu - 3n vrcholů, obarvím ∀ 1 barvou, odp. vrcholy spojím do trojúhelníka, hledám max. nez. množinu velikosti n.
• 3 => 1 : ∀ vrchol - proměnná x_v = 1 <=> v ∈ NezMn. Formule - ∀ hranu: (!x_v || !x_w) - tj. max. 1 z vrcholů je v nez. mn. (formálně jde převést na 3). Pomocná funkce φ(x₁, ..., x_n) je splněná <=> alespoň k proměnných = 1. (dá se napsat jednodušše: ∨_xi1..xik( xi₁ && ... && xi_k ) ( to je ale (ⁿ _k) proměnných - moc. Jde lépe (BD).
• => úlohy jsou stejně těžké. "lehká úloha" ∈ P.

Třída NP

• úlohy pro něž ex. nedeterministicky polynomiální alg. - řešení uhodnutelné/ověřitelné v polynomiálním čase (nedet. rychle uhodnu & rychle zkontroluju).
• úloha - A ⊂ {0,1}* ... množina některých posloupností 0,1 - ∀ zadání na PC na tohle převoditelné - problém: najít algoritmus, který řeší úlohu - odpovídá "Ano" <=> zadaná posl. ∈ A.
• redukce - A --> B: alg. f, vstup w∈{0,1}*, výstup f(w)∈{0,1}*, w∈ A <=> f(w)∈ B.
• polynomiální algoritmus w∈{0,1}* => výpočet se zastaví max. po P(|w|) krocích.
• A lehčí než B - ∃ polynomiální redukce A --> B. ( ∃ i opačně => stejně těžké ).
• nedeterministický algoritmus - příkaz "either/or", 1 vstup => mnoho výstupů. Přijímá vstup <=> ex. přípustný výstup "Ano". Řeší úlohu <= ( přijímá vstup <=> odpověď na úlohu je "Ano" ).

Převod na splnitelnost

• jde ∀ NP úlohu A, nedeterm. alg. α. w ∈ A, |w| = N, T(A) := M = P(N). V PC - paměť m₀ ... m_k, k = Q(M), alg. provádí kroky t₀ ... t_M => ∀ pam. buňku - M stavů - zavedu proměnné ξ_ij ( = 1 <=> t_i : m_j = 1 ). Vstup - v 1. n buňkách - ξ₀₀ = w₀ ... ξ_0n = w_n. Výstup - ξ_m0 = 1 <=> "Ano".
• práce počítače lze popsat: ∀ čas t: if( progr-čítač_t == r && r-tá instrukce == ... ) then ... . (instrukce - nedeterministická) => ∀ instr. se dá nějak popsat jako vztah proměnných ξ_tj a ξ_t+1,k. => dostanu celý popis => tolik výroků, kolik mám v PC instrukcí. ∀ vztah - 1 log. formule, další f. - zač. vstup ξ₀₀ - ξ_0n; na konci ξ_m0 = 1. => dohromady formule, kdy mohu rozhodnout, zda alg. může někdy opdovědět "Ano".

NP-úplné

• př. problém 2 loupežníků pro velká čísla
• další - prvočíselnost(složitější!) /složené číslo - není symetrická úloha: časté
• převoditelnost - transitivní
• "nejtěžší NP úlohy" - ∀ úloha z NP jde na ně převést. Problém - P ?≠ NP ?≠ NPC ( když P ≠ NP => P ∩ NPC = ∅ ), jediná nezařazená úloha - izomorfismus ( nemáme v P, ale NPC je nepravd. )
• isomorfismus dokážu ověřit rychle, neisomorfismus - náh. vyberu G₁ / G₂, zpermutuju vrcholy, nepřítel zjistí, kterého grafu je to kopie.

Neideální řešení

• Barevnost grafu (ekviv. sestavování rozvrhu - 2 hodiny neslučitelné => hrana ) - Χ(G) = ?; A(G) - počet barev, které by potřeboval alg. A. Hledám A(G) / Χ(G) ≤ 1 + c. ∀ konst. c - A(G) ≤ (2-ε) + c, ε > 0 stejně těžké jako najít opt. řešení.
• někde aproximační alg. nejsou - stejně těžké jako přesné řešení.
• Batoh - a₁ ... a_n, b ... ∃ I ⊂ {0, ..., n-1}, t.ž. ∑ w(A_i) = b? (nebo často ∑ w(A_i) < b && = max. ). Přesné pokrytí množiny X množinami A₁ ... A_m - ekvivalentní problém. Převod: ∀ prvku z X přiřadím číslo n^j ~ w_j, každé množině ∑_j∈Aiw_j. Mn. X - (chci pokrýt) := (n^m -1)/(n -1). ∃ I ⊂ {0,..,n-1}, t.ž. ∑ w(a_j) = (n^m -1)/(n-1)? Všechna čísla zapíšu v soustavě o základu n (∀ prvek - 1 číslice). Součet - max. n-1 sčítanců (případ, že všechny A_i akorát pokryjí X, vyřešit zvlášť). Chci najít mn., jejíž součet ∑_I w(A_i) = 111111....111 (m číslic).
• aprox. alg - přepsat na %: a'₀ ... a'₀ ≅ zaokrouhl. na M des. míst - neliší se o víc než (1/M), součty pak taky ne => nemusím řešit pro dlouhá čísla - stačí pro konst. počet dest. míst - znám alg. z dyn. progr.
• π_i,β - určuje, zda jsem schopen z a₀ ... a_i-1 nasčítat β. Znám π_j,β ∀ j < i. Potom π_i,β buď lze nasčítat z a₀ ... a_i-1, nebo jen z a₀ ... a_i-2 (= π_i-1,β ), pokud mám mezivýpočty v tabulce - max. n*b kroků.
• Bin-packing - 0 ≤ a, ..., a_n ≤ 1 - rozházet do krabic o velikosti 1. Alg. - First fit (≤ 1,7*min. + 4), Best fit (kde je toho nejmíň) & Worst fit (kde zbyde nejmíň) ≤ (11/9)*min; jde (1+ε)*min - PTAS

Šifrování

DES

• "digital encryption system, symetrický => klíč tajný.
• funkce F:

          /--(expanze)--> [48bit]                      /---> [32bit- OUT]
        [IN- 32bit]         |                         /
                            xor ---->[48bit]---(8 fcí (6vstupů&4výstupy))  
                            |       
                          [48bit klíč]
  

• celkem:

       [ LINP ]      [ RINP ]
          |             |
         xor<---(F)-----+
          |      |      |
          v     klíč    v
       [ ROUT ]      [ LOUT ]
  

  - 64 bit, 16 iterací (∀ prohodí levý/pravý vstup). Dešifrování - znám vstup do F, => mohu si spočítat jeho F, znám i výsl. xor-u => vím i LINP.
• f- libovolná (ale závisí na ní kvalita šifry). Měření kvality - dostanu šifr. text & zdroj, jak dlouho trvá výpočet klíče? (DES- 2⁴⁰ pro 64-bit) <-- není úplně bezpečný. Prolamování - pomocí distrib. výpočtů.

RSA

• Rivest, Shamir, Adleman - veřejný klíč pro šifrování & tajný pro dešifrování.
• 2 prvočísla p,q (tajná); n := p*q (veřejné). φ(n) = (p-1)(q-1) (tajné), E < φ(n) (nesoudělné s φ(n)!, veřejné), D: D*E = 1 mod φ(n) (tajné).
• text[m] (0 ≤ m < n) --Š--> c = m^E mod n --DŠ--> m ≡ c^D mod n.
• Důkaz: (Malá Fermatova věta: p prvočíslo, ∀ a: 0 ≤ a < p => a^p ≡ a mod p, a^p-1 - 1 mod p (a ≠0) ).
  1.) m ≡ c^D mod p: c^D ≡ (m^E)^D mod p = m^ED = m^{r*(p-1)(q-1)+1} = ( m^r(q-1))^(p-1)*m = ( m^r(q-1) mod p )^(p-1)*m = (MFV) ≡ 1*m. m ≡ c^D mod q - podobně.
  2.) m ≡ c^D mod pq => m^ED ≡ m mod n.
• bez znalosti D / p&q neznáme dešifr. alg.; problém - najít 2 prvočísla ( random vyberu & testuju - mezera mezi 2 prvočísly roste ≅ log)
• test pč. - MFV -není moc přesné (je-li málo čísel a^p-1 ≠ 1 mod p ) :
  Rabin-Miller - mám p. Vezmu p-1 := 2^s*d (d liché, dělím tak dlouho dokud nedostanu liché č.). p není pč. <=> ∃ a: a^d ≠ 1 mod p && ∀ r: a^2r*d ≠ -1 mod p. (0≤ r< s, 0≤a < p). Takovýchto a je 3/4 p => pro velký počet opak. malá pravd. chyby.