Y36BEZ Bezpečnost přenosu a zpracování dat. Úvod. Róbert Lórencz

Y36BEZ – Bezpeˇcnost pˇrenosu a zpracování dat Róbert Lórencz 1. pˇrednáška

Úvod http://service.felk.cvut.cz/courses/Y36BEZ [email protected]

ˇ Róbert Lórencz (CVUT FEL, 2007)

Y36BEZ – Bezpeˇcnost pˇrenosu a zpracování dat

1 / 33

Obsah pˇrednášky

Historie Základy modulární aritmetiky Základy teorie cˇ ísel ˇ aritmetiky Základní veta



2 / 33

Historie Moderní kryptografie – matematický aparát teorie cˇ ísel. Teorie cˇ ísel – studium vlastností pˇrirozených N = {1, 2, . . . } a celých cˇ ísel Z = {0, ±1, ±2, . . . }. Jedna z nejstarších matematických disciplín – antika. ˇ Nekteré algoritmy z období antiky – souˇcást moderních kryptografických systému, ˚ napˇr. Eukliduv ˚ algoritmus. Práce L. Eulera (1707-1783) a C. F. Gausse (1777-1855) položily základ moderní teorie cˇ ísel a algebry. Velmi duležitý ˚ pojem kongruence zaveden Gaussem: a ≡ b (mod m) – a je kongruentní b modulo m. Algebra – vyšetˇruje vlastnosti množin a jejich prvku˚ z hlediska algebraické manipulace s nimi (napˇr. +/−).



3 / 33

Základy modulární aritmetiky (1) Definice kongruence Necht’ a, b, m ∈ Z, kde m > 1. Pokud m|(b − a), ˇríkáme, že b je kongruentní k a modulo m a píšeme b ≡ a (mod m). Pokud m - (b −a), ˇríkáme, že b není kongruentní k a modulo m a píšeme b 6≡ a (mod m). Pokud používáme celoˇcíselnou aritmetiku a výsledky redukujeme modulem m, ˇríkáme, že používáme tzv. jedno-modulovou aritmetiku kódu˚ zbytkových tˇríd (single-modulus residue arithmetic). Celé cˇ íslo m > 1 nazýváme modulem aritmetického systému. ˇ Typický pˇríklad z bežného života – „hodinová aritmetika“ 23 ≡ 11 (mod 12) – ? 11 hod. ∼ 23 hod. ? ˇ Róbert Lórencz (CVUT FEL, 2007)


4 / 33

Základy modulární aritmetiky (2) Vlastnosti kongruencí Necht’ a, b, c, d, x, y , m ∈ Z, kde m > 1. 1

Následující tˇri kongruence jsou ekvivalentní: a ≡ b (mod m), b ≡ a (mod m), a − b ≡ 0 (mod m).

2

Pokud a ≡ b (mod m) a b ≡ c (mod m) potom a ≡ c (mod m).

3

Pokud a ≡ b (mod m) a c ≡ d (mod m) potom ax + cy ≡ bx + dy (mod m).

4

Pokud a ≡ b (mod m) a c ≡ d (mod m), potom ac ≡ bd (mod m).



5 / 33

Základy modulární aritmetiky (3) V jedno-modulární reziduální aritmetice je každé celé cˇ íslo b ∈ Z zobrazeno do celého cˇ ísla r ∈ Zm = {0, 1, 2, . . . , m − 1} . ˇ Císlo r je nejmenším nezáporným reziduem b modulo m. Definice zobrazení | · |m | · |m : Z → Zm je definováno zápisem |b|m = r tehdy a jen tehdy, když 0 ≤ r < m a b ≡ r (mod m). Z je sjednocení m disjunktních podmnožin R0 , R1 , . . . , Rm−1 nazvaných zbytkové tˇrídy, kde Rk = {b ∈ Z : |b|m = k }. ˇ Pˇríklad: Když m = 7, potom 58 ∈ R2 protože |58|7 = 2. Ríkáme, že 2 je nejmenší nezáporné reziduum cˇ ísla 58 modulo 7.



6 / 33

Základy modulární aritmetiky (4) Vlastnosti zobrazení | · |m ˇ 1 Veta Necht’ a, b, m ∈ Z, kde m > 1. Potom |a|m

je jedineˇcné,

|a|m = |b|m ⇐⇒ a ≡ b (mod m), |km|m = 0

