Крипто 19 10

0:04

S… Speaker 1 (Крипто 19 10)

Než začneme s tou šestkou,

0:06

S… Speaker 1 (Крипто 19 10)

tak jako vždycky krátce rekapitulace té předpozí,

0:10

S… Speaker 1 (Крипто 19 10)

pětky a té páté to bylo takový zase vybraný

0:15

S… Speaker 1 (Крипто 19 10)

partie zdová matematiky,

0:16

S… Speaker 1 (Крипто 19 10)

nějaké věty a pak teorie složitosti.

0:19

S… Speaker 1 (Крипто 19 10)

Takže já zase rychlo si to projdu,

0:22

S… Speaker 1 (Крипто 19 10)

pozorním na věci,

0:23

S… Speaker 1 (Крипто 19 10)

který pomočuju za důležitý a hodné ocenky.

0:27

S… Speaker 1 (Крипто 19 10)

nebo nějaké sloušky.

0:29

S… Speaker 1 (Крипто 19 10)

V podstatě malá fermatová věta,

0:31

S… Speaker 1 (Крипто 19 10)

Eulerová věta,

0:32

S… Speaker 1 (Крипто 19 10)

čínská věta ozbících,

0:33

S… Speaker 1 (Крипто 19 10)

co jsou všechno věci,

0:34

S… Speaker 1 (Крипто 19 10)

které se používají potom dál v nějakých větlých fotografických algoritmech.

0:39

S… Speaker 1 (Крипто 19 10)

Malá fermatová věta a Eulerová věta má

0:43

S… Speaker 1 (Крипто 19 10)

jasný úsledek,

0:45

S… Speaker 1 (Крипто 19 10)

vede k tomu,

0:46

S… Speaker 1 (Крипто 19 10)

že můžete redukovat exponenty v modulární aritmetice.

0:50

S… Speaker 1 (Крипто 19 10)

A jak dneska uvidíte,

0:52

S… Speaker 1 (Крипто 19 10)

vy to mocnění...

0:54

S… Speaker 1 (Крипто 19 10)

na nějaké větší exponenty a je v té asimetrické kryptografie

0:58

S… Speaker 1 (Крипто 19 10)

extrémně častní.

0:59

S… Speaker 1 (Крипто 19 10)

Takže samozřejmě tu redukci potřebujeme.

1:04

S… Speaker 1 (Крипто 19 10)

Jsou to dvě věty,

1:07

S… Speaker 1 (Крипто 19 10)

které říkají to stejné,

1:08

S… Speaker 1 (Крипто 19 10)

akorát pro různé použití.

1:11

S… Speaker 1 (Крипто 19 10)

A ta dvlatová věta říká pro právě v moduláři

1:15

S… Speaker 1 (Крипто 19 10)

arizmetické modulo prvočíslo.

1:18

S… Speaker 1 (Крипто 19 10)

A Oliverová věta to říká pro modulo nějaké

1:22

S… Speaker 1 (Крипто 19 10)

číslo složené,

1:24

S… Speaker 1 (Крипто 19 10)

které se skládá v více pročísa.

1:26

S… Speaker 2 (Крипто 19 10)

Jsou tam nějaké důkazy?

1:28

S… Speaker 1 (Крипто 19 10)

My jsme si ukazovali minulé.

1:31

S… Speaker 1 (Крипто 19 10)

Tady je to použití,

1:33

S… Speaker 1 (Крипто 19 10)

kde základ vždycky můžete redukovat

1:37

S… Speaker 1 (Крипто 19 10)

přímo tím modulem,

1:39

S… Speaker 1 (Крипто 19 10)

takže ze 46 modulo 11 můžete udělat

1:43

S… Speaker 1 (Крипто 19 10)

dvojku a z 51 modulo

1:47

S… Speaker 1 (Крипто 19 10)

10 ne 11,

1:48

S… Speaker 1 (Крипто 19 10)

protože redukujete modulem hodnoty ojelerové funkce

1:53

S… Speaker 1 (Крипто 19 10)

z toho modula.

1:55

S… Speaker 1 (Крипто 19 10)

11 je prvo číslo,

1:56

S… Speaker 1 (Крипто 19 10)

takže hodnota ojelerové funkce je 10.

1:58

S… Speaker 1 (Крипто 19 10)

Takže bachák exponem vždycky redukujte hodnotou

2:03

S… Speaker 1 (Крипто 19 10)

ojelerové funkce z toho vašeho modula.

2:06

S… Speaker 3 (Крипто 19 10)

Takže,

2:07

S… Speaker 1 (Крипто 19 10)

pane svat, je to modulo 10,

2:08

S… Speaker 1 (Крипто 19 10)

o tom je 1.

2:09

S… Speaker 1 (Крипто 19 10)

A z paměníky počítáte 4650.

2:12

S… Speaker 4 (Крипто 19 10)

Tak,

2:16

S… Speaker 1 (Крипто 19 10)

ojelerová byte říkal úplně to stejný.

2:20

S… Speaker 1 (Крипто 19 10)

Akorát zase pro případ,

2:22

S… Speaker 1 (Крипто 19 10)

kdy tím modulem není prvočíslo,

2:24

S… Speaker 1 (Крипто 19 10)

ale číslo složené.

2:25

S… Speaker 1 (Крипто 19 10)

Třeba patnáctka je číslo složené tři krát pět ze dvou

2:29

S… Speaker 1 (Крипто 19 10)

prvočísel,

2:30

S… Speaker 1 (Крипто 19 10)

když se vypočítá hodnota ojzerové funkce ze

2:34

S… Speaker 1 (Крипто 19 10)

součinu dvou prvočísel,

2:36

S… Speaker 1 (Крипто 19 10)

a to tak,

2:37

S… Speaker 1 (Крипто 19 10)

že vezmete ty dvě prvočísla o jedničku,

2:39

S… Speaker 1 (Крипто 19 10)

jestli žijíte a vy ze sebou vydásobíte.

2:41

S… Speaker 1 (Крипто 19 10)

