Aplikimi i kongruencave

Aplikimi i Kongruencave

Teoria e numrave ka aplikime në një gamë të gjerë fushash. Ne do të prezantojmë tre nga aplikimet e shumëta: përdorimin e kongruencave për të caktuar vendndodhjet e memories për skedarët e kompjuterit, gjenerimin e numrave pseudorandom dhe kriptosistemet bazuar në aritmetikën modulare.

Funksionet Hashing

Kompjuteri qendror në një kompani sigurimesh mban të dhëna për secilin prej klientëve të saj. Si mund të caktohen vendndodhjet e memories në mënyrë që të dhënat e klientit të mund të merren shpejt? Zgjidhja për këtë problem është përdorimi i një funksioni hash të zgjedhur në mënyrë të përshtatshme. Regjistrimet identifikohen duke përdorur një çelës, i cili identifikon në mënyrë unike të dhënat e secilit klient. Për shembull, të dhënat e klientit shpesh identifikohen duke përdorur numrin e Sigurimeve Shoqërore të klientit si çelës. Një funksion hash h cakton vendndodhjen e memories h(k) në rekordin që ka k si çelës. Në praktikë, përdoren shumë funksione të ndryshme hashing. Një nga më të zakonshmet është funksioni
h(k) = k mod m
ku m është numri i vendndodhjeve të disponueshme të memories.
Funksionet hash duhet të përcaktohen ashtu që skedarët të mund të gjenden shpejtë. Funksioni hash h(k) = k mod m plotëson këtë kërkesë; për të gjetur h(k), na duhet vetëm të llogarisim mbetjen kur k pjesëtohet me m. Për më tepër, funksioni hash duhet të plotësoj kushtin, që të gjitha vendndodhjet e kujtesës të jenë të mundshme. Funksioni h(k) = k mod m gjithashtu e plotëson këtë veti.

Shembulli 1:

Gjeni vendndodhjet e memories të caktuara nga funksioni hash h(k) = k mod 111 në të dhënat e klientëve me numrat e Sigurimeve Shoqërore 064212848 dhe 037149212.

Zgjidhje:

Të dhënat e klientit me numër të sigurimeve shoqërore 064212848 është caktuar në vendndodhjen e memories 14, sepse
h(064212848) = 064212848 mod 111 = 14.
Në mënyrë të ngjashme, sepse
h(037149212) = 037149212 mod 111 = 65,
në memorie caktohet rekordi i klientit me numër sigurimesh 037149212 vendndodhja 65.
Për shkak se një funksion hash nuk është një-për-një (sepse ka më shumë çelësa të mundshëm sesa vendndodhje të memories), më shumë se një skedar mund t'i caktohet një vendndodhjeje memorie. Kur kjo ndodh, themi se ndodh një përplasje. Një mënyrë për të zgjidhur një përplasje është caktimi i vendndodhjes së parë të lirë pas vendndodhjes së memories së zënë të caktuar nga funksioni hash.

Shembulli 2:

Pasi të keni bërë caktimet e të dhënave në vendndodhjet e memories në Shembullin 1, caktoni një vendndodhje memorie në rekordin e klientit me numrin e Sigurimeve Shoqërore 107405723.

Zgjidhje:

Vini re fillimisht se funksioni hash h(k) = k mod 111 harton numrin e Sigurimeve Shoqërore 107405723 në vendndodhjen 14, sepse
h(107405723) = 107405723 mod 111 = 14.
Megjithatë, ky vend është tashmë i zënë (nga dosja e klientit me numër të Sigurimeve Shoqërore 064212848). Por, për shkak se vendndodhja e memories 15, vendndodhja e parë pas vendndodhjes së memories 14, është e lirë, ne caktojmë regjistrimin e klientit me numrin e Sigurimeve Shoqërore 107405723 në këtë vendndodhje.
Kjo ishte njëra nga mënyrat për zgjidhjen e përplasjeve që u përmend në shembullin 1, pra caktimi i memories së parë të lirë pas vendndodhjes së memories të zënë.

Numrat Pseudorandom

Numrat e zgjedhur rastësisht (Numrat pseudorandom) shpesh nevojiten për simulimet kompjuterike. Janë krijuar metoda të ndryshme për gjenerimin e numrave që kanë vetitë e numrave të zgjedhur rastësisht. Për shkak se numrat e gjeneruar nga metoda sistematike nuk janë vërtet të rastësishme, ata quhen
numra pseudorandom.
Procedura më e përdorur për gjenerimin e numrave pseudorandom është metoda lineare kongruente. Ne zgjedhim katër numra të plotë: modulin m, shumëzuesin a, rritjen c dhe fara x0 (është një numër (ose vektor) i përdorur për të inicializuar një gjenerues numrash pseudorandom),
me 2 ≤ a < m, 0 ≤ c < m dhe 0 ≤ x0 < m. Ne gjenerojmë një sekuencë numrash pseudorandom {xn}, me 0 ≤ xn < m për të gjithë n, duke përdorur në mënyrë të njëpasnjëshme funksionin e përcaktuar në mënyrë rekursive.
x_n+1 = (ax_n + c) mod m.
Shumë eksperimente kompjuterike kërkojnë gjenerimin e numrave pseudorandom midis 0 dhe 1. Për të gjeneruar numra të tillë, ne i ndajmë numrat e gjeneruar me një gjenerator kongruencial linear me modulin: domethënë, përdorim numrat x_n∕m.

Shembulli 1:

Gjeni sekuencën e numrave pseudorandom të gjeneruar nga metoda kongruente lineare me modulin m = 9, shumëzuesin a = 7, rritjen c = 4 dhe farën x0 = 3.