pro všechna k ∈ Z

a dále platí |a + b|m = |a|m + |b|m = |a|m + b = a + |b|m m m m |ab|m = |a|m |b|m = |a|m b = a|b|m . m

m

m

Z pˇredcházejícího je zˇrejmé, že nezáleží na tom, kdy se provede redukce modulo m. ˇ Róbert Lórencz (CVUT FEL, 2007)


7 / 33

Základy modulární aritmetiky (5) ˇ 2 Veta Množina (Zm , +, ·), kde + a · oznaˇcuje sˇcítání modulo m a násobení modulo m tvoˇrí koneˇcný komutativní okruh s jednotkou. ˇ ríme následující vlastnosti, které jsou platné pro každé Dukaz: ˚ Oveˇ a, b, c, ∈ Zm . uzavˇrenost komutativita asociativita neutrální prvek inv. prvek k + distributivita

|a + b|m ∈ Zm |a + b|m = |b + a|m |a + (b + c)|m = |(a + b) + c|m |a + 0|m = |a|m |a + a|m = 0 |a(b + c)|m = |ab + ac|m ,

|ab|m ∈ Zm , |ab|m = |ba|m , |a(bc)|m = |(ab)c|m , |a · 1|m = |a|m , ··· ,

kde aditivní inverze modulo m je a ≡ | − a|m = m − a. ˇ Róbert Lórencz (CVUT FEL, 2007)


8 / 33

Základy modulární aritmetiky (6) Mužeme ˚ definovat odˇcítání na okruhu (Z, +, ·) jako sˇcítání s aditivní inverzí modulo m Definice odˇcítání na okruhu (Z, +, ·) |a − b|m ≡ |a + b|m . ˇ Modulární multiplikativní inverze urˇcitého prvku (Zm , +, ·) umožnuje ˇ delení ˇ provádet tímto prvkem jako násobení jeho inverzí modulo m. Problém: existence modulární multiplikativní inverze prvku z (Zm , +, ·). ˇ 3 Veta ˇ Koneˇcný komutativní okruh (Z, +, ·) je koneˇcným telesem tehdy a jen tehdy, pokud m je prvoˇcíslo. ˇ Róbert Lórencz (CVUT FEL, 2007)


9 / 33

Základy modulární aritmetiky (7) ˇ Pokud m je prvoˇcíslo, (Zm , +, ·) je izomorfní k Galoisovu telesu GF(p) a každý nenulový prvek Zm má multiplikativní inverzi modulo m, která ˇ je definovaná následovne: ˇ 4 – definice Veta Když m je prvoˇcíslo, b 6= 0 a b ∈ Zm , pak existuje jediné celé cˇ íslo c ∈ Zm , které vyhovuje rovnici |cb|m = |bc|m = 1. ˇ Císlu c ˇríkáme multiplikativní inverze b modulo m a píšeme c = b−1 (m) nebo jednoduše b−1 pokud je modul znám. ˇ Pokud m není prvoˇcíslo, (Zm , +, ·) není teleso a nenulové prvky nemusí mít multiplikativní inverzi. ˇ Róbert Lórencz (CVUT FEL, 2007)


10 / 33

Základy modulární aritmetiky (8) ˇ 5 o existenci inverze Veta Necht’ b ∈ Z. Potom existuje jediné celé cˇ íslo c ∈ Zm , které vyhovuje rovnici |cb|m = |bc|m = 1 ⇔ |b|m 6= 0 ∧ gcd(b, m) = 1. Dusledek: ˚ Když b ∈ Zm , b 6= 0 ⇒ existuje práveˇ jedno b−1 (m) ∈ Zm ˇ ⇐⇒ b a m jsou vzájemneˇ nesoudelná. Pˇríklady: m = 10 a Z10 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} tak jen cˇ ísla 1,3,7 a 9 mají multiplikativní inverzi modulo 10. m = 5 (prvoˇcíslo) a Z5 = {0, 1, 2, 3, 4} tak všechny nenulové prvky (tj. 1,2,3,4) mají multiplikativní inverzi modulo 5. (Zm , +, ·) je vždy koneˇcný komutativní okruh. Když m je prvoˇcíslo ⇒ ˇ ˇ (Zm , +, ·) je koneˇcné teleso izomorfní ke Galoisovu telesu GF(m). ˇ Róbert Lórencz (CVUT FEL, 2007)