Takže z tři krát pět se vám stane dvakrát čtyři.

2:46

S… Speaker 1 (Крипто 19 10)

což by mělo být 8,

2:48

S… Speaker 1 (Крипто 19 10)

51 modulo 8 a

2:52

S… Speaker 1 (Крипто 19 10)

by mělo být 3.

2:53

S… Speaker 1 (Крипто 19 10)

Protože 408 asi je delitérní.

2:57

S… Speaker 1 (Крипто 19 10)

8 modulo.

3:00

S… Speaker 1 (Крипто 19 10)

Jo, takže za celou faktivy počítáte,

3:02

S… Speaker 1 (Крипто 19 10)

že 46 a 51 je 1 na třetí,

3:06

S… Speaker 1 (Крипто 19 10)

protože 46 radikujete přímo,

3:08

S… Speaker 1 (Крипто 19 10)

z toho se vám ustala nyníka.

3:09

S… Speaker 1 (Крипто 19 10)

Exponent už byste ani nepotřebovali,

3:11

S… Speaker 1 (Крипто 19 10)

protože 1 na cokoliv je 1,

3:13

S… Speaker 1 (Крипто 19 10)

ale když se můžeme mít úplný,

3:15

S… Speaker 1 (Крипто 19 10)

tak 51 modulo 8 je 3 a máte 10.

3:19

S… Speaker 1 (Крипто 19 10)

Tohle hodně důležitým deskatou můžete v druhé části,

3:23

S… Speaker 1 (Крипто 19 10)

kde budeme brát 50čkový digitální podpis.

3:28

S… Speaker 2 (Крипто 19 10)

Je to jasný,

3:29

S… Speaker 1 (Крипто 19 10)

kde můžeme jak redukovat základ a exponent?

3:32

S… Speaker 1 (Крипто 19 10)

Ano,

3:33

S… Speaker 3 (Крипто 19 10)

ne?

3:34

S… Speaker 4 (Крипто 19 10)

Ano,

3:35

S… Speaker 4 (Крипто 19 10)

super.

3:35

S… Speaker 4 (Крипто 19 10)

Tak,

3:38

S… Speaker 1 (Крипто 19 10)

tohle tady je řázka,

3:40

S… Speaker 1 (Крипто 19 10)

kdy vás vždycky ubije.

3:41

S… Speaker 2 (Крипто 19 10)

A já myslím,

3:43

S… Speaker 2 (Крипто 19 10)

vás probudit.

3:44

S… Speaker 1 (Крипто 19 10)

Číska je tam o pětcích.

3:48

S… Speaker 1 (Крипто 19 10)

To je věc,

3:49

S… Speaker 1 (Крипто 19 10)

kterou vy příjmu až tak asi nebudete potřebovat při výpočtech,

3:53

S… Speaker 1 (Крипто 19 10)

někde na papíře,

3:54

S… Speaker 1 (Крипто 19 10)

ale zase se používá téměř vždycky při implementací.

3:57

S… Speaker 1 (Крипто 19 10)

Takže když máte nějakou softwarovou knihovnu,

4:00

S… Speaker 1 (Крипто 19 10)

softwarovou implementaci,

4:02

S… Speaker 1 (Крипто 19 10)

třeba ověřování digitálního podpisu,

4:04

S… Speaker 1 (Крипто 19 10)

tak velice často je urychlená pomocí čínské věky

4:08

S… Speaker 1 (Крипто 19 10)

o zbytcí.

4:09

S… Speaker 1 (Крипто 19 10)

Takže vy finální to ověření neděláte modulo souči dvou

4:13

S… Speaker 1 (Крипто 19 10)

prvočísel a uděláte to jako mocnění dvou

4:18

S… Speaker 1 (Крипто 19 10)

rovnic modulo,

4:19

S… Speaker 1 (Крипто 19 10)

ale vždycky menší prvočíslo.

4:21

S… Speaker 1 (Крипто 19 10)

To vám to umyklí,

4:23

S… Speaker 1 (Крипто 19 10)

byť to vypadá nelogicky,

4:25

S… Speaker 1 (Крипто 19 10)

tak opravdu se to používá.

4:29

S… Speaker 1 (Крипто 19 10)

Takže tady jsme si říkali,

4:30

S… Speaker 1 (Крипто 19 10)

jak to funguje,

4:32

S… Speaker 1 (Крипто 19 10)

že to vlastně slouží k tomu,

4:34

S… Speaker 1 (Крипто 19 10)

abyste byli schopni vyřešit soustavu konkurencí.

4:38

S… Speaker 1 (Крипто 19 10)

My se v tomto kurzu budeme zabývat soustavami jenom o dvou,

4:42

S… Speaker 1 (Крипто 19 10)

maximálně třech konkurencí.

4:45

S… Speaker 1 (Крипто 19 10)

Takže maximálně to bude tak,

4:47

S… Speaker 1 (Крипто 19 10)

jak je to teď tady.

4:48

S… Speaker 1 (Крипто 19 10)

Budete i nějaké x je konkurencí z A1,

4:50

S… Speaker 1 (Крипто 19 10)

x je A2,

4:51

S… Speaker 1 (Крипто 19 10)

x je z A3 a vždycky je to v jiném modulu.

4:54

S… Speaker 1 (Крипто 19 10)

Ty moduly jsou už zájemně nesoudělné,

4:56

S… Speaker 1 (Крипто 19 10)

to znamená jich největší společný teritorií.

5:00

S… Speaker 1 (Крипто 19 10)

Neexistuje v tomu nějaký postup,

5:02

S… Speaker 1 (Крипто 19 10)

jak vyřešit konkurenci,

5:03

S… Speaker 1 (Крипто 19 10)

a to je přesně tady tento vzoreček,

5:06

S… Speaker 1 (Крипто 19 10)

který se musíte naučit,

5:08

S… Speaker 1 (Крипто 19 10)

abyste byli vstupnit ten příklad potom vypočítat.

5:11

S… Speaker 1 (Крипто 19 10)

Je poměrně jednoduchý,

5:13

