Matematikai alapismeretek
Adatbiztons´ag el˝oad´as Huszti Andrea
Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
Tartalom
1
Matematikai alapismeretek Algebrai strukt´ ur´ak Oszthat´os´ag Kongruenci´ak
Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
Algebrai strukt´ur´ak
Defin´ıci´o Az S = {x, y , z, . . . } halmazban defini´alva van egy m˝ uvelet, ha az S-nek minden x, y elemp´arj´ahoz hozz´a van rendelve S-nek egy eleme. ´ aban Jel¨olj¨ uk ezt az elemet x ◦ y -nal, ahol a m˝ uvelet jele: ◦. Altal´ k´et m˝ uveletet k¨ ul¨onb¨oztet¨ unk meg, az ¨ osszead´ast ´es a szorz´ast.
Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
Defin´ıci´o A m˝ uveletet kommutat´ıvnak nevezz¨ uk, ha b´armely x, y ∈ S eset´en x ◦ y = y ◦ x. P´elda: Az ¨osszead´as is ´es a szorz´as is kommutat´ıv az eg´esz sz´amok k¨or´eben. Defin´ıci´o A m˝ uveletet asszociat´ıvnak nevezz¨ uk, ha b´armely x, y , z ∈ S eset´en (x ◦ y ) ◦ z = x ◦ (y ◦ z). P´elda: Az ¨osszead´as is ´es a szorz´as is asszociat´ıv az eg´esz sz´amok k¨or´eben.
Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
Defin´ıci´o Ha S-ben defini´alva van az ¨ osszead´as ´es szorz´as m˝ uvelete, ´es ha b´armely x, y , z ∈ S eset´en x · (y + z) = x · y + x · z ´es (y + z) · x = y · x + z · x teljes¨ ul, akkor a szorz´ast disztribut´ıvnak nevezz¨ uk az ¨osszead´asra n´ezve. P´elda: Az eg´esz sz´amok k¨ or´eben a szorz´as disztribut´ıv az ¨osszead´asra n´ezve.
Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
Defin´ıci´o Az S-nek valamely e elem´et egys´egelemnek vagy neutr´alis elemnek nevezz¨ uk, ha b´armely x ∈ S eset´en e ◦ x = x ◦ e = x. P´elda: Az eg´esz sz´amok halmaz´an szorz´as m˝ uvelet´ere n´ezve az egys´egelem az 1. Defin´ıci´o Ha S-ben l´etezik e egys´egelem, ´es ha az x elemhez l´etezik olyan y elem, hogy x ◦ y = y ◦ x = e, akkor y -t az x inverz´enek nevezz¨ uk. P´elda: A val´os sz´amok halmaz´aban 2 inverze 1/2. Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
Defin´ıci´o Egy S = {x, y , . . . } halmazt algebrai strukt´ ur´anak nevezz¨ uk, ha defini´alva van benne legal´abb egy m˝ uvelet.
Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
Defin´ıci´o Egy S halmaz f´elcsoport, ha defini´alva van benne egy asszociat´ıv m˝ uvelet. Egy S halmaz csoport, ha defini´alva van benne egy asszociat´ıv m˝ uvelet, l´etezik neutr´alis elem vagy egys´egelem, ´es minden elemnek l´etezik az inverze. Egy S halmaz Abel csoport, ha csoport ´es a m˝ uvelet kommutat´ıv is. Egy S halmaz gy˝ ur˝ u, ha defini´alva van az ¨ osszead´as ´es szorz´as m˝ uvelet, valamint a halmaz az ¨ osszead´asra n´ezve Abel csoport, szorz´asra n´ezve f´elcsoport ´es a szorz´as disztribut´ıv az ¨osszead´asra n´ezve. Az S kommutat´ıv, egys´egelemes gy˝ ur˝ u, ha a szorz´as kommutat´ıv, valamint l´etezik egys´egelem a szorz´asra n´ezve. Egy S halmaz test, ha kommutat´ıv, egys´egelemes gy˝ ur˝ u ´es minden nem 0 elemnek van inverze a szorz´as m˝ uvelet´ere n´ezve. Huszti Andrea Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
Oszthat´os´ag
Defin´ıci´o Az a eg´esz sz´amot egy b eg´esz sz´am oszt´ oj´anak nevezz¨ uk, ha l´etezik olyan q eg´esz sz´am, hogy b = a · q. Jel¨ ol´es: a|b. P´eld´ak: 3|12, 5|20, −3|9, 15| − 60, −2| − 10, 4 - 6, 5 - −2 Defin´ıci´o Egy sz´amot egys´egnek nevez¨ unk, ha minden sz´amnak oszt´oja. T´etel Az eg´esz sz´amok k¨or´eben k´et egys´eg van, az 1 ´es −1.
Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
T´etel (Oszthat´os´ag tulajdons´agai) 1
Minden a eg´esz sz´amra a|a (reflex´ıv).
2
Ha a|b ´es b|c, akkor a|c (tranzit´ıv).
3
Az a|b ´es b|a oszthat´ os´agok egyszerre akkor ´es csak akkor teljes¨ ulnek, ha az a sz´am a b sz´am egys´egszerese, azaz |a| = |b|. (nem szimmetrikus)
4
Ha a|b ´es a|c, akkor a|(r · b + s · c).
5
Ha a|b ´es b 6= 0, akkor |a| ≤ |b|.
Fontos megjegyezni, hogy az eg´esz sz´amok halmaz´an az oszthat´ os´ag nem szimmetrikus. A term´eszetes sz´amok halmaz´an az oszthat´os´ag antiszimmetrikus rel´aci´ o, hiszen a harmadik pontban lev˝o abszol´ ut ´ert´ek jelek elhagyhat´ ok. ´Igy az oszthat´os´ag a term´eszetes sz´amok halmaz´an rendez´esi rel´aci´ o, azaz reflex´ıv, tranzit´ıv ´es antiszimmetrikus. Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
T´etel (Marad´ekos oszt´as t´etele) Ha a, b ∈ Z ´es b 6= 0, akkor egy´ertelm˝ uen l´eteznek olyan q ∈ Z ´es r ∈ Z sz´amok, hogy a = b · q + r , ahol 0 ≤ r < |b|. Bizony´ıt´as Tekints¨ uk azt az esetet, amikor b > 0. A 0 ≤ r = a − bq < b felt´etel pontosan akkor teljes¨ ul, ha bq ≤ a < b(q + 1), azaz
a < q + 1. b Ilyen q ∈ Z pontosan egy l´etezik: q = b ba c, az ba (als´o) eg´eszr´esze, azaz a legnagyobb olyan eg´esz sz´am, amely m´eg kisebb vagy egyenl˝o, mint ba . q≤
Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
Ha b < 0, akkor a 0 ≤ r = a − bq < −b felt´etel pontosan akkor ´all fenn ha, q≥
a > q − 1, b
ami ism´et pontosan egy a q = d ba e eg´eszre ´all fenn, az ba fels˝o eg´eszr´esz´ere, azaz a legkisebb olyan eg´eszre, amely m´eg nagyobb vagy egyenl˝o, mint ba . 2 A marad´ekos oszt´as v´egrehajt´asa ut´an kapott q ´ert´eket h´anyadosnak, az r ´ert´eket pedig legkisebb nemnegat´ıv marad´eknak nevezz¨ uk. Amennyiben a marad´ek ´ert´eke 0, akkor b|a.
Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
P´eld´ak: 1
Legyen a = 19 ´es b = 5, ekkor 19 = 3 · 5 + 4, azaz q = 3 ´es r = 4.
2
Legyen a = 23 ´es b = −8, ekkor 23 = (−2) · (−8) + 7, azaz q = −2 ´es r = 7.
3
Legyen a = −23 ´es b = 8, ekkor −23 = (−3) · 8 + 1, azaz q = −3 ´es r = 1.
4
Legyen a = −28 ´es b = −9, ekkor −28 = 4 · (−9) + 8, azaz q = 4 ´es r = 8.
Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
Defin´ıci´o Legyenek a ´es b eg´esz sz´amok, ekkor az a ´es b legnagyobb k¨oz¨os oszt´oja d, ha d|a, d|b ´es ∀c ∈ Z eset´en, ha c|a ´es c|b teljes¨ ul, akkor c|d. Jel¨ol´es: (a, b) P´eld´ak: Legyen a = 100 ´es b = 35, ekkor a ´es b k¨oz¨os oszt´oi: −5, −1, 1, 5. A fenti defin´ıci´ o szerint a legnagyobb k¨oz¨os oszt´ok −5, 5. Pozit´ıv eg´esz sz´amok halmaz´an: (100, 35) = 5. Amennyiben a = b = 0, akkor defin´ıci´ o szerint (a, b) = 0.
Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
T´etel B´armely k´et eg´esz sz´amnak l´etezik legnagyobb k¨ oz¨os oszt´oja. Bizony´ıt´as Ha a = b = 0, akkor defin´ıci´ o szerint l´etezik a legnagyobb k¨oz¨os oszt´o, m´egpedig (a, b) = 0. Ha a 6= 0 ´es b = 0, akkor a legnagyobb k¨oz¨os oszt´ok a, −a, illetve ha a = 0 ´es b 6= 0, akkor b, −b. A tov´abbiakban tegy¨ uk fel, hogy a ´es b null´at´ ol k¨ ul¨ onb¨oz˝o eg´esz sz´amok ´es |a| > |b|. Ha b|a, akkor a legnagyobb k¨oz¨os oszt´ok: b, −b.
Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
Ha b - a, akkor a marad´ekos oszt´as t´etele miatt egy´ertelm˝ uen l´eteznek qi ´es ri eg´eszek, ahol i = 0, . . . , n, hogy a = b · q1 + r2 , ahol 0 < r2 < |b|, b = r2 · q2 + r3 , ahol 0 < r3 < r2 , r2 = r3 · q3 + r4 , ahol 0 < r4 < r3 , .. . rn−2 = rn−1 · qn−1 + rn , ahol 0 < rn < rn−1 , rn−1 = rn · qn , ahol rn+1 = 0. Az el˝obbi elj´ar´as b´armely null´at´ ol k¨ ul¨ onb¨ oz˝ o a, b eg´eszek eset´en v´eges sok l´ep´es ut´an befejez˝ odik, hiszen a marad´ekok nemnegat´ıv eg´eszekb˝ol ´all´o szigor´ uan monoton cs¨ okken˝ o sorozatot alkotnak. |b| > r2 > · · · > rn > 0. Teh´at rn mindig l´etezik. Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
Bel´atjuk, hogy rn az egyik legnagyobb k¨ oz¨ os oszt´ o. A defin´ıci´o szerint k´et dolgot kell igazolnunk: 1 r |a ´ es rn |b n Az algoritmuson alulr´ ol felfel´e haladunk. Tekints¨ uk az algoritmus utols´o sor´at. Trivi´alis, hogy rn |rn−1 . Az utols´o el˝otti sor alapj´an: rn |rn−2 . Ugyanis, ha rn |rn ´es rn |rn−1 , akkor rn |rn−2 . Ugyan´ıgy folytatva megkapjuk a m´asodik, illetve az els˝o sor alapj´an, hogy rn |b ´es rn |a. 2 ∀c eset´ en, ha c|a ´es c|b, akkor c|rn Az algoritmuson fel¨ ulr˝ ol lefel´e haladunk. Az els˝o sor alapj´an, ha c|a ´es c|b, ∀c ∈ Z eset´en, akkor c|(a − b · q1 ), azaz c|r2 . A m´asodik sor szerint, ha c|b ´es c|r2 , akkor c|r3 . Ugyan´ıgy folytatva, az utols´ o sor alapj´an c|rn . A fenti bizony´ıt´as konstrukt´ıv, azaz a bizony´ıt´as sor´an egy algoritmust adtunk az egyik legnagyobb k¨ oz¨ os oszt´o kisz´am´ıt´as´ara. Ez az algoritmus az euklideszi algoritmus. A m´asik legnagyobb k¨oz¨os oszt´o a (−rn ). 2 Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
T´etel Az a ´es b k´et eg´esz sz´am legnagyobb k¨ oz¨ os oszt´ oja alkalmas x, y ∈ Z sz´amokkal kifejezhet˝ o (a, b) = a · x + b · y alakban. A m´ar ismertett euklideszi algoritmust b˝ ov´ıtj¨ uk ki xi ´es yi ´ert´ekekkel, ahol i = 0, . . . , n. Legyen x0 = 1, x1 = 0, y0 = 0, y1 = 1 ´es xi+1 = xi qi + xi−1 , yi+1 = yi qi + yi−1 . (−1)n x
Az x = es y = (−1)n+1 yn n ´ A bizony´ıt´as konstrukt´ıv. Az algoritmust kib˝ ov´ıtett euklideszi algoritmusnak nevezz¨ uk. Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
oz¨ os oszt´oj´at a sz´amok P´elda: ´Irjuk fel a 112 ´es a 63 legnagyobb k¨ line´aris kombin´aci´ojak´ent. A megold´ast a k¨ovetkez˝ o t´abl´azat seg´ıts´eg´evel adjuk meg: k rk qk xk yk
0 112 1 0
1 63 1 0 1
2 49 1 1 1
3 14 3 1 2
4 7 2 4 7
5 0 -
A t´abl´azat alapj´an az utols´ o nemnulla marad´ek r4 = 7, teh´at n = 4. A legnagyobb k¨ oz¨ os oszt´ ok egyike: (112, 63) = 7. x = (−1)4 x4 = 4, y = (−1)5 y4 = −7. A megold´as a kapott ´ert´ekekb˝ol: 7 = 112 · 4 + 63 · (−7).
Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
Defin´ıci´o Az a1 , a2 ,. . . , an sz´amok relat´ıv pr´ımek, ha nincs egys´egt˝ol k¨ ul¨onb¨oz˝o k¨oz¨os oszt´ojuk, azaz (a1 , a2 , . . . , an ) = 1. P´elda: 5, −3, 15, −56 sz´amok relat´ıv pr´ımek. Defin´ıci´o Az a1 , a2 , . . . , an sz´amok p´aronk´ent relat´ıv pr´ımek, ha b´armely kett˝o legnagyobb k¨oz¨os oszt´ oja 1, azaz minden 1 ≤ i 6= j ≤ k eset´en, (ai , aj ) = 1.
Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
Defin´ıci´o A p egys´egt˝ol ´es null´at´ ol k¨ ul¨ onb¨ oz˝ o sz´amot pr´ımsz´amnak (vagy pr´ımnek) nevezz¨ uk, ha csak u ´gy lehet oszt´ oja k´et eg´esz sz´am szorzat´anak, ha legal´abb az egyik t´enyez˝ onek oszt´oja. Azaz p|ab =⇒ p|a vagy p|b. Minden a ∈ Z sz´amnak oszt´ oja az 1, a, −1, −a. Ezeket trivi´alis oszt´oknak nevezz¨ uk. A nem trivi´alis oszt´ ok a val´ odi oszt´ok. Defin´ıci´o A p egys´egt˝ol (´es null´at´ ol) k¨ ul¨ onb¨ oz˝ o sz´amot felbonthatatlan (irreducibilis) sz´amnak nevezz¨ uk, ha csak u ´gy bonthat´o fel k´et eg´esz sz´am szorzat´ara, hogy valamelyik t´enyez˝ o egys´eg. Azaz p = ab =⇒ a vagy b egys´eg.
Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
T´etel Az eg´esz sz´amok k¨or´eben p akkor ´es csak akkor pr´ım, ha felbonthatatlan. T´etel Minden null´at´ol ´es egys´egt˝ ol k¨ ul¨ onb¨ oz˝ o eg´esz sz´amnak l´etezik felbonthatatlan oszt´oja. A k¨ovetkez˝o t´etel a sz´amelm´elet alapt´etel´et mondja ki. T´etel Minden, a null´at´ol ´es egys´egekt˝ ol k¨ ul¨ onb¨ oz˝ o eg´esz sz´am felbonthat´o v´eges sok felbonthatatlan sz´am szorzat´ara, ´es ez a felbont´as a t´enyez˝ok sorrendj´et˝ ol ´es egys´egszeresekt˝ol eltekintve egy´ertelm˝ u.
Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
Kongruenci´ak
Defin´ıci´o Legyenek a ´es b eg´esz sz´amok ´es m pozit´ıv eg´esz. Azt mondjuk, hogy a kongruens b-vel modulo m, ha m|a − b. Jel¨ol´es: a ≡ b (mod m) Az m sz´amot modulusnak nevezz¨ uk. K´et sz´am pontosan akkor kongruens modulo m, ha m-mel osztva ugyanazt a marad´ekot adj´ak Amennyiben a ´es b nem kongruensek modulo m, akkor a ´es b inkongruensek modulo m, jel¨ ol´ese: a 6≡ b (mod m) P´eld´ak: 13 ≡ 8 (mod 5), 25 ≡ −10 (mod 7), 25 6≡ 10 (mod 7)
Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
Ekvivalenciarel´aci´o T´etel A kongruencia (mod m) ekvivalenciarel´aci´ o. Bizony´ıt´as Azt kell igazolnunk, hogy a kongruencia reflex´ıv, szimmetrikus ´es tranzit´ıv rel´aci´o. A kongruencia rel´aci´ o reflex´ıv: ∀a ∈ Z, a ≡ a (mod m), hiszen m|a − a. szimmetrikus: Ha a ≡ b (mod m), akkor b ≡ a (mod m) teljes¨ ul, mert ha m|a − b, akkor m|b − a is. tranzit´ıv: Ha a ≡ b (mod m) ´es b ≡ c (mod m), akkor m|a − b ´es m|b − c. Az el˝ obbiek alapj´an m|(a − b) + (b − c), azaz m|a − c. Ezzel bel´attuk, hogy ha a ≡ b (mod m) ´es b ≡ c (mod m), akkor a ≡ c (mod m). 2 Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
Marad´ekoszt´alyok T´etel 1 Ha a ≡ b (mod m) ´ es c ≡ d (mod m), akkor a + c ≡ b + d (mod m) ´es a − c ≡ b − d (mod m). 2
3 4
Ha a ≡ b (mod m) ´es c ≡ d (mod m), akkor ac ≡ bd (mod m) Ha a ≡ b (mod m), akkor an ≡ b n (mod m) Legyen d = (mod d).
m (c,m) .
Ha ac ≡ bc (mod m), akkor a ≡ b
Defin´ıci´o Ha a ∈ Z, akkor az a-val kongruens (mod m) eg´esz sz´amok halmaz´at az a ´altal reprezent´alt (mod m) marad´ ekoszt´ alynak nevezz¨ uk. Jel¨ol´es: (a)m Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
Marad´ekrendszerek Defin´ıci´o Ha r¨ogz´ıtett m modulus mellett minden egyes marad´ekoszt´alyb´ol pontosan egy elemet vesz¨ unk, akkor modulo m teljes marad´ ekrendszert kapunk. Defin´ıci´o Az (a)m marad´ekoszt´aly reduk´ alt marad´ ekoszt´ aly, ha (a, m) = 1. Defin´ıci´o Ha egy r¨ogz´ıtett m modulus mellett minden egyes reduk´alt marad´ekoszt´alyb´ol pontosan egy elemet vesz¨ unk, akkor reduk´ alt marad´ ekrendszert kapunk.
Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
T´etel Adott eg´esz sz´amok pontosan akkor alkotnak modulo m teljes marad´ekrendszert, ha 1
sz´amuk m ´es
2
p´aronk´ent inkongruensek modulo m.
Defin´ıci´o (Euler-f´ele ϕ f¨ uggv´eny) Tetsz˝oleges n pozit´ıv eg´esz eset´en ϕ(n) jel¨ oli az 1, 2, . . . , n sz´amok k¨oz¨ ul az n-hez relat´ıv pr´ımek sz´am´at. T´etel ϕ(n) = n
Yp−1 p|n
p
, ahol p pr´ım.
Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
T´etel Adott sz´amok egy r¨ogz´ıtett m modulus mellett pontosan akkor alkotnak reduk´alt marad´ekrendszert, ha 1
sz´amuk ϕ(m),
2
p´aronk´ent inkongruensek modulo m, ´es
3
valamennyien relat´ıv pr´ımek m-hez.
T´etel Legyen r1 , r2 , . . . , rϕ(m) reduk´alt marad´ekrendszer modulo m ´es (a, m) = 1. Ekkor arl , ar2 , . . . , arϕ(m) is reduk´alt marad´ekrendszer modulo m.
Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
Euler-Fermat t´etel T´etel Ha (a, m) = 1, akkor aϕ(m) ≡ 1 (mod m). Bizony´ıt´as Legyen r1 , r2 , . . . , rϕ(m) egy reduk´alt marad´ekrendszer (mod m), ekkor ar1 , ar2 , . . . , arϕ(m) is reduk´alt marad´ekrendszer (mod m). Ebb˝ol k¨ovetkezik, hogy minden ari -hez l´etezik egy ´es csak egy rj , hogy ari ≡ rj (mod m), tov´abb´a k¨ ul¨ onb¨ oz˝ o ari - khez k¨ ul¨onb¨oz˝o elemek tartoznak az eredeti reduk´alt marad´ekrendszerb˝ol. Teh´at a k¨ovetkez˝ot kapjuk: ar1 ≡ s1 (mod m), ar2 ≡ s2
(mod m), .. .
arϕ(m) ≡ sϕ(m)
(mod m),
Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
Euler-Fermat t´etel
ahol s1 , s2 , . . . , sϕ(m) az r1 , r2 , . . . , rϕ(m) egy permut´aci´oja. Most szorozzuk ¨ossze ezeket a kongruenci´akat: aϕ(m) r1 r2 · · · · · rϕ(m) ≡ r1 r2 · · · · · rϕ(m) (mod m). Ha egyszer˝ us´ıt¨ unk r1 r2 · · · · · rϕ(m) -mel, amely m-hez relat´ıv pr´ım, kapjuk, hogy aϕ(m) ≡ 1 (mod m). 2 T´etel (kis Fermat t´etel) 1
Ha p pr´ımsz´am, a ∈ Z ´es p - a, akkor ap−1 ≡ 1 (mod p).
2
Ha p pr´ımsz´am ´es a ∈ Z, akkor ap ≡ a (mod p).
Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
Line´aris kongruenci´ak
Defin´ıci´o Ha a, b ∈ Z ´es m pozit´ıv eg´esz, akkor az ax ≡ b (mod m) kongruenci´at line´ aris kongruenci´ anak nevezz¨ uk. A kongruencia megold´asai olyan eg´esz sz´amok, melyeket x hely´ebe ´ırva a kongruencia teljes¨ ul. Megold´asok sz´am´an a k¨ ul¨onb¨oz˝o marad´ekoszt´alyok sz´am´at ´ertj¨ uk, melyekb˝ ol vett eg´eszek a kongruenci´at kiel´eg´ıtik. T´etel Ha a, b ∈ Z ´es m pozit´ıv eg´esz, az ax ≡ b (mod m) line´aris kongruencia akkor ´es csak akkor oldhat´ o meg, ha (a, m) | b.
Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
Line´aris kongruenci´ak
T´etel Ha a, b ∈ Z, az m pozit´ıv eg´esz ´es az ax ≡ b (mod m) line´aris kongruencia megoldhat´ o, akkor a megold´asok sz´ama (a, m). Amennyiben (y )m megold´asa a kongruenci´anak, akkor az ¨osszes megold´ast az y, y +
m m m , y +2· , . . . , y + ((a, m) − 1) · (a, m) (a, m) (a, m)
elemek ´altal reprezent´alt marad´ekoszt´alyok alkotj´ak.
Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
T´etel Ha (a, m) = 1, akkor az ax ≡ b (mod m) line´aris kongruencia egyetlen megold´asa x ≡ aϕ(m)−1 · b (mod m). Bizony´ıt´as Ha x ≡ aϕ(m)−1 · b (mod m), akkor x val´ oban megold´as, hiszen az Euler-Fermat t´etel szerint aaϕ(m)−1 · b ≡ b (mod m). 2
Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
Szimult´an kongruenciarendszer Defin´ıci´o Ha ugyanazon ismeretlenre t¨ obb k¨ ul¨ onb¨ oz˝ o modulus´ u kongrueciafelt´etelt adunk, akkor szimult´ an kongruenciarendszert kapunk. T´etel Az x ≡ y1
(mod m)
x ≡ y2
(mod n)
szimult´an kongruenciarendszer megoldhat´ os´ag´anak sz¨ uks´eges ´es el´egs´eges felt´etele, hogy (m, n) | y1 − y2 . Az ¨ osszes megold´as egy marad´ekoszt´alyt alkot modulo [m, n]. Az [m, n] az m ´es n modulusok legkisebb k¨ oz¨ os t¨ obbsz¨or¨os´et jel¨oli. Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
K´ınai marad´ekt´etel T´etel Legyenek m1 , m2 , . . . , mk p´aronk´ent relat´ıv pr´ımek. Ekkor x ≡ y1
(mod m1 )
x ≡ y2
(mod m2 ) .. .
x ≡ yk
(mod mk )
szimult´an kongruenciarendszer b´armilyen y1 , y2 , · · · , yk eg´eszek eset´en megoldhat´o, ´es a megold´asok egyetlen marad´ekoszt´alyt alkotnak modulo m1 m2 · · · · · mk .
Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
K´ınai marad´ekt´etel Bizony´ıt´as M , ahol i = 1, 2, . . . , k. Legyen M = m1 m2 · · · · · mk ´es Mi = m i Mivel az m1 , . . . , mk modulusok p´aronk´ent relat´ıv pr´ımek, ez´ert (Mi , mi ) = 1, i = 1, 2, . . . , k. Tekints¨ uk az Mi · x ≡ 1 (mod mi ), ahol i = 1, 2, . . . , k kongruenci´akat. B´armely i eset´en a kongruencia megoldhat´ o, hiszen (Mi , mi ) = 1, legyen x ≡ ci (mod mi ) a megold´as. Ekkor Mi · ci ≡ 1 (mod mi ) ´es Mi · ci ≡ 0 (mod mj ), ahol i 6= j. Legyen x0 ≡
k X
Mi ci yi
(mod M).
i=1
Az el˝obbiek alapj´an x0 ≡ yi (mod mi ), i = 1, . . . , k, teh´at x0 megold´asa a szimult´an kongruenciarendszernek. Ezzel egy konstrukt´ıv bizony´ıt´ast adtunk a megold´as l´etez´es´ere. Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
Most l´assuk be, hogy csak egy megold´asa van. Tegy¨ uk fel, hogy x00 szint´en megold´asa a szimult´an kongruenciarendszernek. ´Igy x00 ≡ yi (mod mi ), i = 1, 2, . . . , k, azaz mi | x00 − yi , b´armely i-re. Ugyanakkor x0 szint´en megold´as, teh´at mi | x0 − yi , ahonnan mi | x00 − x0 b´armely i-re. Ha az el˝ obbi oszthat´ os´ag tetsz˝oleges i ∈ {1, 2, . . . , k}-re teljes¨ ul, akkor m1 m2 · · · · · mk | x00 − x0 is ´all, azaz m | x00 − x0 , ´ıgy x00 ≡ x0 (mod M). Teh´at x00 ´es x0 megold´asok egy marad´ekoszt´alyba esnek modulo M. 2
Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
Algebrai strukt´ura
Defin´ıci´o Az (a)m ´es (b)m marad´ekoszt´alyok ¨ osszeg´en az (a + b)m , szorzat´an pedig az (ab)m marad´ekoszt´alyt ´ertj¨ uk, azaz (a)m + (b)m = (a + b)m ´es (a)m · (b)m = (ab)m . B´armely k´et modulo m marad´ekoszt´aly ¨ osszege, illetve szorzata egy´ertelm˝ uen meghat´arozott.
Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
Kommutat´ıv, egys´egelemes gy˝ur˝u T´etel A modulo m marad´ekoszt´alyok eset´en az ¨osszead´as asszociat´ıv ´es kommutat´ıv, a (0)m nullelem, azaz minden (a)m -ra (0)m + (a)m = (a)m + (0)m = (a)m , az (a)m ellentettje (−a)m , azaz (−a)m + (a)m = (a)m + (−a)m = (0)m , a szorz´as asszociat´ıv ´es kommutat´ıv, az (1)m egys´egelem, azaz minden (a)m -ra (1)m · (a)m = (a)m · (1)m = (a)m , ´erv´enyes a disztributivit´as. K¨onnyen l´athat´o, hogy amennyiben a modulus pr´ım, akkor a modulo m marad´ekoszt´alyok halmaza testet alkot. Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
Defin´ıci´o Legyen (a, m) = 1. Az a elem rendj´ enek nevezz¨ uk modulo m azt k i a k kitev˝ot, melyre a ≡ 1 (mod m), ´es a 6≡ 1 (mod m) b´armely i-re, ahol i = 1, 2, . . . , k − 1. Az elem rendj´et om (a)-val jel¨ olj¨ uk. Az Euler-Fermat t´etelb˝ol k¨ovetkezik, hogy om (a) ≤ φ(m). Defin´ıci´o Egy g sz´amot primit´ıv gy¨ oknek nevez¨ unk modulo m, ha om (g ) = φ(m). Defin´ıci´o Legyen g primit´ıv gy¨ok modulo p, ahol p pr´ım ´es (a, p) = 1. Ekkor a-nak g alap´ u diszkr´ et logaritmus´an azt a 0 ≤ k ≤ p − 2 sz´amot ´ertj¨ uk, melyre a ≡ g k (mod p). Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
Matematikai alapismeretek
Defin´ıci´o Egy S csoport ciklikus, ha egy elemmel gener´alhat´o. Tegy¨ uk fel, hogy S ciklikus csoport a szorz´asra n´ezve, ´es az x elem seg´ıts´eg´evel gener´alhat´ o. Ezek szerint S minden eleme fel´ırhat´o x 0 = e, x 1 , x −1 , x 2 , x −2 , x 3 , x −3 , . . . alakban. K´et esetet k¨ ul¨onb¨oztet¨ unk meg: 1
2
V´egtelen ciklikus csoportr´ ol besz´el¨ unk, ha x 0 = e, x 1 , x −1 , x 2 , x −2 , x 3 , x −3 , . . . elemek mind k¨ ul¨onb¨oz˝oek. V´eges ciklikus csoportr´ ol besz´el¨ unk, ha x hatv´anyai nem mind k¨ ul¨onb¨oz˝oek. Ekkor l´etezik olyan k ´es l, hogy x k = x l . Legyen k > l, ekkor x k−l = e. Ami azt jelenti, hogy x-et k − l-edik hatv´anyra emelve egys´eget kapunk. Legyen n a legkisebb pozit´ıv eg´esz, melyre x n = e. Ekkor e, x, x 2 , x 3 , . . . , x n−1 elemek mind k¨ ul¨ onb¨ oznek ´es a csoport b´armely eleme ezek egyik´evel egyenl˝o. Huszti Andrea
Adatbiztons´ ag el˝ oad´ as
