Prvni prednaska z Kodovani a sifrovani

Zaklady teorie cisel

Obsah

Zaklady teorie cisel
Prvocislo
je prirozene cislo p, ktere ma za delitele jen 1 a sebe sama. Kazde prirozene cislo n vetsi nez 1 se da jednoznacne zapsat ve tvaru n = p1^a1 * p2^a2 * ... * pn^an
Nejvetsi spolecny delitel
cisel a a b (NSD(a,b)) je nejvetsi takove cislo d, ktere deli a i b.
Nejmensi spolecny nasobek
cisel a a b (NSN(a,b)) je nejmensi takove cislo n, ktere je nasobkem a i b.
Eulerova funkce fi
udava pocet prirozenych cisel mensich nez n a nesoudelnych s n Hodnoty funkce fi pro cisla 1..1e jsou 1 1 2 2 4 2 6 4 6 4. Pro prvocislo p je fi(p)=p-1.
Kongurence
Cisla a a b nazveme kongurentni modulo m, pokud je rozdil a-b delitelny m. a a b jsou kongurentni, pokud davaji pri deleni m stejny zbytek. Kongurence lze scitat a nasobit.

Mala Fermatova veta
Tvrzeni
Pokud je p prvocislo, pak je kazdy binomicky koefincient p nad a pro 0 < a < p kongurentni s 0 modulo p. (Dukaz je zrejmy, v rozvoji binomickeho koeficientu se v citateli objevuje clen p, ktery nelze vykratit s nicim ve jmenovateli.
Tvrzeni
Pokud je p prvocislo, pak pro kazda dve cisla a a b plati (a+b)^p je kongurentni s a^p+b^p modulo p (plyne z predchoziho tvrzeni.
Mala fermatova veta
Pro kazde prvocislo p a pro kazde prirozene cislo c plati c^p je kongurentni s c modulo p. (Dukaz indukci dle c).
Jiny tvar Fermatovy vety
Pro kazde prvocislo p a pro kazde prirozene cislo c plati c^(p-1) je kongurentni s 1 modulo p.
Jeste jiny dusledek
Pokud k cislu N existuje cislo c takove, ze c^(N-1) neni kongurentni s 1 modulo N, pak je N cislo slozene. (Poznamka: obracene tvrzeni neplati, 37*73 je slozene cislo, ale splnuje MFV).

Zakladni algebraicke struktury
Grupa
Mnozina M s operaci + tvori grupu, pokud
Komutativni grupa
je grupa, kde je navic operace + komutativni.
Okruh
je mnozina M se dvema operacemi + a *, ktere splnuji nasledujici podminky:
  • - Vzhledem k operaci + je mnozina M grupou.
  • - Operace * je uzavrena, asociativni a ma jednotkovy prvek.
  • - Operace jsou navzajem distributivni.
    • Faktor okruhy celych cisel
    Na mnozina Zn={0,1,...,n-1} definujeme scitani a nasobeni modulo n. Vzhledem k teto operaci je mnozina Zn okruh. Inverzni prvek vzhledem k nasobeni existuje pro cislo a ze Zn prave tehdy, kdyz je a nesoudelne s n. Je-li n prvocilo, existuje inverzni prvek pro kazdy prvek mnoziny Zn a Zn tvori teleso.
    Eulerova veta
    Pro kazde prirozene cislo n a cislo c nesoudelne z n plati c^fi(n) je kongurentni s 1 modulo n. (je to zobecneni Male Fermatovy vety).
    Tuto stranku vytvoril Tomas Vanicek a jedna se o soucast volitelnych prednasek z Kodovani a sifrovani pro vsechny obory Stavebni fakulty Ceskeho vysokeho uceni technickeho v Praze.