S… Speaker 1 (Крипто 19 10)

podle toho, kolik je tam těch konkurencí,

5:15

S… Speaker 1 (Крипто 19 10)

tak tolik je tam sum nebo tolik je tam součtu.

5:19

S… Speaker 1 (Крипто 19 10)

A když máte soustranu třech konkurenci,

5:22

S… Speaker 1 (Крипто 19 10)

jako jsme měli na tom předchozím slajdu,

5:23

S… Speaker 1 (Крипто 19 10)

tak tady budou třikrát sečtětné.

5:27

S… Speaker 1 (Крипто 19 10)

Tady tyto součiny.

5:28

S… Speaker 1 (Крипто 19 10)

A v součinu je vždycky A,

5:30

S… Speaker 1 (Крипто 19 10)

to je to čisto,

5:31

S… Speaker 1 (Крипто 19 10)

který máte v zadání.

5:33

S… Speaker 1 (Крипто 19 10)

M to vypočítáte jako velký modulus,

5:36

S… Speaker 1 (Крипто 19 10)

součin všech modulů nomeno ten aktuální malý modulus a L

5:41

S… Speaker 1 (Крипто 19 10)

je fitverzní krovek M.

5:43

S… Speaker 1 (Крипто 19 10)

V modulární aritmetice modulo ten

5:47

S… Speaker 1 (Крипто 19 10)

malý modulus.

5:48

S… Speaker 1 (Крипто 19 10)

Není na tom nic složitý,

5:51

S… Speaker 1 (Крипто 19 10)

jenom jestli to potřebujeme.

5:54

S… Speaker 1 (Крипто 19 10)

A pak jsme schopni řešit,

5:56

S… Speaker 1 (Крипто 19 10)

vlastně jsou to soustavy rovnic v modulární aritmetice.

6:00

S… Speaker 1 (Крипто 19 10)

Tady nějaký příklad,

6:03

S… Speaker 1 (Крипто 19 10)

můžete se řeknulovat tady,

6:06

S… Speaker 1 (Крипто 19 10)

kde se to potom používá,

6:07

S… Speaker 1 (Крипто 19 10)

to už je mimo,

6:08

S… Speaker 1 (Крипто 19 10)

my to nemůžeme tady v tom RSAčku dělat,

6:11

S… Speaker 1 (Крипто 19 10)

protože neznáme Gardner algoritmus a budeme

6:15

S… Speaker 1 (Крипто 19 10)

spolíhat na to,

6:16

S… Speaker 1 (Крипто 19 10)

že někdo to naprogramoval,

6:17

S… Speaker 1 (Крипто 19 10)

že to použijeme někde v soustředě.

6:21

S… Speaker 1 (Крипто 19 10)

Tak to bylo šest z těch důležitých věc.

6:23

S… Speaker 1 (Крипто 19 10)

A pak jsme tady ještě měli nějakou takovou vybranou část

6:28

S… Speaker 1 (Крипто 19 10)

teorii složitosti.

6:30

S… Speaker 1 (Крипто 19 10)

Tam jsme mluvili o paměťové a početní složitosti.

6:34

S… Speaker 1 (Крипто 19 10)

Říkali jsme si,

6:35

S… Speaker 1 (Крипто 19 10)

že to je nějaký vztah mezi počtem nebo velitostí

6:40

S… Speaker 1 (Крипто 19 10)

vstupů a tím,

6:42

S… Speaker 1 (Крипто 19 10)

jak dlouho ten autoritmus trvá,

6:44

S… Speaker 1 (Крипто 19 10)

anebo když se zavere paměti.

6:46

S… Speaker 1 (Крипто 19 10)

Často to je přímo v nepřímé úměře.

6:50

S… Speaker 1 (Крипто 19 10)

Čím algoritmus optimalizujete na rychlost,

6:53

S… Speaker 1 (Крипто 19 10)

tím vám víc zabane paměti.

6:55

S… Speaker 1 (Крипто 19 10)

A nebo naopak,

6:57

S… Speaker 1 (Крипто 19 10)

když chcete, aby zabrát co nejdůle paměti,

6:59

S… Speaker 1 (Крипто 19 10)

tak pravděpodobně bude pomalejší.

7:01

S… Speaker 1 (Крипто 19 10)

To je jako proti sovětlivě složitosti.

7:04

S… Speaker 1 (Крипто 19 10)

V dnešní době sice paměti jsou drahý,

7:06

S… Speaker 1 (Крипто 19 10)

ale pořád ještě je pro nás asi zajímavější ta výpočetní složitost.

7:12

S… Speaker 1 (Крипто 19 10)

Ta nám říká,

7:13

S… Speaker 1 (Крипто 19 10)

jak dlouho ten algoritm poběží a v závislosti,

7:17

S… Speaker 1 (Крипто 19 10)

když mu dáte takový počet nebo takovou velikost vstupů.

7:20

S… Speaker 2 (Крипто 19 10)

Říkali jsme si,

7:23

S… Speaker 1 (Крипто 19 10)

že to jde buď to určit přesně u nějakých triviálních

7:27

S… Speaker 1 (Крипто 19 10)

algoritmů,

7:28

S… Speaker 1 (Крипто 19 10)

jako je třeba řazení čísel od nejmenšího po největší a tak podobně.

7:32

S… Speaker 1 (Крипто 19 10)

Tam to dokážete určit přesně,

7:34

S… Speaker 1 (Крипто 19 10)

ale u větších algoritmů i...

7:37

S… Speaker 1 (Крипто 19 10)

V kryptografii používáme takzvanou asymptotickou složitost,

7:42

S… Speaker 1 (Крипто 19 10)

což je nějaký odhad.

7:43

S… Speaker 1 (Крипто 19 10)

A ten odhad máme třech typů.

7:47

S… Speaker 1 (Крипто 19 10)

Omega, Omikron a Theta.

7:49

S… Speaker 1 (Крипто 19 10)

Omega je optimista,

7:52

S… Speaker 1 (Крипто 19 10)

to je nejlepší možný případ.

7:55