11 / 33

Základy modulární aritmetiky (9) ˇ ˇ Definice delení na koneˇcném telese ˇ Když b−1 existuje ⇒ definujeme delení modulo m jako a = |ab−1 |m . b m Pozor! Podíl dvou celých cˇ ísel v jedno-modulární aritmetice, pokud existuje, je ˇ že a nedelí ˇ b. vždy celé cˇ íslo a to i v pˇrípade, Pˇríklad: |7/9|11 = |7 · 9−1 |11 = |7 · 5|11 = 2. ˇ Róbert Lórencz (CVUT FEL, 2007)


12 / 33

Základy modulární aritmetiky (10) |b|m je definováno jako nezáporné rezidum (zbytek) b modulo m. ˇ Tímto zpusobem ˚ jsou výpoˇcty v jedno-modulární aritmetice provádeny s nezápornými celými cˇ ísly z množiny (Zm , +, ·). V pˇrípadeˇ použití množiny záporných cˇ ísel, uvažujeme množinu symetrických reziduí modulo m. n m−1 m − 1o Sm = − , . . . , −2, −1, 0, 1, 2, . . . , , 2 2 Pro symetrii vzhledem k nule, m musí být liché cˇ íslo. Množina Sm zobrazuje každé celé cˇ íslo b ∈ Z do celého cˇ ísla s ∈ Sm podle následujícího zobrazení. Definice symetrického rezidua b modulo m → /b/m / · /m : Z → Sm ∧ /b/m = s ˇ Róbert Lórencz (CVUT FEL, 2007)

⇔

b ≡ s (mod m) ∧ − m 2 <s <


m 2

13 / 33

Základy modulární aritmetiky (11) Vlastnosti zobrazení / · /m (Sm , +, ·) je koneˇcný komutativní okruh, ˇ Když m je prvoˇcíslo ⇒ (Sm , +, ·) je koneˇcné teleso, (Sm , +, ·) je izomorfní k (Zm , +, ·). Uvažujme pˇrípad, že data popisující ˇrešený problém jsou z Sm ⇒ 1

zobrazíme daná data z Sm do Zm ,

2

vykonáváme operace v Zm ,

3

výsledky pˇrevedeme do Sm .

Zobrazovací funkce z / · /m do | · |m a obráceneˇ jsou následující: n /a/ , když 0 ≤ /a/m < m m 2 |a|m = /a/m + m jinak, n |a| , když 0 ≤ |a|m < m m 2 /a/m = |a|m − m jinak, ˇ Róbert Lórencz (CVUT FEL, 2007)


14 / 33

Základy modulární aritmetiky (12) Pˇríklad:

|x|103 = |48/12 + (−24)|103 −1 = |48 · 12 |103 + 79 103 = |48 · 43|103 + 79 103

= |4 + 79|103 = 83. ˇ do S103 a získáme: Tento výsledek zobrazíme zpet /x/103 = −20. Poznámka: Je duležité ˚ vybrat tak velké m, aby Sm obsahovalo jak hodnoty popisující ˇrešený problém, tak také hodnoty výsledku ˇrešení problému. Výsledek muže ˚ být nesprávný, ale je kongruentní se správným výsledkem ⇒ nastalo pseudo-pˇreteˇcení (pseudo-overflow). ˇ Róbert Lórencz (CVUT FEL, 2007)


15 / 33

Základy teorie cˇ ísel (1) ˇ spoleˇcný delitel ˇ Definice – Nejvetší (greatest common divisor — GCD) ˇ spoleˇcný delitel ˇ ˇ Nejvetší dvou celých nenulových cˇ ísel a a b je nejvetší ˇ ˇ kladné cˇ íslo d, pro které platí: d|a a d|b. Nejvetší spoleˇcný delitel a a b je oznaˇcen jako gcd (a, b). Také definujeme gcd (0, 0) = 0. Z této definice dále plyne: gcd (a, a) = |a|, gcd (a, 1)

= 1,

gcd (a, b)|a a souˇcasneˇ gcd (a, b)|b. ˇ Definice – Nesoudelnost ˇ Celá cˇ ísla a a b jsou nesoudelná (relatively prime) když a a b mají ˇ spoleˇcný delitel ˇ nejvetší gcd (a, b) = 1. ˇ ˇ Pˇríklad: Císla 25 a 42 jsou nesoudelná protože gcd (25, 42) = 1. ˇ Róbert Lórencz (CVUT FEL, 2007)


