Jos käytettävissä on arpanoppia joissa kussakin silmäluvut 1 - 6 niin miten näitä heittelemällä saisi aikaan aidosti satunnaisia lukuja esim. välillä 1 - 26 tasaisella jakautumalla?
Se ei mene niin että heitää esim. 5 noppaa ja laskee silmäluvut yhteen. Ei sittenkään vaikka muista paitsi yhdestä nopasta vähentäisi silmäluvusta yhden niin että myös summa 1 ( = 1 0 0 0 0 ) ja 26 ( = 6 5 5 5 5 ) on mahdollinen.
Kaikkien summien pitäisi olla yhtä todennäköisiä ja aidosti satunnaisia.
Se ei mene niin että heitää esim. 5 noppaa ja laskee silmäluvut yhteen. Ei sittenkään vaikka muista paitsi yhdestä nopasta vähentäisi silmäluvusta yhden niin että myös summa 1 ( = 1 0 0 0 0 ) ja 26 ( = 6 5 5 5 5 ) on mahdollinen.
Kaikkien summien pitäisi olla yhtä todennäköisiä ja aidosti satunnaisia.
Vastaukset 18
Vanhimmat
ekalla nopalla arvotaan luvun ryhmä
silmät ; ryhmä
1 ; 1 ... 6
2 ; 7 .... 12
3 ; 13 ... 18
4 ; 19 ... 24
5 ; 25 ... 26
6 ; hylätään, uusi yritys
Tokalla nopalla arvotaan ryhmän "pohjalukuun" lisättävä luku yhdellä vähennettynä. Jos menee yli 26:n niin hylätään ja yritetään uudelleen.
Esim.
I. Eka noppa 6, hylätään
II. Eka noppa 5, toka noppa 3, hylätään koska 25 3 - 1 > 26
III. Eka noppa 4, toka noppa 6, arvottu luku = 19 6 - 1 = 24 ; hyväksytään
Entäpä jos arpanopilla halutaan arpoa vaikkapa lottonumeroita 1 ... 37 johon tämä menetelmä ei suoraan skaalaudu koska 6*6 < 37?
Ekalla arpanopalla arvotaan kuuluuko arvottava luku välille 1 ... 36 vaiko välille 37 ... jolta väliltä vain yksi tulos 37 on hyväksyttävissä.
Toisella arpanopan heitolla - voi olla sama noppa - arvotaan lisäys edelliseen "pohjalukuun" ja tästä vähennetään yksi koska myös lopputulos 1 täytyy olla mahdollinen.
1 ; lisätään nolla
2 ; lisätään 6
3 ; lisätään 12
4 ; lisätään 18
5 ; lisätään 24
6 ; lisätään 30
Jos summa jo tässä vaiheessa menee yli ylärajan 37 niin heitot hylätään ja aletaan uudelleen alusta.
Kolmannen nopan silmäluku lisätään ja vähennetään yksi. Tämä on lopputulos jos summa on 37 tai sen alle.
Esim.
I. Eka noppa 2 ; kokeillaan tulisiko 37 joka olisi ainoa hyväksyttävä tässä tapauksessa. Pohjaluku on 37. Toka noppa tuottaa 3 joten nämä heitot hylätään koska 39 > 37.
II. Eka noppa 2 ; pohjaluku 37. Toka noppa 1 joten 37 on edelleen mahdollinen. Kolmas noppa tuottaa kuitenkin lian suuren luvun 2 joten yläraja ylittyy ja kaikki nämä heitot hylätään.
III. Eka noppa 2 ; pohjaluku 37. Toka noppa 1 joten jatketaan. Kolmas noppa myös 1 joten lisätään nolla, 37 toteutuu ja se on hyväksyttävä lopputulos.
IV. Eka noppa 1; pohjaluku 1. Toka noppa 6, joten lisätään 30, saadaan 31. Kolmas noppa myös 6, joten lisätään 5 ja lopputulos on hyväksyttävä 36.
V. Eka noppa 1 ; pohjaluku 1. Toka noppa 1, joten lisätään nolla ja tulos edelleen 1. Kolmas noppa 1, joten lisätään vain nolla ja lopputuloksesi hyväksytään 1.
Käytetään lukujärjestelmän kantalukuna numeroa 6. Silloin välille [0, 6^n) tasan jakaantuneet luvut saadaan n heitolla. Olkoon heiton k. arvo s(k) (k = 0,...,n-1). Muodostetaan luku
R = (s(0)-1) 6 *( s(1)-1) 6^2 * (s(2)-1) ... 6^{n-1} * (s(n-1)-1).
Tämä voidaan myös panna Hornerin muotoon
R = (...((s(n-1)-1) * 6 (s(n-2)-1) * 6 ... (s(1)-1) * 6) (s(0)-1).
Esimerkki: Heitetään noppaa 3 kertaa. Olkoot silmäluvut 3 , 1 ja 5. Silloin muodostetaan luku (4 * 6 0) * 6 2 = 146. Näin saadut luvut ovat kokonaislukuja, jotka ovat tasan jäkaantuneet välille [0,216).
Silloin luvut R / 6^n ovat likimäärin tasan jakaantuneita välille [0,1). n pitää olla tarpeeksi suuri (yli 10).
Arpanoppien ohella muita mekaanisia keinoja arpoa aitoja tasaisesti ja satunnaisesti jakautuneita lukuja välillä 1 ... 26 ovat ainakin korttipakka ja lottokone.
Lottokoneesta otetaan ylimääräiset pallot pois. Jokaisen arvontakerran jälkeen arvottu pallo on pistettävä takaisin lottokoneeseen koska muuten tilanne muuttuu seuraavaa arvottaessa. Jokaisen luvun 1 ... 26 todennäköisyys on sama 1/26 vain jos kaikki 26 palloa ovat koneessa.
Korttipakassa on 4 maata ja jokaisessa maassa 13 korttia. Ässän arvo lasketaan ykköseksi, jätkä 11, huor ... eikun rouva 12, kunu 13. Jokereita ei käytetä.
Punaisia kortteja, herttoja ja ruutuja, on yhteensä 26 kpl ja mustia kortteja, patoja ja ristejä, on myös 26.
Lopputuloksen arvot voi asettaa esim. näin:
Ruutu ja pata ; 1 ... 13
Hertta ja risti ; 14 ... 26
Jos siis tulee pata tai risti niin kortin arvo lisätään "pohjalukuun" 13
Korttipakka sekoitetaan hyvin, siitä vedetään yksi kortti kerrallaan, merkitään ylös arvottu numero ja kortti palautetaan pakkaan, sekoitetaan ...
On tärkeää että kaikki kortit ovat pakassa kun uutta lukua aletaan arpoa, muuten arvotut luvut eivät ole toisistaan riippumattomia.
Eikun piti kirjoittaa:
Jos tulee _hertta_ tai risti niin kortin arvo lisätään "pohjalukuun" 13
Ehkä täytyy mainita miksi juuri lukuja 1 .. 26?
Englannin kielessä on vain 26 kirjainta 'A' .. 'Z'.
Perinteisessä salakirjoituksessa ei kryptata välilyöntejä. Kryptogrammi koostuu esim. viiden merkin mittaisista osista niin että sanojen pituutta ei voi siitä päätellä.
Kerta-avainta käyttäen selvätekstin kryptaus tapahtuu lisäämällä selväkieliseen kirjaimeen (tai sitä vastaavaan numeroon) avaimen kirjain (tai sitä vastaava numero) ja tarvittaessa palauttamalla tulos välille A .. Z (tai 1..26)
Kirjainta A vastaa siis luku 1, kirjainta B luku 2 .... kirjainta Z vastaa luku 26.
Ideana on että salakirjoitettaessa mistä tahansa selväkielen 26:sta merkistä täytyy tulla kryptogrammiin mikä tahansa tuon saman merkistö merkki täsmälleen samalla todennäköisyydellä. Niinpä lisättävä luku täytyy olla merkistön mukaisesti 1.. 26.
Kun lisäys on aidosti satunnainen niin ilman avainta kryptogrammin yksiselitteinen avaus on ikuisesti mahdotonta, olkoon vihollisella vaikka kvanttitietokone käytössään. Kaikkien tulkintojen todennäköisyys on sama.
Ratkaisevan tärkeää kuitenkin on että avain on (vähintään) yhtä pitkä kuin viesti, aidosti satunnainen, eikä avainta koskaan käytetä uudelleen. Avain on siis kertakäyttöinen, tästä menetelmän nimi "kerta-avain" (One-Tiime-Pad, OTP). Ja vastaanottajalla täytyy tietysti olla se sama kertakäyttöinen avain käytössään, eli se täytyy toimittaa hänelle erikseen.
Korjaus: One-Time-Pad, eli i-kirjaimia tuli liikaa
Viestin vastaanottaja periaatteessa _vähentää_ kryptogrammin merkeistä ne yhteisen avaimen merkit jotka lähettäjä on lisännyt ja tarvittaessa palauttaa tuloksen välille A .. Z eli 1 .. 26 jolloin hän saa alkuperäisen viestin joka toivottavasti on laadittu niin että se on ymmärrettävä ja ykiskäsitteinen ilman välilyöntejäkin.
Kävisikö tälläinen menettely tahdot luvun 1...26
arvonta kolikolla, jaat luvut kahden ryhmiin 1,2 ja 3,4 ja 5,6 jne.
ja näistä kustakin arvot kolikolla kumpi pari jää. Jos ei ole paria niin arvo säilyykö luku vai arvotaanko se pois. Sitten toistat tämä jäljelle jääneiden kanssa kunnes lopulta on vain yksi luku jäljellä.
Esim. ensimmäiseltä kierrokselta arvottu sattumalta aina eka pari
1,3,5,7,9,11,13,15,17,19,21,23,25
Toistataan ja taas sattumalta aina eka pari tulee ja pariton 25 säilyy mukana
1,5,9,13,17,21,25
Toistetaan ja jälleen sattuman oikusta tulee eka pareista mutta tällä kertaa 25 putoaa arvonnan tuloksena
1,9,17
Toistetaan 17 säilyy arvonnan tuloksena
1,17 ja näistä arvot toisen ja voittaja on 17.
Tämä onnistuu kolikolla ja kolikkoa voi simuloida nopalla 1-3 klaava 4-6 kruuna
En tiedä meneekö todennäköisyydet menettelyllä varmasti tasan, joku voisi tarkistaa.
Kyllä toimii joka kierroksella luvun tippumisen todennäköisyys on 50%. Ja tämä on sama kaikille luvuille jotka on kierroksella mukana. Mutta eihän 50% kertomalla millään saada 1/26? Saadaan koska kierrosten lukumäärä vaihtelee eri arvontakerroilla.
Ei toimi esim. arvotaan kolikolla 1,2,3 yksi näistä numeroista
P(1 valituksi)=0,375
P(2 valituksi)=0,375
P(3 valtiuksi)=0,25
Jos tahdot luvun 1...26 niin arvo binääriluku kolikolla
0,0101010101101... (niin pitkään kuin tarpeen) ja katsot mihin lukuväliin se kuuluu
0-1/26,1/26-2/26,..., 25/26-1 ja kun lukuväli on löytynyt niin saat haluamasi luvun.
Ongelma tulee vain esim. kun binäärilukusi on lähellä vaikkapa 1/26 että kumpaan väliin se kuuluu. Tässä jatkat arpomista niin kauan kunnes väli selviää tai sitten riittävän pitkä arpomisen jälkeen päätät että se on aina vaikka ensimmäiseen väliin, tällöin todennäkäisyydet eivät mene aivan tasan mutta ero on itsesi valitsema vaikkapa 0,000000000001 heitto todennäköisyyksissä.
Pistänpäs minäkin lusikkani tähän kolikon heitolla arpomiseen. Heitetään kruunaa ja klaavaa kolikolla tarkoituksena tuottaa satunnainen luku välillä 1 ... 26.
Lukua 26 suurempi luvun 2 tasapotenssi on 32 eli 2^5
Yksinkertaisimmin minusta arvotaan kolikkoa heittämällä 5-bittinen luku välillä 0 ... 31 ja lisätään 1 jolloin saadaan luku välillä 1 ... 32. Jos tulos ylittää 26 niin se hylätään ja arvotaan uudelleen alusta alkaen.
Binääriluku täytynee muodostaa aina samassa järjestyksessä ja kruunat ja klaavat tulkita biteiksi samalla tavalla. Jos vaikkapa on sovittu että ensin arvotaan vähiten merkitsevä bitti niin tästä sopimuksesta on pidettävä kiinni vaikka lopulta kävisi niin että 26 ylittyy ja järjestys kääntämällä se ei ylittyisi. Epäilen että muuten jakautuma voi vääristyä jos sääntöjä muutetaan lennossa.
Tuo kolikko ja arpakuutiohomma toimii tarkkaan ottaen vain silloin jos oletetaan että ajalla,paikalla ja subjektin ominaisuuksilla ei ole osuutta lopputulokseen. Näin tietysti oletetaan että ko. tapahtuma on satunnainen mutta onko asia oikeasti niin on oikeastaan kai avoin kysymys kuitenkin.
Lie vaikea pistää satunnaisuudessa paremmaksi kuin mitä on pienimuotoinen kolikon heitto, tasapainoisen arpakuution pyörittely, lottokoneella arpominen, ruletin pyöritys tai yhden kortin vetäminen hyvin sekoitetusta kokonaisesta korttipakasta. Hyvin valittuihin fysikaalisiin ilmiöihin perustuva satunnaisuus on niin vahvalla pohjalla kuin satunnaisuus ylipäätään voi olla.
Kaikki ei kuitenkaan ole likikään satunnaista vaikka voisi kuvitella. Esim. näppiksen hakkaaminen villisti Tarzanin Cheetah-apinatyylillä ei tuota satunnaisia merkkejä. Neukut tekivät joskus OTP-avaimia vakoilijoitaan varten kirjoituskoneella näpyttelemällä "satunnaisesti", mutta niissä tuloksissa oli selviä säännömukaisuuksia jotka tekivät niistä heikkoja kerta-avaimina.
Tavallinen teksti ei myöskään ole likikään satunnaista. Kirjaimet eivät seuraa toisiaan satunnaisessa järjestyksessä, vaan tekstillä on rakenne joka tekee siitä huonon kerta-avaimen. OTP-kerta-avainmenetelmä on turvallinen vain aidosti satunnaisen avaimen kanssa.
Tietokonekielten yksinkertaiset satunnaislukugeneraattorit ovat kuuluisia kryptograafisesta heikkoudestaan, vaikka niiden tulokset saattavat maallikosta näyttää melko satunnaisilta.
Joo kai tuo nopanheitto yms. ovat tarpeeksi satunnaisia jotain tiettyjä käytännöllisiä tarkoituksia varten mutta ovatko ne sitten aidosti satunnaisia tuloksia kullakin konkreettisella kerralla on ehkä vähän toinen juttu.
Muistaakseni tietsikan ohjelmointikielissä satunnaislukugeneraattorille annettiin joku alkuluku (usein otettiin koneen kellosta tyyliin rnd(-timer)) niin että se saatu luku olisi sitten tarpeeksi satunnainen joka iteroinnilla. Lotossa kai on tärkeintä että kukaan ei kykene ainakaan laskemalla tai jollain algoritmilla ennustamaan oikeaa lottoriviä.
Yksittäinen luku voi olla satunnainen jos generaattori alustetaan kellonajalla, vaikka generaattori ei kovin hyvä olisikaan, mutta vain kryptograafista laatua oleva satunnaislukugeneraattori tuottaa peräkkäin samalla alustuksella hyviä satunnaislukuja.
Kyllähän kielissä on jo melkoisen hyviäkin satunnaislukugeneraattoreita, mutta vanhat generaattorit olivat aika onnettomia kryptograafisiin tarkoituksiin. Niiden heikon laadun näki esim. niin että jos vaikkapa otti aina kolme "satunnaislukua" peräkkäin ja muodosti niistä pisteen xyz-koordinaatit 3D-avaruudessa niin nämä pisteet muodostivat selvästikin _tasoja_, eli luvut eivät suinkaan olleet toisistaan riippumattomia.
"ohjelmointikielissä satunnaislukugeneraattorille annettiin joku alkuluku "
Siemenluku! Alkuluku tarkoittaa hiukan eri asiaa.
Tietokoneet muodostavat pseudosatunnaislukuja tai quasisatunnaislukuja
quasisatunnaisluvut ovat erittäin tasaisesti jakautuneet (liiankin) ja nämä ovat hyödyllisiä monte carlo-simulaatioissa.
pseudosatunnaisluvut ovat tasaisesti jakautuneet pitkässä juoksussa mutta väliin on mahduttava myös "epäonnistumisia" jakaumassa.
kryptografiset pseudosatunnaisluvut ovat sellaisia että aidosti satunnainen bittijono voidaan laskennallisesti pidentää pitemmäksi bittijonoksi sillä lisäehdolla että ei ole algoritmia joka onnistuisi erottamaan tämän uuden bittijonon aidosti satunnaisesta bittijonosta tehokkaasti eli lyhyessä ajassa riittävän todennäköisesti onnistuen.
Satunnainen reaaliluku on esimerkiksi Chaitinin Omega-luvut, joiden idea on se, että ei voida tehdä algoritmia jonka pituus oli oleellisesti lyhyempi kuin bittijonon pituus jonka ohjelma voi tuottaa Omegaluvusta. Toisin sanoen Omegalukuja ei voi pakata eli kompressoida toisin sanoen ei voida myöskään ennustaa seuraavia bittejä.