S… Speaker 1 (Крипто 19 10)

V reálu to rychlejší nebude.

7:57

S… Speaker 1 (Крипто 19 10)

Tohle je vždycky jako lepší.

8:00

S… Speaker 1 (Крипто 19 10)

Omikron je zase pessimista,

8:02

S… Speaker 1 (Крипто 19 10)

to je nejhorší možný případ,

8:04

S… Speaker 1 (Крипто 19 10)

co může nastat.

8:06

S… Speaker 1 (Крипто 19 10)

To je nějaký přední případ,

8:08

S… Speaker 1 (Крипто 19 10)

nějaký rozmezí,

8:09

S… Speaker 1 (Крипто 19 10)

ale v praxi to není moc použitelný,

8:11

S… Speaker 1 (Крипто 19 10)

protože je to tak široký,

8:12

S… Speaker 1 (Крипто 19 10)

že vám to moc o algoritmu neřeším.

8:14

S… Speaker 1 (Крипто 19 10)

Takže používám omegu nebo omikron.

8:18

S… Speaker 1 (Крипто 19 10)

Teď je to v zobrazení,

8:20

S… Speaker 1 (Крипто 19 10)

potom...

8:21

S… Speaker 1 (Крипто 19 10)

A můžeme to potom rozředit zase do nějakých přích

8:25

S… Speaker 1 (Крипто 19 10)

od té nejjednodušší složitosti constant až

8:29

S… Speaker 1 (Крипто 19 10)

od tu úplně největší faktoriál.

8:32

S… Speaker 1 (Крипто 19 10)

Je o toho,

8:33

S… Speaker 1 (Крипто 19 10)

že když máte nějaký počet studiň x,

8:36

S… Speaker 1 (Крипто 19 10)

tak jakou funkcí z toho x vám to poběží časovou.

8:41

S… Speaker 1 (Крипто 19 10)

To rozhraní mezi tím,

8:43

S… Speaker 1 (Крипто 19 10)

co se pouvažuje za efektivní a co příliš pomalé leží tady,

8:47

S… Speaker 1 (Крипто 19 10)

mezi exponenciální a polinomiální.

8:49

S… Speaker 1 (Крипто 19 10)

Polinomiální je pro nás dobré a všechno,

8:52

S… Speaker 1 (Крипто 19 10)

co je lepší,

8:53

S… Speaker 1 (Крипто 19 10)

a exponenciální a dolů je zase špatné.

8:57

S… Speaker 1 (Крипто 19 10)

To nespustíte prostě reálně na počítače a takový

9:01

S… Speaker 1 (Крипто 19 10)

algoritm budeme pouvažovat za nepoužitelem.

9:06

S… Speaker 2 (Крипто 19 10)

Tak,

9:07

S… Speaker 1 (Крипто 19 10)

stejně tak potom jsme měli nějaké řezení problémů,

9:11

S… Speaker 1 (Крипто 19 10)

takzvané třídy složitosti řešení problémů,

9:13

S… Speaker 1 (Крипто 19 10)

byly to třídy třída P nebo polinomiální,

9:16

S… Speaker 1 (Крипто 19 10)

tam dochážeme právě v polinomiálním čase vyřešit problém

9:21

S… Speaker 1 (Крипто 19 10)

a uvěřit to řešení.

9:25

S… Speaker 1 (Крипто 19 10)

To jsou takové problémy,

9:26

S… Speaker 1 (Крипто 19 10)

které nedokážete vyřešit v polinomiálním čase,

9:29

S… Speaker 1 (Крипто 19 10)

trvalo by vám to třeba exponenciální čas,

9:31

S… Speaker 1 (Крипто 19 10)

a když vám to řešení někdo dá,

9:33

S… Speaker 1 (Крипто 19 10)

tak ho dokážete v polinomiální čase ověřit,

9:37

S… Speaker 1 (Крипто 19 10)

že je správné.

9:37

S… Speaker 1 (Крипто 19 10)

A NP komplet nebo i NP úplné problémy,

9:41

S… Speaker 1 (Крипто 19 10)

to jsou takové ty nejtěžší z té přídy NP.

9:45

S… Speaker 1 (Крипто 19 10)

Ty, když umíte vyřešit,

9:47

S… Speaker 1 (Крипто 19 10)

tak umíte vyřešit všechty ostatní to NP.

9:49

S… Speaker 1 (Крипто 19 10)

Je to taková podobnožina těch nejvolších,

9:52

S… Speaker 5 (Крипто 19 10)

nejtěžších.

9:56

S… Speaker 1 (Крипто 19 10)

To bylo vše z předpozdní prezentace.

10:00

S… Speaker 1 (Крипто 19 10)

Takže poslední šance na nějaký dotaz.

10:03

S… Speaker 4 (Крипто 19 10)

Tak

10:07

S… Speaker 1 (Крипто 19 10)

a šestka

10:11

S… Speaker 1 (Крипто 19 10)

už je konečně z půlky

10:16

S… Speaker 1 (Крипто 19 10)

o kryptografii,

10:18

S… Speaker 1 (Крипто 19 10)

ale ještě se podíváme na nějaké dva,

10:20

S… Speaker 1 (Крипто 19 10)

tři algorytmy.

10:21

S… Speaker 1 (Крипто 19 10)

A zkusíme upřesnit to,

10:24

S… Speaker 1 (Крипто 19 10)

co jsme tady doteďka dělali.

10:27

S… Speaker 1 (Крипто 19 10)

My jsme si definovali některé věci jako třeba multiplicativní

10:31

S… Speaker 1 (Крипто 19 10)

inverzní prvek.

10:32

S… Speaker 1 (Крипто 19 10)

Vy víte,

10:33

S… Speaker 1 (Крипто 19 10)

co to je, ale do teďka ho neumíte úplně spočítat.

10:37

S… Speaker 1 (Крипто 19 10)

Umíte ho takovou jako brute force přístupem,

10:42

S… Speaker 1 (Крипто 19 10)

hrubou silou spočítat,

10:43

S… Speaker 1 (Крипто 19 10)