16 / 33

Základy teorie cˇ ísel (2) ˇ 6 Veta Když a, b, c ∈ Z a dále když platí, že a|b a b|c, potom a|c. Dukaz: ˚ Protože a|b a b|c ⇒ existují taková celá cˇ ísla e a f , pro která platí ae = b a bf = c. Z toho vyplývá, že c = bf = (ae)f = a(ef ) a a|c. Pˇríklad: 5|15, 15|45 ⇒ 5|45. ˇ 7 Veta Když a, b, m, n ∈ Z a dále když platí, že c|a a c|b, potom c|(ma + nb). Dukaz: ˚ Když c|a a c|b ⇒ existují e a f ∈ Z, pro která platí a = ce a b = cf ⇒ ma + mb = mce + ncf = c(me + nf ) a potom c|(ma + nb). Pˇríklad: 3|6, 3|15 ⇒ 3|(6m + 15n) ≡ 3|(3(2m + 5n)). ˇ Róbert Lórencz (CVUT FEL, 2007)


17 / 33

Základy teorie cˇ ísel (3) ˇ 8 Veta Necht’ a, b, c, d ∈ Z, pro která platí gcd (a, b) = d, ⇒ 1

gcd (a/d, b/d) = 1

2

gcd (a + cb, b) = gcd (a, b)

Dukaz: ˚ 1

Platí gcd (a, b) = d ⇒ ukážeme, že a/d a b/d nemají spoleˇcný ˇ kladný delitel jiný než 1. Necht’ e ∈ Z, e > 0 a platí e|(a/d) a e|(b/d) ⇒ existují taková k , l ∈ Z, pro která platí a/d = ke a ˇ b/d = le a tedy a = dek a b = del ⇒ de je spoleˇcným delitelem a ˇ spoleˇcný delitel ˇ a b. Protože d je nejvetší a a b platí de ≤ d a z toho plyne, že e = 1 a tedy také gcd (a/d, b/d) = 1.

2

ˇ ˇ jak a, tak také b ⇒ e|(a + cb). Když nejaké celé cˇ íslo e delí ˇ Spoleˇcní delitelé b a (a + cb) jsou stejná cˇ ísla jako spoleˇcní ˇ delitelé a a b ⇒ ??? ⇒ gcd (a + cb, b) = gcd (a, b).



18 / 33

Základy teorie cˇ ísel (4) ˇ spoleˇcný delitel ˇ Dále si ukážeme, že nejvetší celých nenulových cˇ ísel a a b je vyjádˇren souˇctem ma + nb, kde m a n jsou celá cˇ ísla. Definice – Lineární kombinace Když a, b ∈ Z, potom lineární kombinace nenulových cˇ ísel a a b je vyjádˇrena vztahem ma + nb, kde m, n ∈ Z. ˇ 9 Veta ˇ ˇ Nejvetší spoleˇcný delitel celých nenulových cˇ ísel a a b je nejmenší kladné celé cˇ íslo, které je lineární kombinací a a b. Dukaz ˚ (1): Necht’ d je nejmenší kladné cˇ íslo, které je lineární kombinací a a b. (Minimálneˇ jedno takové kladné cˇ íslo existuje, protože jedna ze dvou lineárních kombinací 1a + 0b a (−1)a + 0b, kde a 6= 0, je kladná.) Pak píšeme d = ma + nb, kde m a n jsou celá cˇ ísla. ˇ Róbert Lórencz (CVUT FEL, 2007)


19 / 33

Základy teorie cˇ ísel (5) ˇ Dukaz ˚ (2): Ukážeme, že d|a a d|b. Z algoritmu pro delení plyne a = dq + r ,

0 ≤ r < d.

Z pˇredchozích dvou rovnic dostáváme rovnici r = a − dq = a − q(ma + nb) = (1 − qm)a − qnb. Z toho plyne, že r je lineární kombinací a a b. Protože 0 ≤ r < d a d je nejmenší kladná lineární kombinace a a b platí, že r = 0 a odtud d|a. Podobným zpusobem ˚ mužeme ˚ ukázat, že platí d|b. ˇ spoleˇcný delitelem ˇ Dále si dokážeme, že d je nejvetší a i b. Toto ˇ ˇ tvrzení platí, pokud existuje nejaký spoleˇcný delitel c cˇ ísel a a b, který ˇ také d. Protože d = ma + nb a z pˇredpokladu c|a a c|b potom delí ˇ 7 c|d. Pokud d|a a d|b, a to jsme dokázali, ⇒ podle Vety gcd(a, b) = d. ˇ Róbert Lórencz (CVUT FEL, 2007)


