Stęršfręšimynstur ķ tölvunarfręši

Vikublaš 9

Ķ nęstu viku veršur haldiš įfram meš venslin.

Ķ žessari viku žurfiš žiš ekki aš glķma viš skiladęmi, heldur getiš žiš spreytt ykkur į įhugaveršum verkefnum. Žiš žurfiš ekki aš skila žessum verkefnum, en viš munum fara yfir žau verkefni sem koma inn og velja 3-4 best leystu verkefnin. Žeir nemendur sem eiga žau verkefni fį ķ veršlaun einkunnina 10 fyrir öll eldri heimadęmi (ž.e. heimadęmi 1 til 8).

Hér aš nešan eru verkefnin. Veljiš eitt af žeim til aš gera og setjiš lausn ykkar fram į žann hįtt aš hęgt sé aš setja lausnina į heimasķšu nįmskeišsins ef hśn veršur fyrir valinu sem ein af įhugaveršustu lausnunum. Žiš getiš til dęmis sett lausnina fram sem Word skjal eša sem gagnvirka Vefsķšu.

Linuleg samleifarašferš

Eins og žiš muniš žį er lķnulega samleifarašferšin (e. linear congruential method, LCM) ein af žeim ašferšum sem notašar eru til aš bśa til gervislembitölur. Ašferšin notar formśluna x_n+1 = (ax_n + c) mod m. Ekki öll gildi į a, c og m gefa ašferš meš full lotu (ž.e. öll gildi frį 0 til m-1 koma fyrir sem slembitölur). Skošiš žetta val į stikunum a, c og m og hugiš sérstaklega aš eftirfarandi atrišum:

• Ef bśa ętti til slembitölugjafa sem gęfi 8 bita slembitölur, er hęgt aš finna gildi į a og c sem gefur fulla lotu ef viš festum m sem 256? Hvaš meš 16 bita slembitölur (ž.e. m = 65536)?
• Skošiš slembitölugjafann ķ Java (ž.e. Random klasann) og fullvissiš ykkur um aš hann gefi fulla lotu.
• Hvaš meš slembni (e. randomness) slembitölugjafans? Eru mismunandi gildi į a, c og m sem gefa mismunandi slembna gjafa?

RSA afkóšun

Ósamhverfa dulkóšunarašferšin RSA byggir į žvķ aš erfitt sé aš žįtta tölur. Hér fįiš žiš gefinn almenningslykil (n, e) įsamt skilabošum sem hafa veriš kóšuš meš honum. Žiš eigiš aš finna upphaflegu skilabošin meš žvķ aš finna fyrst einkalykilinn (n, d) śt frį almenningslyklinum og nota hann til aš afkóša skilabošin.
Lykilinn sem žiš fįiš er (221873272483254945141922353186910788703120217007463592538956281140602541064561, 65537). Hér er n 257-bita tala og e er 65537. Hér er n į sextįndakerfisformi: (01 EA87 D26D AE2B B5E4 DC33 6EE0 D994 DB82 FE49 F895 5D80 0E36 6B76 722C 1016 4171)₁₆. Žar sem n er 257-bita (ž.e. rśmlega 32 bęti) žį er hęgt aš kóda 32 bókstafi ķ einni tölu, sem er lęgri en n, ef viš skeytum saman ASCII-kódum stafanna. Skeytiš sem žiš eigiš aš reyna aš finna er kóšaš ķ tveimur 257-bita tölum. Žaš er žvķ į bilinu 33 til 64 stafir aš lengd. Tölurnar eru

• 104281735391995426127780900927647529412754004160490656811749030991653345899311
  eša (00 E68D 5EDF 3416 FF31 D5FC 22D5 2E24 26DC 5141 8733 85D4 18C7 AA7E 1368 3D23 332F)₁₆
• 171337256407249794293897175609924994722989505938960696638848588549637707305419
  eša (01 7ACD 7355 13A8 5617 B44C 69EA 00DD 8870 54C4 08AF 6E02 CEDA 268E D44E 7E3A 91CB)₁₆

Til žess aš žiš vitiš hvort žiš séuš į réttri leiš žį hefst skeytiš svona: "Nś ...". Fyrstu žrķr stafirnir eru žvķ 'N' (78), 'ś' (250) og ' ' (32). Skiliš lżsingu į ašferšinni sem žiš notušuš til žess aš brjóta upp ašferšina, įsamt lausninni aš sjįlfsögšu.

Athugiš aš nś eru yfirleitt notašir 1024-bita lyklar (ž.e. stęršin į n) ķ RSA, en žeir sem vilja meira öryggi nota 2048-bita lykla. Ykkur ętti žvķ ekki aš vera skotaskuld śr žvķ aš brjóta upp 257-bita lykil!

Hip

Leikurinn Hip er spilašur į NxN borši žar sem N er oddatala. Ķ upphafi er boršiš tómt, en leikmenn skiptast į aš leggja nišur steina, annar hefur hvķta steina, hinn svarta. Markmišiš ķ leiknum er aš komast hjį žvķ aš lįta 4 steina af sama lit mynda ferning į boršinu. Ferningur žarf ekki endilega aš vera samsķša hlišum boršsins. Hann gęti veriš halla (sjį myndir af ferningum). Žiš eigiš aš greina leikinn og skrifa skżrslu um žaš sem žiš komist aš.

• Reikniš śt fjölda mögulegra ferninga sem eru į NxN borši.
• Skošiš tilfellin N=5 og N=7. Er til įętlun fyrir annan leikmanninn sem tryggir honum sigur?
• Hversu marga mögulega leiki er um aš ręša (t.d. fyrir N=5 og N=7)?
• Hvernig lķtur leikjatré (e. game tree) (sjį bls. 651-656 ķ kennslubók) žessa leikjar śt (skošiš fyrstu lögin)?

Ķ dęmatķmum ķ nęstu viku (1.-2. nóv.) eigiš žiš aš reyna aš leysa valin dęmi śr efni nįmskeišsins hingaš til. Dęmatķmakennararnir munu ganga į milli og ašstoša, en munu ekki vera meš kennslu aš öšru leyti. Žiš žurfiš ekki aš męta ķ žessa tķma, en žaš er mikilvęgt fyrir žį sem hafa misst af einhverju efni, eša vilja sjį hvernig žeir standa aš nżta sér žetta tękifęri.

Dęmin sem leysa į ķ dęmatķmunum ķ nęstu viku verša tilkynnt sķšar.