fokus omyl,

10:44

S… Speaker 1 (Крипто 19 10)

ale nemáte na to deterministický algoritmus.

10:47

S… Speaker 1 (Крипто 19 10)

Chce je tak modulárně redukci.

10:49

S… Speaker 1 (Крипто 19 10)

Máte takový jako jednoduchý postup,

10:52

S… Speaker 1 (Крипто 19 10)

že když chcete redukovat nějaké číslo menším číslem,

10:56

S… Speaker 1 (Крипто 19 10)

tak ji to odečítáte ten modulus do té doby,

10:58

S… Speaker 1 (Крипто 19 10)

než tam najdete ten správný,

11:02

S… Speaker 1 (Крипто 19 10)

ten výsledek z intervalu 0 až modulus minus 1,

11:06

S… Speaker 1 (Крипто 19 10)

nebo uděláte,

11:07

S… Speaker 1 (Крипто 19 10)

podělíte to tím a ten zbytek podělení je ta redukce,

11:10

S… Speaker 1 (Крипто 19 10)

ale to není úplně nejvykladší.

11:12

S… Speaker 1 (Крипто 19 10)

Takže ukážeme se trošku o o lepšení.

11:15

S… Speaker 1 (Крипто 19 10)

A to je právě ten Euclidův algoritmus.

11:17

S… Speaker 1 (Крипто 19 10)

Je stane 300 před naším letopočtem.

11:21

S… Speaker 1 (Крипто 19 10)

Dušíte si,

11:23

S… Speaker 1 (Крипто 19 10)

kdo ho vymyslel.

11:25

S… Speaker 1 (Крипто 19 10)

Je to efektivní algoritmus,

11:28

S… Speaker 1 (Крипто 19 10)

který slouží k výpočtu největšího společného dělitele.

11:32

S… Speaker 1 (Крипто 19 10)

Největší společný dělitel,

11:34

S… Speaker 1 (Крипто 19 10)

co jsme tady dělali v druhé přednářce na většině

11:38

S… Speaker 1 (Крипто 19 10)

GCD.

11:42

S… Speaker 1 (Крипто 19 10)

Má na vzpucu dvě čísla,

11:45

S… Speaker 1 (Крипто 19 10)

dejme tomu třeba

11:50

S… Speaker 1 (Крипто 19 10)

18 a 20.

12:00

S… Speaker 1 (Крипто 19 10)

A my jsme se doteďka učili,

12:02

S… Speaker 1 (Крипто 19 10)

nebo já jsem vás učil,

12:04

S… Speaker 1 (Крипто 19 10)

že když chcete spočítat největší společný dělitel,

12:07

S… Speaker 1 (Крипто 19 10)

tak potřebujete prvočíslený rozklad.

12:10

S… Speaker 1 (Крипто 19 10)

Potřebujete vzít těch čísla a rozložit je na prvočinitel,

12:14

S… Speaker 1 (Крипто 19 10)

nebo vyfaktorizovat.

12:16

S… Speaker 1 (Крипто 19 10)

Což pro osmnáctku osmnáctka je 2 krát 9,

12:20

S… Speaker 1 (Крипто 19 10)

takže 2 krát 3 krát 3.

12:22

S… Speaker 1 (Крипто 19 10)

Takže nebo 2 krát 3 na druhou.

12:26

S… Speaker 1 (Крипто 19 10)

Pro třicítku

12:29

S… Speaker 1 (Крипто 19 10)

by to bylo dva krát

12:34

S… Speaker 1 (Крипто 19 10)

patnáct,

12:36

S… Speaker 1 (Крипто 19 10)

že jo, takže patnáct je pět krát tři,

12:39

S… Speaker 1 (Крипто 19 10)

takže tři krát pět,

12:40

S… Speaker 1 (Крипто 19 10)

kontrolujte mě to si,

12:42

S… Speaker 4 (Крипто 19 10)

jo,

12:43

S… Speaker 5 (Крипто 19 10)

by to ale dajte.

12:44

S… Speaker 1 (Крипто 19 10)

No a teprve potom jsme byli schopni vypočítat největší společný dělitel,

12:48

S… Speaker 1 (Крипто 19 10)

a to tak,

12:49

S… Speaker 1 (Крипто 19 10)

že jsme se růzloce zamysleli,

12:51

S… Speaker 1 (Крипто 19 10)

potřebali jsme si,

12:52

S… Speaker 1 (Крипто 19 10)

co mají společného,

12:54

S… Speaker 1 (Крипто 19 10)

ty rozklady,

12:55

S… Speaker 1 (Крипто 19 10)

a znali bysme to společný.

12:57

S… Speaker 1 (Крипто 19 10)

Tady je dvojka společná,

12:58

S… Speaker 1 (Крипто 19 10)

tady je trojka společná,

13:00

S… Speaker 1 (Крипто 19 10)

takže dva krát tři by bylo šest.

13:02

S… Speaker 1 (Крипто 19 10)

Takže největší společný dělitel by byla šestka.

13:05

S… Speaker 1 (Крипто 19 10)

Šestka bez zbytku dělí 17 a šestka

13:09

S… Speaker 1 (Крипто 19 10)

bez zbytku dělí 30,

13:11

S… Speaker 1 (Крипто 19 10)

takže to funguje.

13:12

S… Speaker 1 (Крипто 19 10)

Blbý je,

13:13

S… Speaker 1 (Крипто 19 10)

že jsme si právě minulou přednášku řekli něco

13:18

S… Speaker 1 (Крипто 19 10)

o problémech typu P a NP,

13:20

S… Speaker 1 (Крипто 19 10)

to znamená těch těžkých a lehkých.

13:24

S… Speaker 1 (Крипто 19 10)

A problém faktorizace platí

13:28

S… Speaker 1 (Крипто 19 10)

mezi ty NP problémy,

13:29

S… Speaker 1 (Крипто 19 10)

ty nejtěžší,

13:30

S… Speaker 1 (Крипто 19 10)

které nedokážeme řešit.

13:33

S… Speaker 1 (Крипто 19 10)