20 / 33

Základy teorie cˇ ísel (6) Vývojem algoritmu pro nalezení GCD dvou kladných celých cˇ ísel se zabýval ˇrecký matematik Euklides narozen cca 350 let pnl. Metoda, kterou Euklides vyvinul/zapsal pro výpoˇcet GCD je známa jako Eukliduv ˚ algoritmus (EA). ˇ 10 – Eukliduv Veta ˚ algoritmus Necht’ r0 = a a r1 = b jsou celá cˇ ísla, pro která platí a ≥ b > 0. Pokud ˇ je delící algoritmus postupneˇ použit k získání rj = rj+1 qj+1 + rj+2 , pˇri platnosti podmínek 0 < rj+2 < rj+1 pro j = 0, 1, 2, . . . , n − 2 a rn+1 = 0, potom gcd (a, b) = rn je poslední nenulový zbytek. Jinak: gcd (a, b) je poslední nenulový zbytek rn v sekvenci rovnic ˇ ˇ generovaných s postupným použitím delícího algoritmu provádeného tak dlouho, dokud není zbytek rovný nule. V každém dalším kroku ˇ ˇ ˇ en ˇ za menší cˇ ísla a to za delitele ˇ algoritmu je delenec a delitel zamen a zbytek kroku pˇredchozího. ˇ Róbert Lórencz (CVUT FEL, 2007)


21 / 33

Základy teorie cˇ ísel (7) Dukaz ˚ (1): Necht’ r0 = a a r1 = b jsou kladná celá cˇ ísla, pro která platí ˇ ˇ a ≥ b. Postupným provádením delícího algoritmu dostáváme posloupnost rovnic a podmínek pro výpoˇcet zbytku˚ r2 , r3 , . . . , rn−1 r0 = r1 q 1 + r2 0 ≤ r2 < r1 r1 = r2 q 2 + r3 0 ≤ r3 < r2 .. . rj−2

= rj−1 qj−1 + rj .. .

0 ≤ rj < rj−1

rn−3 = rn−2 qn−2 + rn−1 0 ≤ rn−1 < rn−2 rn−2 = rn−1 qn−1 + rn 0 ≤ rn < rn−1 rn−1 = rn qn Mužeme ˚ pˇredpokládat, že pro získání zbytku, který je roven nule, ˇ potˇrebujeme koneˇcný poˇcet delení a to nejvíce a protože platí a = r0 > r1 > r2 > · · · ≥ 0. ˇ Róbert Lórencz (CVUT FEL, 2007)


22 / 33

Základy teorie cˇ ísel (8) ˇ Veta ˇ 8 (2.) dále platí, že Dukaz ˚ (2): S použitím pomocné vety gcd (a, b) = gcd (r0 , r1 ) = gcd (r1 , r2 ) = gcd (r2 , r3 ) = · · · = gcd (rn−3 , rn−2 ) = gcd (rn−2 , rn−1 ) = gcd (rn−1 , rn ) = gcd (rn , 0) = rn ⇒ gcd (a, b) = rn , kde rn je poslední nenulový zbytek. Pˇríklad: gcd (254, 158) = ? 254 = 1 · 158 + 96 158 = 1 · 96 + 62 96 = 1 · 62 + 34 62 = 1 · 34 + 28 34 = 1 · 28 + 6 28 = 4 · 6 + 4 6 = 1·4+2 gcd (254, 158) = 2. ˇ Róbert Lórencz (CVUT FEL, 2007)

4 = 2·2. Y36BEZ – Bezpeˇcnost pˇrenosu a zpracování dat

23 / 33

ˇ aritmetiky (1) Základní veta Množinu všech kladných nenulových cˇ ísel (pˇrirozených cˇ ísel) ˇ rozdelujeme do tˇrí skupin: ˇ 1 ˇ Císlo 1, které kromeˇ sebe není delitelné žádným jiným cˇ íslem. 2