Zgjidhje :

Ne llogarisim termat e kësaj sekuence duke përdorur në mënyrë të njëpasnjëshme funksionin e përcaktuar në mënyrë rekursive x_n+1 = (7x_n + 4) mod 9, duke filluar duke futur farën(vektorin) x₀ = 3 për të gjetur x₁. Do të fitojmë
x₁ = 7x₀ + 4 mod 9 = 7 ⋅ 3 + 4 mod 9 = 25 mod 9 = 7,
x₂ = 7x₁ + 4 mod 9 = 7 ⋅ 7 + 4 mod 9 = 53 mod 9 = 8,
x₃ = 7x₂ + 4 mod 9 = 7 ⋅ 8 + 4 mod 9 = 60 mod 9 = 6,
x₄ = 7x₃ + 4 mod 9 = 7 ⋅ 6 + 4 mod 9 = 46 mod 9 = 1,
x₅ = 7x₄ + 4 mod 9 = 7 ⋅ 1 + 4 mod 9 = 11 mod 9 = 2,
x₆ = 7x₅ + 4 mod 9 = 7 ⋅ 2 + 4 mod 9 = 18 mod 9 = 0,
x₇ = 7x₆ + 4 mod 9 = 7 ⋅ 0 + 4 mod 9 = 4 mod 9 = 4,
x₈ = 7x₇ + 4 mod 9 = 7 ⋅ 4 + 4 mod 9 = 32 mod 9 = 5,
x₉ = 7x₈ + 4 mod 9 = 7 ⋅ 5 + 4 mod 9 = 39 mod 9 = 3.
Për shkak se x₉ = x₀ dhe për shkak se çdo term varet vetëm nga termi i mëparshëm, ne shohim se sekuenca
3, 7, 8, 6, 1, 2, 0, 4, 5, 3, 7, 8, 6, 1, 2, 0, 4, 5, 3, ...
është gjeneruar. Kjo sekuencë përmban nëntë numra të ndryshëm përpara se të përsëritet.
Shumica e kompjuterëve përdorin gjeneratorë kongruentë linearë për të gjeneruar numra pseudorandom. Shpesh, përdoret një gjenerator kongruencial linear me rritje c = 0. Një gjenerator i tillë quhet gjenerator i pastër shumëzues. Për shembull, gjeneratori i pastër shumëzues me modul 2³¹ − 1 dhe shumëzuesi 7⁵ = 16,807 përdoret gjerësisht. Me këto vlera mund të tregohet se 2³¹ − 2 numra gjenerohen përpara se të fillojë përsëritja.

Kriptologjia

Një nga aplikimet më të rëndësishme të kongruencave përfshin kriptologjinë, e cila është studimi i mesazheve sekrete. Një nga përdorimet më të hershme të njohura të kriptologjisë u bë nga Julius Caesar. Metoda e Caesar zhvendoste secilën shkronjë për tre shkronja përpara në alfabet(B shkon te E kurse X te A). Kjo ishte mënyra e enkriptimit, që do të thotë, procesi i bërjes së një mesazhi sekret.
Enkripitimi sipas metodës së Caesar shprehet matematikisht duke zëvendësuar së pari secilën shkronjë me një numër nga 0-25, bazuar në renditjen në alfabet. Për shembull, A zëvendsohet me 0, K me 10, dhe Z me 25. Metoda e enkriptimit mund të paraqitet me anë të funksionit f që caktohet nga numri jonegativ p, p≤25, numri f (p) në bashkësinë
{0,1,2,...,25} me
f (p)= (p + 3) mod 26
Në versionin e enkriptuar të mesazhit, shkronja e prezentuar me p zëvendsohet nga shkronja (p + 3) mod 26.

Shembulli 1:

Cili është mesazhi sekret që fitohet nga mesazhi "MEET YOU IN THE PARK" duke përdorur shifrimin sipas Caesar?

Zgjidhje :

Së pari zëvendsojmë shkronjat e mesazhit me numra, fitojmë
MEET = 12 4 4 19 , YOU = 24 14 20 , IN = 8 13 , THE = 19 7 4 , PARK = 15 0 17 10 .
Tani zëvendsojmë secilin nga këta numëra p, me f (p) = (p + 3) mod 26. Fitojmë
MEET = 15 7 7 22 , YOU = 1 17 23 , IN = 11 16 , THE = 22 10 7 , PARK = 18 3 20 13 .
I zëvendsojmë numrat me shkronja në bazë të alfabetit, fitojmë mesazhin e enkriptuar
PHHW BRX LQ WKH SDUN
Dekriptimi i një mesazhi të enkriptuar me metodën e Caesar bëhet duke gjetur f ^-1 . Pra praktikisht shkronjat që janë në mesazhin e enkriptuar i kthejmë në numra p në bazë të renditjes së alfabetit, pastaj i zbresim për tre (p - 3) mod 26 .
Në ditët e sotme përdoren metoda enkriptimi më të sofistikuara, pasi që metoda e Caesar është lehtë e dekriptueshme. Metodat e sotme zëvendsojnë blloqe të shkronjave me blloqe të shkronjave, në atë mënyrë që ti bëjnë ballë sulmit brute-force.

Discrete Mathematics and Its Applications By Kenneth H. Rosen Fourth Edition Arkivuar 20 shkurt 2017 tek Wayback MachineDiscrete Mathematics and Its Applications By Kenneth H. Rosen Seventh Edition Arkivuar 20 shkurt 2017 tek Wayback Machine