Takže v kryptografii,

13:34

S… Speaker 1 (Крипто 19 10)

když já bych po vás nechtěl největší společný delitel čísla 18 a

13:38

S… Speaker 1 (Крипто 19 10)

30 a nechtěl bych třeba nějakých kryptografických parametrů,

13:42

S… Speaker 1 (Крипто 19 10)

které se používají v praxi,

13:43

S… Speaker 1 (Крипто 19 10)

což jsou nějaké čísla,

13:45

S… Speaker 1 (Крипто 19 10)

které mají tři tisíce bytů,

13:47

S… Speaker 1 (Крипто 19 10)

jsou to velké součiny,

13:49

S… Speaker 1 (Крипто 19 10)

tak bychom to nedokázali faktorizovat

13:54

S… Speaker 1 (Крипто 19 10)

a tím vás dokázali vyvočít na ten největší společný delitel.

13:58

S… Speaker 1 (Крипто 19 10)

Ten postup,

13:59

S… Speaker 1 (Крипто 19 10)

který jsme se naučili na druhé přednášce,

14:01

S… Speaker 1 (Крипто 19 10)

je prostě k ničemu pro velký číslo.

14:03

S… Speaker 1 (Крипто 19 10)

Tam nedokážeme faktorizovat.

14:05

S… Speaker 1 (Крипто 19 10)

Naštěstí,

14:07

S… Speaker 1 (Крипто 19 10)

ale existuje možnost dovolidovat algoritmu,

14:11

S… Speaker 1 (Крипто 19 10)

který tu faktorizaci umožní.

14:15

S… Speaker 1 (Крипто 19 10)

A to tak,

14:16

S… Speaker 1 (Крипто 19 10)

že postupně počítáme,

14:20

S… Speaker 1 (Крипто 19 10)

redukujeme pomocí modula,

14:22

S… Speaker 1 (Крипто 19 10)

modulární aritmetiky.

14:24

S… Speaker 2 (Крипто 19 10)

To znamená,

14:24

S… Speaker 1 (Крипто 19 10)

my si ty čísla zmenšujeme tak,

14:26

S… Speaker 1 (Крипто 19 10)

že vždycky to číslo větší a zde vypůjete tím menší.

14:30

S… Speaker 1 (Крипто 19 10)

A zapíšete místo toho většího ten zbytek a poté 0 dělnice.

14:35

S… Speaker 1 (Крипто 19 10)

A takhle jedete ful do kola,

14:36

S… Speaker 1 (Крипто 19 10)

až dostanete největší společní dělitel.

14:40

S… Speaker 1 (Крипто 19 10)

Takže je tady nějaký příklad.

14:42

S… Speaker 1 (Крипто 19 10)

My ten příklad zkusíme udělat tady pro ten náš.

14:46

S… Speaker 1 (Крипто 19 10)

Takže máme 3 počítal GCD 18.

14:55

S… Speaker 1 (Крипто 19 10)

A podle toho postupu,

14:56

S… Speaker 1 (Крипто 19 10)

který je na slajdu,

14:57

S… Speaker 1 (Крипто 19 10)

tak vy si můžete dovolit...

15:00

S… Speaker 1 (Крипто 19 10)

a změnit ty čísla tak,

15:03

S… Speaker 1 (Крипто 19 10)

že vezmete to číslo,

15:05

S… Speaker 1 (Крипто 19 10)

které je větší,

15:06

S… Speaker 1 (Крипто 19 10)

a redukujete ho tím menší.

15:08

S… Speaker 1 (Крипто 19 10)

Takže dáme vždycky na první pozici

15:12

S… Speaker 1 (Крипто 19 10)

to větší číslo,

15:14

S… Speaker 1 (Крипто 19 10)

takže je to můžitele mohli přehazovat,

15:17

S… Speaker 1 (Крипто 19 10)

už je na pohledu nezáleží,

15:19

S… Speaker 1 (Крипто 19 10)

takže je to stejné,

15:19

S… Speaker 1 (Крипто 19 10)

jak by tady bylo třicet psi a osmnáct.

15:23

S… Speaker 1 (Крипто 19 10)

A teďka platí,

15:25

S… Speaker 1 (Крипто 19 10)

že můžeme to větší redukovat i menší.

15:28

S… Speaker 1 (Крипто 19 10)

Takže bychom měli říct,

15:30

S… Speaker 1 (Крипто 19 10)

kolik je 18 modulo 33,

15:34

S… Speaker 1 (Крипто 19 10)

13

15:40

S… Speaker 1 (Крипто 19 10)

modulo 18.

15:41

S… Speaker 1 (Крипто 19 10)

Takže můžeme

15:45

S… Speaker 1 (Крипто 19 10)

napsat, dáme to větší jako první a to menší jako dvní.

15:49

S… Speaker 1 (Крипто 19 10)

Tak,

15:51

S… Speaker 1 (Крипто 19 10)

můžeme pokračovat dále.

15:52

S… Speaker 1 (Крипто 19 10)

Zase to větší můžeme redukovat,

15:54

S… Speaker 1 (Крипто 19 10)

tím menší.

15:54

S… Speaker 1 (Крипто 19 10)

Takže co se nám stane,

15:57

S… Speaker 1 (Крипто 19 10)

když 18 koze redukujeme 15,

15:59

S… Speaker 1 (Крипто 19 10)

v koncu nám důstane?

16:01

S… Speaker 5 (Крипто 19 10)

Tři.

16:02

S… Speaker 1 (Крипто 19 10)

Takže tady nám dáme na první pozici patnáct.

16:06

S… Speaker 1 (Крипто 19 10)

A tady dáme tři.

16:08

S… Speaker 1 (Крипто 19 10)

Tak a jdeme dál.

16:11

S… Speaker 4 (Крипто 19 10)

Tak tady

16:17

S… Speaker 1 (Крипто 19 10)

máme trojku.

16:17

S… Speaker 1 (Крипто 19 10)

A když z reduku moje patnáct modulo tři,

16:21