ˇ Prvoˇcísla, které kromeˇ sebe jsou delitelné jen cˇ íslem 1.

3

A ostatní cˇ ísla, která se nazývají složená.

ˇ 11 - pomocná Veta Když a|bc a gcd (a, b) = 1 potom a|c. ˇ 9, že existují Dukaz: ˚ Z podmínky gcd (a, b) = 1 plyne podle Vety taková celá cˇ ísla x a y , že 1 = ax + by . Vynásobme uvedenou rovnici cˇ íslem c: c = cax + cby . ˇ 7 je tedy pravá strana poslední rovnosti Podle pˇredpokladu a|bc a Vety ˇ ˇ delitelná cˇ íslem a, a proto musí být delitelná také levá tj. cˇ íslem c. ˇ Róbert Lórencz (CVUT FEL, 2007)


24 / 33

ˇ aritmetiky (2) Základní veta ˇ 12 Veta Necht’ p je prvoˇcíslo a necht’ p|(a1 · a2 · · · · · ak ), kde ai , k jsou pˇrirozená cˇ ísla. Potom bud’ p|a1 nebo p|a2 ... nebo p|ak . Slovy: Když prvoˇcíslo je ˇ ˇ delitelem souˇcinu, potom je delitelem alesponˇ jednoho cˇ initele. Dukaz: ˚ Dukaz ˚ provedeme indukcí. ˇ dokážeme nejdˇríve pro k = 2. Pokud p je prvoˇcíslo, mohou nastat Vetu dva pˇrípady, bud’ p|a1 , a v tom pˇrípadeˇ nemáme co dokazovat, nebo ˇ 11 a ze vztahu gcd (p, a1 ) = 1. Ve druhém pˇrípadeˇ z pomocné Vety p|(a1 · a2 ) plyne p|a2 . ˇ platí pro Nyní si oznaˇcme A = a1 · a2 · · · ak −1 . Pˇredpokládejme, že veta k − 1 cˇ initelu˚ a dokážeme, že platí také pro k cˇ initelu. ˚ Podle ˇ platí p|(A · ak ). Opet ˇ rozlišujeme dva pˇrípady: bud’ pˇredpokladu˚ vety p|A, a potom podle indukˇcního pˇredpokladu je naše tvrzení pravdivé, nebot’ p|ak . ˇ Róbert Lórencz (CVUT FEL, 2007)


25 / 33

ˇ aritmetiky (3) Základní veta ˇ 13 Veta Každé složené cˇ íslo mužeme ˚ psát ve tvaru souˇcinu prvoˇcísel. Dukaz: ˚ Dukaz ˚ provedeme indukcí. Nejmenší složené cˇ íslo je 4, pro které platí 4 = 2 · 2, a tedy tvrzení je správné. Pˇredpokládejme, že tvrzení je pravdivé pro všechna složená cˇ ísla menší než n. Necht’ n je složené cˇ íslo a mužeme ˚ ho napsat ve ˇ tvaru n = a · b, kde 1 < a < n, 1 < b < n. Císlo a je bud’ prvoˇcíslo, nebo složené cˇ íslo menší než n, a tak podle indukˇcního pˇredpokladu je ho možné napsat ve tvaru souˇcinu prvoˇcísel. To samé platí také pro b, a proto také n mužeme ˚ zapsat ve tvaru souˇcinu prvoˇcísel, protože n je souˇcinem a a b. ˇ aritmetiky ukazuje, že prvoˇcísla jsou základními Základní veta "stavebními prvky" pˇrirozených cˇ ísel. ˇ Róbert Lórencz (CVUT FEL, 2007)


26 / 33

ˇ aritmetiky (4) Základní veta ˇ 14 – Základní veta ˇ aritmetiky Veta Každé kladné celé cˇ íslo n se dá vyjádˇrit jediným zpusobem ˚ ve tvaru, ˇ který se nazývá kanonickým rozkladem cˇ ísla n nebo prvocíselnou mocninnou faktorizací cˇ ísla n n = p1α1 · p2α2 · · · pkαk , kde p1 < p2 < · · · < pk jsou prvoˇcísla a α1 , . . . , αk jsou pˇrirozená cˇ ísla. ˇ Každé složené cˇ íslo muže Slovne: ˚ být jednoznaˇcneˇ zapsáno jako souˇcin prvoˇcísel, kde prvoˇcíselné souˇcinitele jsou seˇrazeny do neklesající posloupnosti. Dukaz ˚ (1): Vyjádˇrení složených cˇ ísel ve tvaru souˇcinu˚ prvoˇcísel bylo již ˇ eˇ 13. Když n je prvoˇcíslo, pak staˇcí, když k = 1, p1 = n uvedeno ve Vet a α1 = 1. Zbývá ješteˇ dokázat, že pro každé pˇrirozené cˇ íslo existuje jediné takové vyjádˇrení. ˇ Róbert Lórencz (CVUT FEL, 2007)