S… Speaker 3 (Крипто 19 10)

tak to je kolik?

16:21

S… Speaker 5 (Крипто 19 10)

Nula.

16:23

S… Speaker 1 (Крипто 19 10)

Nula. Tak a dostali jsme do okamžiku,

16:26

S… Speaker 1 (Крипто 19 10)

kdy jedno z těch čísel je nula.

16:27

S… Speaker 1 (Крипто 19 10)

Takže to druhý je největší společný dělita.

16:31

S… Speaker 1 (Крипто 19 10)

Tak a nikde máme něco asi do dvě.

16:35

S… Speaker 2 (Крипто 19 10)

Nikde máme

16:39

S… Speaker 1 (Крипто 19 10)

něco do dvě, tak mě pohleďte,

16:40

S… Speaker 2 (Крипто 19 10)

kde máme do dvě.

16:43

S… Speaker 1 (Крипто 19 10)

Máme stejný zemdání 18,

16:45

S… Speaker 1 (Крипто 19 10)

tady máme 33 a tam máme 30.

16:47

S… Speaker 1 (Крипто 19 10)

Proto nám to nevyšlo stejně.

16:49

S… Speaker 1 (Крипто 19 10)

Kdybyste to opravili,

16:51

S… Speaker 1 (Крипто 19 10)

tak máme 18,

16:54

S… Speaker 1 (Крипто 19 10)

30.

16:55

S… Speaker 1 (Крипто 19 10)

Když

17:02

S… Speaker 1 (Крипто 19 10)

dáme 30 modulo 18,

17:04

S… Speaker 1 (Крипто 19 10)

tak výsledek by měl být 12.

17:06

S… Speaker 1 (Крипто 19 10)

18

17:16

S… Speaker 1 (Крипто 19 10)

modulo 12 je 6.

17:18

S… Speaker 1 (Крипто 19 10)

Tady

17:24

S… Speaker 1 (Крипто 19 10)

dáme 6.

17:27

S… Speaker 1 (Крипто 19 10)

6k, když se redukujeme 1 nádpůl 6,

17:30

S… Speaker 1 (Крипто 19 10)

tak je 0, takže tak.

17:31

S… Speaker 1 (Крипто 19 10)

Tak už jsme ke stejnému výsledku.

17:34

S… Speaker 2 (Крипто 19 10)

Je to srozumitelný,

17:37

S… Speaker 1 (Крипто 19 10)

euklinu k algoritmus,

17:38

S… Speaker 1 (Крипто 19 10)

pořád dokola redukujete větší tím menší.

17:42

S… Speaker 1 (Крипто 19 10)

Až se dostanete k 0,

17:43

S… Speaker 1 (Крипто 19 10)

tak to druhý je ten největší společný.

17:45

S… Speaker 4 (Крипто 19 10)

Jo,

17:46

S… Speaker 1 (Крипто 19 10)

to je důležitý algoritmus,

17:47

S… Speaker 1 (Крипто 19 10)

protože modulární redukce je efektivní

17:51

S… Speaker 1 (Крипто 19 10)

a rychlý algoritmus.

17:53

S… Speaker 1 (Крипто 19 10)

Jo, ten polinomí je rájní prostě složitost.

17:55

S… Speaker 1 (Крипто 19 10)

Není tam potřeba žádných...

17:59

S… Speaker 1 (Крипто 19 10)

Něco jako faktorizace tady.

18:00

S… Speaker 1 (Крипто 19 10)

Takže to dokážeme dělat i pro extrémně velká čísla.

18:04

S… Speaker 1 (Крипто 19 10)

Tak to je jednutí Euglidův

18:08

S… Speaker 1 (Крипто 19 10)

algoritmus a potom ještě rozšíření Euglidův algoritmus.

18:12

S… Speaker 1 (Крипто 19 10)

A ten nám umožňuje vypočítat největší společný

18:17

S… Speaker 1 (Крипто 19 10)

dělitel a k tomu ještě vynárnu kombinaci,

18:20

S… Speaker 1 (Крипто 19 10)

to znamená čísla A a B,

18:23

S… Speaker 1 (Крипто 19 10)

které budou sedět tady v této rovnici.

18:27

S… Speaker 1 (Крипто 19 10)

A a B můžou být jedno je kladný,

18:29

S… Speaker 1 (Крипто 19 10)

druhý je záporný,

18:30

S… Speaker 1 (Крипто 19 10)

aby to se dělalo.

18:31

S… Speaker 1 (Крипто 19 10)

Takže vlastně ono vám to ještě

18:35

S… Speaker 1 (Крипто 19 10)

dopočítá k tomu.

18:37

S… Speaker 1 (Крипто 19 10)

Nejenom, že to vypočítá ten největší společný dělitel 6,

18:40

S… Speaker 1 (Крипто 19 10)

tu šestku,

18:41

S… Speaker 1 (Крипто 19 10)

ale ještě vypočítá nějaké dvě čísla A,

18:46

S… Speaker 1 (Крипто 19 10)

které když vynásovíte s tím jedním číslem,

18:49

S… Speaker 1 (Крипто 19 10)

dejme tomu 18,

18:50

S… Speaker 1 (Крипто 19 10)

a přičtete k tomu nějaké

18:54

S… Speaker 1 (Крипто 19 10)

číslo B krát 30.

18:57

S… Speaker 1 (Крипто 19 10)

tak to bude sedět v té rodnici.

18:59

S… Speaker 1 (Крипто 19 10)

Tohle dělá rozšíření euklidů v algoritmus.

19:02

S… Speaker 1 (Крипто 19 10)

Vypočte to A a B.

19:04

S… Speaker 1 (Крипто 19 10)

Jedno je kvarné,

19:06

S… Speaker 1 (Крипто 19 10)

jedno je záporné,

19:07

S… Speaker 3 (Крипто 19 10)

aby to sedělo.

19:07

S… Speaker 4 (Крипто 19 10)

To

19:12

S… Speaker 1 (Крипто 19 10)

musí říct na lineální kombinace dvou čísel,

19:15

S… Speaker 1 (Крипто 19 10)

aby to vedlo kvůznice.

19:17

S… Speaker 1 (Крипто 19 10)

A tohle se dá dobře zneužít,

19:20

S… Speaker 1 (Крипто 19 10)

ten rozšíření euklidů v algoritmus,

19:22

S… Speaker 1 (Крипто 19 10)

k tomu,

19:23

S… Speaker 1 (Крипто 19 10)

když chcete spočítat multiplicativní inverzní

19:28

S… Speaker 2 (Крипто 19 10)

prvek.

19:30

S… Speaker 1 (Крипто 19 10)

Kdybyste chtěli vypočítat multiplicativní niverzní prvek,

19:34

S… Speaker 1 (Крипто 19 10)

ten se označuje jako 18 na minus první modulo

19:38

S… Speaker 4 (Крипто 19 10)

30,

19:39

S… Speaker 1 (Крипто 19 10)

tak tohle vám pomůže.

19:43

S… Speaker 1 (Крипто 19 10)

Tady to H a B.

19:45

S… Speaker 1 (Крипто 19 10)

Proč?

19:47

S… Speaker 1 (Крипто 19 10)

Protože když chcete počítat

19:51

S… Speaker 1 (Крипто 19 10)

multiplicativní niverzní prvek,

19:55

S… Speaker 1 (Крипто 19 10)

tak vy základní předpoklad musíte vědět,

20:00

S… Speaker 1 (Крипто 19 10)

je větší společný dělitel 18 i a 30 i je jednička.

20:04

S… Speaker 1 (Крипто 19 10)

Tak vidíte,

20:06

S… Speaker 1 (Крипто 19 10)

to je z definice multiplicativního inverzního prvku.

20:09

S… Speaker 1 (Крипто 19 10)

Ten existuje jenom pokud jsou ty dvě čísla nesoudělné,

20:13

S… Speaker 1 (Крипто 19 10)

ta 18 a 30.

20:14

S… Speaker 1 (Крипто 19 10)

Takže vy vidíte,

20:15

S… Speaker 1 (Крипто 19 10)

že na davé straně máte jedničku a na pravé

20:19

S… Speaker 1 (Крипто 19 10)

straně máte nějaké číslo a

20:23

S… Speaker 1 (Крипто 19 10)

krát 18 plus

20:27

S… Speaker 1 (Крипто 19 10)

b krát 30.

20:31

S… Speaker 1 (Крипто 19 10)

Máme tady tu rovnici,

20:33

S… Speaker 1 (Крипто 19 10)

do které dokážeme spočítat A a B pomocí rozštířeného a úbědového

20:37

S… Speaker 1 (Крипто 19 10)

albatu.

20:38

S… Speaker 1 (Крипто 19 10)

Ale co se stane,

20:39

S… Speaker 1 (Крипто 19 10)

když tu rovnici aplikujete

20:44

S… Speaker 1 (Крипто 19 10)

na to modulární arismetiku?

20:45

S… Speaker 1 (Крипто 19 10)

To znamená modulo 30.

20:46

S… Speaker 1 (Крипто 19 10)

Pracujeme modulo 30.

20:48

S… Speaker 1 (Крипто 19 10)

Modulo 30 bude

20:53

S… Speaker 1 (Крипто 19 10)

pořád 1.

20:53

S… Speaker 1 (Крипто 19 10)

Vydáme konkurenci,

20:57

S… Speaker 1 (Крипто 19 10)

protože aplikujeme modulo 30.

21:02

S… Speaker 1 (Крипто 19 10)

No a tady vpravo,

21:03

S… Speaker 1 (Крипто 19 10)

v modulární aritmetice,

21:06

S… Speaker 1 (Крипто 19 10)

zůstane je to stejný,

21:07

S… Speaker 1 (Крипто 19 10)

A x 18,

21:08

S… Speaker 1 (Крипто 19 10)

ale když dáte B x 30,

21:11

S… Speaker 1 (Крипто 19 10)

nevydopojíte modulo 30,

21:12

S… Speaker 1 (Крипто 19 10)

tak to vám zmizí.

21:13

S… Speaker 1 (Крипто 19 10)

Jakýkoliv násobek třícítky v modulární aritmetice

21:17

S… Speaker 1 (Крипто 19 10)

modulo 30 je 0.

21:19

S… Speaker 1 (Крипто 19 10)

Zbytek podělení třícítkou z násobky třícítky

21:23

S… Speaker 1 (Крипто 19 10)

je 0.

21:23

S… Speaker 1 (Крипто 19 10)

Takže toto celý zmizelo a máme v modulární aritmetice tady

21:27

S… Speaker 1 (Крипто 19 10)

takovou to konkurec.

21:30

S… Speaker 1 (Крипто 19 10)

jednička rovná se,

21:32

S… Speaker 1 (Крипто 19 10)

nebo je konkurence,

21:33

S… Speaker 1 (Крипто 19 10)

a krát osmnáct.

21:34

S… Speaker 1 (Крипто 19 10)

No a tohle už je definice multiplicativního inverzního prvu,

21:38

S… Speaker 1 (Крипто 19 10)

že jo?

21:38

S… Speaker 1 (Крипто 19 10)

Protože když osmnáctku vy násovíte ačkem a vyjde

21:43

S… Speaker 1 (Крипто 19 10)

vám jednička,

21:43

S… Speaker 1 (Крипто 19 10)

no tak ačko je multiplicativní inverzní

21:48

S… Speaker 1 (Крипто 19 10)

prvu.

21:48

S… Speaker 4 (Крипто 19 10)

Takže

21:53

S… Speaker 1 (Крипто 19 10)

vy tady máte postup.

21:55

S… Speaker 1 (Крипто 19 10)

Jak vypočítat multiplicativní inverzní prvek?

21:58

S… Speaker 1 (Крипто 19 10)

Dosud jste to neuděli.

22:00

S… Speaker 3 (Крипто 19 10)

Dokud teďka,

Крипто 19 10

Резюме

Попитайте интелигентния интелект за този текст