27 / 33

ˇ aritmetiky (5) Základní veta ˇ Dukaz ˚ (2): Pˇredpokládejme, že pro nejaké n existují dveˇ vyjádˇrení α1 α2 v kanonickém tvaru n = p · p · · · p αk 1

2

q1β1

q2β2

k

· · · qsβs ,

n= · kde p1 < p2 < · · · < pk , q1 < q2 < · · · < qs , jsou prvoˇcísla a α1 , . . . , αk a β1 , . . . , βs jsou pˇrirozená cˇ ísla. Potom p1α1 · p2α2 · · · pkαk = q1β1 · q2β2 · · · qkβs . Pro každé i tedy platí

pi |(q1β1 · q2β2 · · · qsβs ). β

ˇ 12 z toho plyne, že pi |qj j pro nekterá ˇ ˇ Na základeˇ Vety j. Staˇcí opet ˇ 12, abychom dostali pi |qi , a to je možné jen tehdy, když aplikovat Vetu pi = qi , protože obeˇ jsou prvoˇcísla. Z toho dále plyne, že na pravé straneˇ rovnice p1α1 · p2α2 · · · pkαk = q1β1 · q2β2 · · · qkβs je alesponˇ tolik prvoˇcísel, jako na levé, tj. k ≤ s. Protože pi a qi jsou uspoˇrádané podle velikosti ⇒ p1 = q1 , . . . , pk = qk . ˇ Róbert Lórencz (CVUT FEL, 2007)


28 / 33

ˇ aritmetiky (6) Základní veta Dukaz ˚ (3): Zbývá ješteˇ dokázat, že αi = βi pro i = 1, 2, . . . , k . Tento dukaz ˚ provedeme nepˇrímo. Pˇredpokládejme, že αi > βi . Potom ˇ z rovnosti s = k po vydelení rovnice p1α1 · p2α2 · · · pkαk = q1β1 · q2β2 · · · qkβs βi cˇ íslem pi dostaneme rovnost αi−1 βi−1 αi+1 βi+1 p1α1 · · · pi−1 · piαi −βi · pi+1 · · · pkαk = p1β1 · · · pi−1 · pi+1 · · · pkβk . ˇ αi − βi > 0, a proto levá strana pˇredchozí rovnosti je delitelná prvoˇcíslem pi , ale pravá ne, a to je spor. Podobneˇ postupujeme v pˇrípadeˇ βi > αi , takže pro všechny i = 1, . . . , k platí αi = βi . Z toho ale vyplývá, že každé dveˇ vyjádˇrení cˇ ísla n v kanonickém tvaru jsou totožná, a proto libovolné n mužeme ˚ vyjádˇrit v kanonickém tvaru jen jediným zpusobem. ˚ ˇ Pˇríklad: Kladná cˇ ísla 240, 289 a 1001 mužeme ˚ vyjádˇrit následovne: 4 240 = 2 · 2 · 2 · 2 · 3 · 5 = 2 · 3 · 5 289 = 17 · 17 = 172 1001 = 7 · 11 · 13 ˇ Róbert Lórencz (CVUT FEL, 2007)


29 / 33

ˇ aritmetiky (7) Základní veta Dále si uvedeme, jakým zpusobem ˚ lze využít prvoˇcíselnou faktorizaci ˇ ˇ pro popis nejvetšího spoleˇcného delitele – GCD dvou celých cˇ ísel a a b gcd (a, b). Dále oznaˇcení min (a, b) vyjadˇruje menší nebo minimum dvou cˇ ísel a a b. Necht’ prvoˇcíselná faktorizace dvou cˇ ísel a a b je vyjádˇrena a = p1α1 · p2α2 · · · pkαk ,

b = q1β1 · q2β2 · · · qkβk ,

kde každý exponent je celé nezáporné cˇ íslo, a kde všechna prvoˇcísla vyskytující se v prvoˇcíselné faktorizaci a a b jsou obsažena v obou souˇcinech a také s nulovým exponentem ⇒ to nejsou kanonické rozklady. Potom min (α1 ,β1 ) min (α2 ,β2 ) min(αk ,βk ) gcd (a, b) = p1 · p2 · · · pk , protože cˇ ísla a a b sdílejí práveˇ min (αi , βi ) násobku˚ prvoˇcísla pi . ˇ Róbert Lórencz (CVUT FEL, 2007)


30 / 33

ˇ aritmetiky (8) Základní veta Prvoˇcíselný rozklad muže ˚ být také použit pro nalezení nejmenšího celého cˇ ísla, které je násobkem dvou kladných celých cˇ ísel. Definice – Nejmenší spoleˇcný násobek (least common multiple – LCM) ˇ Nejmenší spolecný násobek dvou kladných cˇ ísel a a b je nejmenší ˇ kladné celé cˇ íslo, které je delitelné cˇ ísly a i b. Nejmenší spoleˇcný násobek cˇ ísel a a b je oznaˇcován zápisem [a, b]. Pokud prvoˇcíselné rozklady cˇ ísel a a b jsou známe, lehce mužeme ˚ ˇ platí najít [a, b]. Necht’ opet a = p1α1 · p2α2 · · · pkαk ,

b = q1β1 · q2β2 · · · qkβk ,

a také každý exponent je celé nezáporné cˇ íslo, a kde všechna prvoˇcísla vyskytující se v prvoˇcíselné faktorizaci a a b jsou obsažena v obou souˇcinech. ˇ Róbert Lórencz (CVUT FEL, 2007)


31 / 33

ˇ aritmetiky (9) Základní veta ˇ jak a, tak také b platí, že jeho prvoˇcíselný rozkPro celé cˇ íslo, které delí ˇ minimálneˇ mocninou vetšího ˇ lad je vytvoˇrený prvoˇcísly pi umocnený ze ˇ dvou cˇ ísel αi a βi ⇒ [a, b], nejmenší kladné celé cˇ íslo delitelné a a b je max (α1 ,β1 )

[a, b] = p1

max (α2 ,β2 )

· p2

max(αk ,βk )

· · · pk

,

ˇ cˇ íslo z cˇ ísel x, y . kde max(x, y ) oznaˇcuje vetší Prvoˇcíselný rozklad velkých celých cˇ ísel je cˇ asoveˇ nároˇcná operace ⇒ nalezení nejmenšího spoleˇcného násobku dvou celých cˇ ísel využívame GCD daných cˇ ísel. GCD lze lehce nalezt podle Euklidova algoritmu. ˇ 15 – pomocná Veta Když x a y jsou reálná cˇ ísla, potom min(x, y ) + max(x, y ) = x + y . ˇ Róbert Lórencz (CVUT FEL, 2007)


32 / 33

ˇ aritmetiky (10) Základní veta ˇ 16 Veta Když a a b jsou dveˇ kladná celá cˇ ísla, potom [a, b] =

a·b . gcd(a, b)

Dukaz: ˚ Necht’ a a b mají prvoˇcíselný rozklad a = p1α1 · p2α2 · · · pkαk , b = p1β1 · p2β2 · · · pkβk , kde exponenty αi ≥ 0 βi ≥ 0 jsou celá cˇ ísla. Oznaˇcme Mi = max(αi , βi ) a mi = min(αi , βi ). Potom [a, b] · gcd(a, b) = p1M1 · p2M2 · · · pkMk · p1m1 · p2m2 · · · pkmk , = p1M1 +m1 · p2M2 +m2 · · · pkMk +mk , = p1α1 +β1 · p2α2 +β2 · · · pkαk +βk , = p1α1 · p2α2 · · · pkαk · p1β1 · p2β2 · · · pkβk , = a·b . Využili jsme rovnosti Mi + mi = max(αi , βi ) + min(αi , βi ) = αi + βi , jejíž ˇ 15. platnost plyne z pomocné Vety ˇ Róbert Lórencz (CVUT FEL, 2007)


33 / 33

Y36BEZ Bezpečnost přenosu a zpracování dat. Úvod. Róbert Lórencz

Recommend Documents