PŘÍRODOVĚDECKÁ FAKULTA UNIVERZITY PALACKÉHO KATEDRA INFORMATIKY Martin Polák

ˇ ´IRODOVEDECK ˇ ´ FAKULTA UNIVERZITY PALACKEHO ´ PR A KATEDRA INFORMATIKY

´ RSK ˇ ´ PRACE ´ BAKALA A

N´ahodn´a ˇc´ısla

2013

Martin Pol´ak

Anotace N´ahodn´a ˇc´ısla jsou v dneˇsn´ı dobˇe velmi d˚ uleˇzit´ a. Uplatˇ nuj´ı se ˇcasto pˇri poˇc´ıtaˇcov´em zpracov´an´ı probl´em˚ u z r˚ uzn´ych oblast´ı lidsk´e ˇcinnosti. V pr´aci jsou pˇredstaveny nˇekter´e z gener´ator˚ u pseudon´ahodn´ych ˇc´ısel, jsou pops´ any jejich v´yhody a nev´yhody. D´ale jsou pops´ any metody z´ısk´ an´ı n´ahodn´ych ˇc´ısel pozorov´an´ım fyzik´aln´ıch jev˚ u. V z´avˇeru jsou pˇredstaveny nˇekter´e metody testov´an´ı n´ ahodnosti ˇc´ıseln´ych posloupnost´ı. V r´amci pr´ace byly tak´e implementov´any pˇredstaven´e algoritmy v programovac´ım jazyku C a vznikl program pro testov´an´ı n´ ahodnosti posloupnost´ı.

Chtˇel bych podˇekovat vedouc´ımu pr´ace RNDr. Miroslavu Kolaˇr´ıkovi, PhD. za zaj´ımav´e t´ema a cenn´e pˇripom´ınky, a tak´e m´e rodinˇe za trpˇelivost.

Obsah ´ 1. Uvod

7

2. Matematick´ e metody 2.1. Uniformn´ı rozdˇelen´ı n´ahodn´ ych ˇc´ısel 2.2. Metoda middle square . . . . . . . . 2.3. Line´arn´ı kongruentn´ı metoda . . . . . 2.3.1. Volba konstant . . . . . . . . 2.3.2. RANDU . . . . . . . . . . . . 2.4. Metoda Blum Blum Shub . . . . . .

. . . . . .

8 9 10 14 14 17 18

3. Fyzik´ aln´ı jevy jako zdroj n´ ahodn´ ych ˇ c´ısel 3.1. Lavarand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2. Difuze v kapalin´ach . . . . . . . . . . . . . . . . . . . . . . . . . .

20 20 21

4. Testov´ an´ı kvality n´ ahodn´ ych posloupnost´ı 4.1. Benford˚ uv z´akon . . . . . . . . . . . . . . . . . 4.2. χ2 test . . . . . . . . . . . . . . . . . . . . . . . 4.3. π test . . . . . . . . . . . . . . . . . . . . . . . 4.4. Hodnocen´ı gener´ator˚ u n´ahodn´ ych posloupnost´ı . 4.4.1. Middle square a middle square improved 4.4.2. Line´arn´ı kongruentn´ı metoda . . . . . . 4.4.3. Difuze . . . . . . . . . . . . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

22 23 25 28 30 30 34 35

5. Knihovna random a program Vengeance 5.1. Knihovna random . . . . . . . . . . . . . 5.2. Program Vengeance . . . . . . . . . . . . 5.2.1. Uˇzivatelsk´ y pohled . . . . . . . . 5.2.2. Program´atorsk´ y pohled . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

36 36 37 37 39

. . . . . .

. . . . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

Z´ avˇ er

40

Conclusions

41

Reference

42

A. Obsah pˇ riloˇ zen´ eho CD

43

4

Seznam obr´ azk˚ u 1. 2. 3. 4. 5. 6.

N´ahodn´a ˇc´ısla generovan´a metodou middle square s v´ ychoz´ı hodnotou 87564. . . . . . . . . . . . . . . . . . . . . . . . . . . . N´ahodn´a ˇc´ısla generovan´a metodou middle square improved s v´ ychoz´ı hodnotou 87564. . . . . . . . . . . . . . . . . . . . . . . Uspoˇr´ad´an´ı n´ahodn´ ych ˇc´ısel generovan´ ych algoritmem RANDU do paraleln´ıch rovin. . . . . . . . . . . . . . . . . . . . . . . . . . Sn´ımek difuze v kapalinˇe, pˇreveden´ y do ˇcernob´ıl´e palety. . . . . . Protnut´ı linky α jehlou (´ useˇcka CD). . . . . . . . . . . . . . . . . Hlavn´ı okno aplikace Vengeance v GUI verzi. . . . . . . . . . .

5

11 12 18 21 29 38

Seznam tabulek 1. 2. 3. 4. 5. 6.

Prvoˇc´ıseln´ y rozklad nejpouˇz´ıvanˇejˇs´ıch ˇc´ısel mocnin´e ˇrady 2. . . . . Posloupnost n´ahodn´ ych ˇc´ısel z´ıskan´ ych z difuze. . . . . . . . . . . ˇ Cetnosti v´ yskytu prvn´ıch ˇc´ıslic dle Benfordova z´akona. . . . . . . Skuteˇcn´ y a pˇredpokl´adan´ y v´ ysledek 36 hod˚ u kostkou. . . . . . . . 2 Hodnoty χ pro vybran´e hladiny v´ yznamnosti a stupnˇe volnosti. . Porovn´an´ı v´ ysledk˚ u metod middle square a middle square improved. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

15 23 24 26 27 34

1.

´ Uvod

Od nepamˇeti se lid´e bˇehem sv´eho ˇzivota setk´avali s jevy, jejichˇz v´ yskyt byl, a nebo se alespoˇ n zd´al b´ yt n´ahodn´ y. U nˇekter´ ych, jako je tˇreba stˇr´ıd´an´ı u ´plˇ nku a novu u Mˇes´ıce, ovˇsem z´ahy odhalili z´akonitosti a cyklus stˇr´ıd´an´ı a ze zd´anlivˇe n´ahodn´eho jevu se stal jev pˇredv´ıdateln´ y. U jin´ ych, napˇr´ıklad pr˚ ulet komet kolem Zemˇe, trvalo stalet´ı, neˇz pokrok vˇedy a pozn´an´ı umoˇznil popsat chov´an´ı komet a pˇredpovˇedˇet jejich n´avrat. St´ale ovˇsem existuje velk´e mnoˇzstv´ı jev˚ u, jejichˇz v´ yskyt je pro n´as, at’ uˇz skuteˇcnˇe nebo zd´anlivˇe, n´ahodn´ y. N´ahodn´a ˇc´ısla se uplatˇ nuj´ı napˇr´ıklad pˇri poˇc´ıtaˇcov´ ych simulac´ıch fyzik´aln´ıch jev˚ u, v kryptografii nebo i k z´abavˇe v r´amci poˇc´ıtaˇcov´ ych her. Pomoc´ı n´ahodn´ ych ˇc´ısel m˚ uˇzeme tak´e vybrat n´ahodn´ y vzorek z velk´e mnoˇziny dat k anal´ yze. Je tedy tˇreba z´ıskat co nejkvalitnˇejˇs´ı zdroj n´ahodn´ ych dat, protoˇze jinak by simulace fyzik´aln´ıch jev˚ u nebyla kvalitn´ı, v pˇr´ıpadˇe kryptografie bychom i pˇri pouˇzit´ı vhodn´ ych algoritm˚ u nedostali dobr´e v´ ysledky. Ve 20. letech 20. stolet´ı se objevily tabulky s n´ahodn´ ymi ˇc´ısly. V roce 1927 publikoval L.H.C. Tippett tabulky s v´ıce neˇz 40 tis´ıci n´ahodn´ ymi ˇc´ısly, kter´a z´ıskal z dat ze sˇc´ıt´an´ı lidu [1]. Pot´e se zapoˇcalo s konstrukc´ı pˇr´ıstroj˚ u, kter´e by umoˇzn ˇovali generov´an´ı n´ahodn´ ych ˇc´ısel automatizovanˇe. Poˇc´ıtaˇc Ferranti Mark I, poprv´e uveden´ y do provozu v roce 1951, obsahoval instrukci nazvanou /W, jeˇz vloˇzila do 20 nejm´enˇe v´ yznamn´ ych bit˚ u akumul´atoru n´ahodn´e hodnoty [3]. Pouˇz´ıval se k tomu hardwarov´ y gener´ator ˇsumu, kter´ y byl souˇca´st´ı poˇc´ıtaˇce. Dalˇs´ı moˇznost´ı jsou speci´aln´ı zaˇr´ızen´ı urˇcen´a pˇr´ımo ke generov´an´ı n´ahodn´ ych ˇc´ısel. Jedn´ım z takov´ ych je zaˇr´ızen´ı ERNIE (Electronic Random Number Indicator Equipment), kter´e je pouˇz´ıvan´e od roku 1957 k losov´an´ı v´ yher v loterii britsk´ ych dluhopis˚ u. V souˇcasnosti se pouˇz´ıv´a uˇz 4. generace. Pˇri postupn´em rozˇsiˇrov´an´ı poˇc´ıtaˇc˚ u se zaˇcalo ˇreˇsit z´ısk´av´an´ı n´ahodn´ ych ˇc´ısel. ’ Tabulky n´ahodn´ ych ˇc´ısel nebyly v tehdejˇs´ı dobˇe ˇreˇsen´ım, nebot poˇc´ıtaˇce mˇely velice omezen´e pamˇet’ov´e moˇznosti. Hardwarov´e gener´atory, jako napˇr´ıklad ten v poˇc´ıtaˇci Ferranti Mark I, zp˚ usobovaly probl´em s ladˇen´ım programu, nebot’ pˇri kaˇzd´em pr˚ uchodu programem jednotka dod´avala jin´e hodnoty a nav´ıc pˇri poruˇse tohoto gener´atoru je obt´ıˇzn´e poruchu detekovat. Proto se zaˇcalo s hled´an´ım metod, jak generovat n´ahodn´a ˇc´ısla ˇcistˇe matematick´ ymi metodami, kter´e pro stejn´e vstupy generuj´ı stejn´e v´ ysledky, chovaj´ı se tedy deterministicky. V pr´aci se nejprve zab´ yv´am ˇcistˇe matematick´ ymi metodami 2. pro generov´an´ı posloupnosti n´ahodn´ ych ˇc´ısel. Popisuji metodu middle square 2.2., vˇcetnˇe jej´ıch nev´ yhod. Navrhl jsem vylepˇsen´ı t´eto metody, kter´e odstraˇ nuje nˇekter´e nev´ yhody a umoˇzn´ı i snadnˇejˇs´ı pouˇzit´ı v praxi. D´ale popisuji gener´atory zaloˇzen´e na line´arn´ı u a vlastnosti vygenekongruentn´ı metodˇe 2.2., kde jsou rozebr´any volby parametr˚ rovan´ ych posloupnost´ı. Nakonec je v matematick´ ych metod´ach pops´an gener´ator Blum Blum Shub 2.3.2., kter´ y pˇri dodrˇzen´ı urˇcit´ ych podm´ınek, m˚ uˇze slouˇzit jako zdroj kvalitn´ıch n´ahodn´ ych ˇc´ısel pro pouˇzit´ı v kryptografii.

7

Dalˇs´ı ˇc´ast pr´ace se zab´ yv´a dvˇema moˇznostmi, jak generovat posloupnosti n´ahodn´ ych ˇc´ısel pomoc´ı pozorov´an´ı fyzik´aln´ıch jev˚ u. Nejprve se vˇenuji popisu gener´atoru Lavarand 3.1., kter´ y vznikl v 90. letech 20. stolet´ı ve spoleˇcnosti Silicon Graphics. Potom v kapitole 3.2. navrhuji metodu z´ısk´av´an´ı posloupnosti n´ahodn´ ych ˇc´ısel pomoc´ı sledov´an´ı difuze v kapalin´ach. N´asleduje ˇc´ast, kde se sezn´am´ıme s moˇznostmi, jak poznat, zda je urˇcit´a posloupnost ˇc´ısel n´ahodn´a. Pˇredstav´ıme si pˇredevˇs´ım dvˇe metody - χ2 test 4.2., coˇz je z´akladn´ı statistick´ y test a jako druh´ y je π test 4.3., kter´ y jsem navrhl a urˇcuje n´ahodnost posloupnosti pomoc´ı aproximace ˇc´ısla π. V posledn´ı ˇca´sti pr´ace, v kapitole 5., pak popisuji program Vengeance, kter´ y jsem v r´amci t´eto pr´ace vyvinul, a kter´ y implementuje testy n´ahodnosti posloupnosti ˇc´ısel s uniformn´ım rozloˇzen´ım mezi 0 a 1. Program lze pouˇz´ıt bud’ jako GUI aplikaci na poˇc´ıtaˇc´ıch firmy Apple s operaˇcn´ım syst´emem OS X nebo jako verzi pro pˇr´ıkazovou ˇra´dku, kde je program multiplatformn´ı a m˚ uˇze fungovat na vˇsech platform´ach, kde je k dispozici kompil´ator jazyka C. V r´amci pr´ace vznikla tak´e multiplatformn´ı knihovna, kde jsou implementov´any metody, popsan´e v t´eto pr´aci.

2.

Matematick´ e metody

V t´eto ˇc´asti se budeme zab´ yvat matematick´ ymi metodami, kter´e umoˇzn ˇuj´ı generov´an´ı pseudon´ahodn´ ych ˇc´ısel. U n´ahodn´ ych ˇc´ısel mus´ıme vˇzdy mluvit v kontextu, nebot’ tˇeˇzko m˚ uˇzeme o jednom ˇc´ıslu bez dalˇs´ıho prohl´asit, ˇze je n´ahodn´e. M´ısto toho mluv´ıme o jist´e posloupnosti ˇc´ısel, kde jednotliv´e ˇcleny posloupnosti mezi sebou nemaj´ı (ide´alnˇe) ˇz´adnou z´avislost. V pˇr´ıpadˇe generov´an´ı n´ahodn´e posloupnosti pomoc´ı deterministick´eho algoritmu hovoˇr´ıme o pseudon´ahodn´ ych ˇc´ıslech, jelikoˇz mezi ˇcleny posloupnosti z´avislost je (je d´ana pouˇzit´ ym algoritmem), ale v pˇr´ıpadˇe kvalitn´ıho algoritmu je tato z´avislost netrivi´aln´ı a posloupˇ ık´ame, nost pseudon´ahodn´ ych ˇc´ısel se bl´ıˇz´ı posloupnosti zcela n´ahodn´ ych ˇc´ısel. R´ ˇze posloupnost vypad´a jako n´ahodn´a. Pseudon´ahodn´a posloupnost b´ yv´a ˇcasto definov´ana rekurentn´ım pˇredpisem obecnˇe ve tvaru: xn+1 = f (xn ).

(1)

Zde xn znaˇc´ı pˇredchoz´ı ˇclen posloupnosti (poˇc´ateˇcn´ı hodnota x0 se oznaˇcuje jako sem´ınko – seed), xn+1 je novˇe z´ıskan´ y ˇclen posloupnosti a f je funkce, generuj´ıc´ı posloupnost. Pokud budeme pracovat v oboru pˇrirozen´ ych ˇc´ısel s 0, znaˇc´ıme N0 , mohli bychom generuj´ıc´ı funkci popsat jako n´asleduj´ıc´ı zobrazen´ı: f : (N0 )n → N0 .

(2)

Jedn´ım ze z´akladn´ıch vstupn´ıch parametr˚ u je tzv. sem´ınko (seed), coˇz je startovac´ı hodnota, od kter´e se potom d´ale, podle funkˇcn´ıho pˇredpisu, odv´ıj´ı posloupnost pseudon´ahodn´ ych ˇc´ısel. Jako seed se vol´ı nˇejak´a nesnadno zjistiteln´a 8

hodnota – ˇcasto se pouˇz´ıv´a aktu´aln´ı ˇcas nebo, pokud jsou dostupn´e pˇr´ısluˇsn´e senzory, teplota procesoru, pˇr´ıpadnˇe kombinace tˇechto veliˇcin. D´ale n´as u posloupnosti pseudon´ahodn´ ych ˇc´ısel zaj´ımaj´ı urˇcit´e podposloupnosti. Pokud se totiˇz tyto podposloupnosti ve v´ ystupu objev´ı opakovanˇe, mluv´ıme pak o cyklu posloupnosti. Je-li tento cyklus kr´atk´ y, je to neˇz´adouc´ı. Definice 1. M´ame-li posloupnost (xi )ni=1 ˇc´ısel a d´ale ryze monot´onn´ı rostouc´ı m posloupnost pˇrirozen´ych ˇc´ısel (ak )m k=1 , m ≤ n, pak posloupnost (xak )k=1 nazveme n podposloupnost´ı posloupnosti (xi )i=1 . Pokud existuje podposloupnost, kter´a se v p˚ uvodn´ı posloupnosti periodicky opakuje, nazveme toto opakov´an´ı cyklem posloupnosti. Definice 2. Mˇejme posloupnost (xi )ni=1 a jej´ı podposloupnost (xak )m k=1 . Existuje-li m m m c ∈ N takov´e, ˇze (xak )k=1 = (xak +bc )k=1 , b ∈ N, pak (xak )k=1 je cyklem posloupnosti (xi )ni=1 s d´elkou m. Pˇ r´ıklad 1. Je d´ana posloupnost (xn ) = 1, 4, 3, 5, 8, 5, 9, 7, 0, 1, 9, 7, 0, 1, . . . , 9, 7, 0, 1. Cyklem je podposloupnost (ym ) = 9, 7, 0, 1 a d´elka cyklu je 4. Je tˇreba tedy vˇenovat pozornost tomu, aby d´elka pˇr´ıpadn´eho cyklu byla v posloupnosti co nejvˇetˇs´ı a aby nedoˇslo v kr´atk´e dobˇe k degeneraci n´ahodn´e posloupnosti na urˇcitou hodnotu, napˇr´ıklad na 0, kter´a se pot´e periodicky opakuje. Vznikne t´ım cyklus s d´elkou 1. D´elka cyklu nen´ı jedinou d˚ uleˇzitou veliˇcinou ud´avaj´ıc´ı kvalitu n´ahodn´e posloupnosti. Existuj´ı posloupnosti d´elky m a d´elkou cyklu tak´e m, tedy ˇza´dn´e ˇc´ıslo se v nich neopakuje, ale pˇresto o nich nem˚ uˇzeme prohl´asit, ˇze by byly n´ahodn´e. Napˇr´ıklad posloupnost 1, 2, 3, 4, . . . , m−1, m, tedy posloupnost pˇrirozen´ ych ˇc´ısel od 1 do m, kde xn+1 = xn + 1. Jistˇe se zde ˇza´dn´a hodnota neopakuje, ale snadno vid´ıme jak´a hodnota bude n´asledovat a m˚ uˇzeme okamˇzitˇe ˇr´ıci, jak´a hodnota je napˇr´ıklad na 1000. m´ıstˇe posloupnosti.

2.1.

Uniformn´ı rozdˇ elen´ı n´ ahodn´ ych ˇ c´ısel

Pro praktick´e pouˇzit´ı je vhodn´e m´ıt pseudon´ahodn´a ˇc´ısla v nˇejak´em standardn´ım tvaru, abychom s nimi mohli snadnˇeji pracovat. Obvykle se pouˇz´ıv´a uniformn´ı rozdˇelen´ı ˇc´ısel mezi 0 a 1 [1]. Poˇzadovan´e ˇc´ıslo un z´ısk´ame pomoc´ı vztahu: xn , (3) un = m kde xn je vygenerovan´e ˇc´ıslo v posloupnosti a m je maxim´aln´ı ˇc´ıslo, kter´e se m˚ uˇze objevit v posloupnosti. U metod, pouˇz´ıvaj´ıc´ıch modul´arn´ı aritmetiku je to hodnota modulu, u metody 2.2. je to ˇc´ıslo bd − 1, kde b je z´aklad ˇc´ıseln´e soustavy a d je poˇcet ˇc´ıslic generovan´ ych n´ahodn´ ych ˇc´ısel.

9

2.2.

Metoda middle square

Nˇekdy kolem roku 1946 navrhl John von Neumann metodu, kter´a umoˇzn ˇuje snadno algoritmicky generovat posloupnosti pseudon´ahodn´ ych ˇc´ısel. Metoda se naz´ yv´a middle square, coˇz pomˇernˇe pˇresnˇe vystihuje jej´ı podstatu. U t´eto metody mohou nastat nˇekter´e probl´emy, kter´e zde popisuji a navrhuji jejich ˇreˇsen´ı. Pokud chceme z´ıskat n´asleduj´ıc´ı n´ahodn´e ˇc´ıslo v posloupnosti, vezmeme aktu´aln´ı ˇc´ıslo, spoˇc´ıt´ame jeho druhou mocninu a jako v´ ysledek pouˇzijeme prostˇredn´ı ˇc´ıslice. ˇ ıslo xn = 4896, druh´a mocnina x2n = 23970816 a tedy n´asleduj´ıc´ı Pˇ r´ıklad 2. C´ ˇc´ıslo v posloupnosti je xn+1 = 9708. Algoritmus 1 n´am ukazuje moˇznou implementaci postupu neform´alnˇe popsan´eho v´ yˇse. (1) Middle square 1: procedure middle-square(previous, digits) ▷ Dalˇs´ı n´ahodn´e ˇc´ıslo 2: base ← 10 ▷ Pracujeme v dekadick´e soustavˇe 3: start ← (3 ∗ digits)/2 4: end ← digits/2 5: remainder ← previous2 mod basestart 6: result ← remainder/baseend 7: return result 8: end procedure

Tato metoda nen´ı v praxi pˇr´ıliˇs vyuˇziteln´a. Probl´emem je pˇredevˇs´ım vytv´aˇren´ı cykl˚ u mal´e d´elky, coˇz pseudon´ahodnou posloupnost znehodnot´ı. Vzhledem k tomu, ˇze z´akladem generuj´ıc´ı funkce je druh´a mocnina, vzniknou probl´emy u ˇc´ısel, jejichˇz druh´a mocnina m´a prostˇredn´ı ˇc´ıslice stejn´e jako umocˇ novan´e ˇc´ıslo (napˇr´ıklad 50, 60, 3792, 7600 nebo 2500) nebo ˇc´ısla 0 a 1. Pokud se takov´e ˇc´ıslo dostane na vstup t´eto metody, dalˇs´ı ˇcleny posloupnosti jiˇz budou pouze toto ˇc´ıslo. Vznikne tedy cyklus s d´elkou 1. Dalˇs´ı probl´em n´am nast´ın´ı Vˇeta 1. Oznaˇcme poˇcet ˇc´ıslic, jeˇz m´a obsahovat v´ ystupn´ı ˇc´ıslo jako d. Vˇ eta 1. Pokud je 12 d a v´ıce zleva nejv´yznamnˇejˇs´ıch ˇc´ıslic vstupn´ıho ˇc´ısla xn ∈ N0 rovno 0, pak posloupnost v koneˇcn´em poˇctu krok˚ u zdegeneruje na hodnotu 0. D˚ ukaz. Definujeme: • b z´aklad ˇc´ıseln´e soustavy, • s pozice poˇca´teˇcn´ı ˇc´ıslice stˇredu ˇctverce x2n zleva, • e pozice koncov´e ˇc´ıslice stˇredu ˇctverce x2n zleva. 10

✭☎✆ ✭ ✄☎✟ ✰✯ ✮✁

✬ ✄☎✞ ✫ ✪

✩ ✄☎✝ ★ ✦

✄☎✆ ✄ ✂✄☎✆ ✂✍✄

✄

✍✄

✭✄✄ ✭✍✄ ✆✄✄ ✱✠✡☛✳ ✴☞✠✴✌

✆✍✄

✎✄✄

✎✍✄

Obr´azek 1.: N´ahodn´a ˇc´ısla generovan´a metodou middle square s v´ ychoz´ı hodnotou 87564. logb [(bd )2 ] d logb [(bd )2 ] + d 2d + d 1 + = = =1 d (4) 2 2 2 2 2 logb [(bd )2 ] d logb [(bd )2 ] − d 2d − d 1 e= − = = = d (5) 2 2 2 2 2 D´ale je zˇrejmˇe d = s − e. Protoˇze plat´ı logb (x2n ) < logb (bd ), je tak´e x2n < bd . 2 bs , plyne Jelikoˇz s = 1 12 d, tak x2n mod bs = x2n . M´ame-li tedy xn+1 = xn mod be x2n 2 2 z toho, ˇze xn+1 = be . Tedy xn+1 < xn a tedy i xn+1 < xn . Dostaneme-li tedy jako vstup ˇc´ıslo dle Vˇety 1, dalˇs´ı ˇcleny posloupnosti budou vˇzdy menˇs´ı neˇz pˇredchoz´ı a po koneˇcn´em poˇctu krok˚ u jiˇz budou v´ ystupy z funkce vˇzdy 0 (Obr. 1.). s =

Ovˇsem probl´em nastane i v pˇr´ıpadˇe, ˇze se nulov´e ˇc´ıslice objev´ı na konci vygenerovan´eho ˇc´ısla. Vˇ eta 2. Je-li v d-m´ıstn´em ˇc´ısle xn ∈ N0 na 12 d nejm´enˇe v´yznamn´ych ˇc´ıslic´ıch zprava ˇc´ıslice 0, je dalˇs´ım ˇclenem v posloupnosti ˇc´ıslo, jeˇz m´a na 21 d nejm´enˇe v´yznamn´ych ˇc´ıslic´ıch zprava opˇet ˇc´ıslici 0. D˚ ukaz. Mˇejme d-m´ıstn´e ˇc´ıslo xn v soustavˇe o z´akladu b, kter´e m´a na

11

1 d 2

1,2

Náhodná !ísla

1 0,8 0,6 0,4 0,2 0 -0,2 -50

0

50

100 150 200 Po!et krok"

250

300

350

Obr´azek 2.: N´ahodn´a ˇc´ısla generovan´a metodou middle square improved s v´ ychoz´ı hodnotou 87564. nejm´enˇe v´ yznamn´ ych ˇc´ıslic´ıch zprava 0. Existuje ˇc´ıslo yn tak, ˇze: xn = yn bs ,

1 s = d. 2

(6)

ˇ ıslo yn se tedy od xn liˇs´ı o bs n´asobek a z´aroveˇ C´ n m´a ˇc´ıslo yn 12 d ˇc´ıslic. Vzhledem s k tomu, ˇze ˇc´ıslo b je mocnina z´akladu ˇc´ıseln´e soustavy, je pro vˇsechna d-m´ıstn´a ˇc´ısla xn konstantou. Poˇcet navz´ajem r˚ uzn´ ych ˇc´ısel xn , kter´a m˚ uˇzeme vytvoˇrit je tedy shodn´ y s poˇctem navz´ajem r˚ uzn´ ych ˇc´ısel yn . T´ım doch´az´ı v posloupnosti 1 k tvorbˇe kr´atk´ ych cykl˚ u, protoˇze se vytv´aˇr´ı pouze n´ahodn´a ˇc´ısla v rozsahu b 2 d a menˇs´ım. Pˇ r´ıklad 3. Jako v´ychoz´ı hodnotu pouˇzijme xn = 5600 a pokraˇcujeme v generov´an´ı posloupnosti d´ale xn+1 = 3600, xn+2 = 9600, xn+3 = 1600, . . .. Vˇsimnˇeme si, ˇze ke kaˇzd´emu xn existuje i ˇc´ıslo yn tak, ˇze xn = yn 102 (yn = 56, yn+1 = 36, . . .). Pod´ıvejme se nyn´ı, jak bychom mohli tyto probl´emy ˇreˇsit. Po vygenerov´an´ı dalˇs´ıho ˇclenu posloupnosti budeme muset testovat, zda tento ˇclen nen´ı problematick´ y ve smyslu v´ yˇse zm´ınˇen´em. Mus´ıme tedy vyzkouˇset pˇredevˇs´ım, zda v´ ystup nen´ı shodn´ y se vstupem, zda nevyhovuje Vˇetˇe 1, a nebo Vˇetˇe 2. Pokud je jedna 12

z podm´ınek splnˇena, mus´ıme pouˇz´ıt pomocnou funkci, kter´a v´ ysledek uprav´ı a zavol´ame znovu generuj´ıc´ı funkci. Asi nejkvalitnˇejˇs´ı ˇreˇsen´ı by bylo ozn´amit ˇzadateli o n´ahodn´a ˇc´ısla, ˇze je tˇreba dodat nov´e sem´ınko, nicm´enˇe v tom pˇr´ıpadˇe bychom byli z´avisl´ı na vnˇejˇs´ım z´asahu, coˇz nen´ı vhodn´e. Navrhneme si tedy jednoduchou funkci, kter´a toto bude ˇreˇsit. V´ yhodou tohoto pˇr´ıstupu je, ˇze pro stejn´e vstupy d´av´a vˇzdy stejn´e v´ ystupy (je tedy deterministick´ y), nev´ yhodou je, ˇze n´aˇs probl´em nemus´ı ˇreˇsit kvalitnˇe. Nejprve si tedy algoritmem 2 uprav´ıme p˚ uvodn´ı algoritmus 1. Pˇrid´ame podm´ınku, kter´a testuje problematick´e hodnoty a pokud na nˇejakou naraz´ı, zavol´a rekurzivnˇe algoritmus 2 s t´ım, ˇze parametr previous je upraven algoritmem 3. Algoritmus 3 ke vstupn´ı hodnotˇe pˇriˇcte digits, coˇz je poˇcet ˇc´ıslic poˇzadovan´eho v´ ystupu z algoritmu 2. T´ım se ˇreˇs´ı probl´em popsan´ y Vˇetou 2. V´ ysledek potom digits n´asob´ıme 2 , coˇz ˇreˇs´ı probl´em Vˇety 1. (2) Middle square improved 1: procedure middle-square(previous, digits) ▷ Dalˇs´ı n´ahodn´e ˇc´ıslo 2: base ← 10 ▷ Pracujeme v dekadick´e soustavˇe 3: start ← (3 ∗ digits)/2 4: end ← digits/2 5: remainder ← previous2 mod basestart 6: result ← remainder/baseend 7: if (result = previous) || (result2 < basedigits−1 ) || (result mod baseend = 8: 9: 10: 11: 12:

0) then renewed ← renew(previous, digits) result ← middle-square(renewed, digits) end if return result end procedure

▷ || Disjunkce (OR)

(3) Renew for middle-square 1: procedure renew(previous, digits) ▷ V´ ystupem je upraven´e ˇc´ıslo 2: sum ← previous + digits 3: result ← sum <
(digits) 4: return result 5: end procedure Na Obr. 1. je vidˇet vznik cyklu s d´elkou 1. Vˇsimnˇeme si, ˇze uˇz asi po 20 kroc´ıch je v´ ystupem hodnota 0, kter´a se pak jiˇz bude opakovat poˇra´d. Tento probl´em odstranila metoda middle square improved, jak vid´ıme na Obr. 2., kde pˇri stejn´ ych vstupn´ıch parametrech tento cyklus nevzniknul. 13

2.3.

Line´ arn´ı kongruentn´ı metoda

Metoda generov´an´ı pseudon´ahodn´ ych ˇc´ısel poprv´e pˇredstavena D. H. Lehmerem v roce 1949. M˚ uˇzeme ji popsat vztahem xn+1 = (axn + c) mod m,

n ∈ N0 ,

(7)

kde • xn+1 je dalˇs´ı ˇclen posloupnosti, • xn je aktu´aln´ı ˇclen posloupnosti; speci´alnˇe x0 je poˇc´ateˇcn´ı ˇclen posloupnosti – sem´ınko, • a ∈ N0 je multiplikativn´ı konstanta, • c ∈ N0 je aditivn´ı konstanta, • m ∈ N0 je modul. Na volbˇe x0 , a, c, m z´avis´ı kvalita v´ ysledn´e posloupnosti. Pokud si zvol´ıme napˇr´ıklad a = 1 a c = 1, tak v´ ysledkem bude posloupnost x0 , x0 +1, x0 +2, . . . , x0 + m, coˇz sice je posloupnost s maxim´aln´ım moˇzn´ ym cyklem o d´elce m, ale n´ahodn´a jistˇe nen´ı. P˚ uvodn´ı Lehmerova metoda nebere v u ´vahu aditivn´ı konstantu, tzn. c = 0 (i kdyˇz Lehmer zmiˇ noval i moˇznost c > 0), takˇze vztah je jednoduˇsˇs´ı: xn+1 = axn mod m,

n ∈ N0 .

(8)

Vztah (8) n´am pˇeknˇe ukazuje, ˇze pokud m´a b´ yt generovan´a posloupnost n´ahodn´a, je tˇreba volit a ≥ 2. D´ale u (8) napˇr´ıklad nikdy nedos´ahneme maxim´aln´ı d´elky cyklu m. Coˇz je zˇrejm´e, nebot’ c = 0, a proto by se nemˇelo vyskytnout xn = 0. 2.3.1.

Volba konstant

Konstanta m, by mˇela b´ yt dostateˇcnˇe velk´a. Uvˇedomme si, ˇze posloupnost nem˚ uˇze m´ıt cyklus delˇs´ı neˇz m, pokud tedy zvol´ıme pˇr´ıliˇs mal´e m, bude m´ıt posloupnost kr´atk´ y cyklus a nebude pˇr´ıliˇs n´ahodn´a. Pˇrirozenˇe se nab´ız´ı moˇznost volby m, jako maxim´aln´ı velikosti datov´eho typu. Pak m˚ uˇzeme operaci dˇelen´ı modulo m poˇc´ıtat snadno pouze pomoc´ı bitov´ ych operac´ı. Probl´em je ale v tom, ˇze ˇc´ıslice na prav´e stranˇe ˇc´ısla jsou m´enˇe n´ahodn´e, neˇz ˇc´ıslice nalevo. V poˇc´ıtaˇci totiˇz pracujeme s ˇc´ısly v bin´arn´ı soustavˇe a maxim´aln´ı velikost celoˇc´ıseln´eho datov´eho typu je vˇzdy ve tvaru 2n . Pokud bude d dˇelitelem ˇc´ısla m, a z´aroveˇ n bude platit yn = xn mod d, (9) potom yn+1 = (ayn + c) mod d. 14

(10)

Vytv´aˇr´ı se line´arn´ı kongruentn´ı posloupnost s d´elkou cyklu maxim´alnˇe d. Budeme-li pracovat s ˇc´ısly v soustavˇe o z´akladu 2 a budeme m´ıt m = 232 a d = 23 , budou tˇri nejm´enˇe v´ yznamn´e bity zleva tvoˇrit posloupnost s cyklem nejv´ yˇse 8, protoˇze yn = xn mod 8 a plat´ı (10), viz Pˇr. 4. Pokud bychom pouˇzili m = 216 − 1, probl´em s m´enˇe n´ahodn´ ymi ˇc´ıslicemi by nastal pouze v pˇr´ıpadˇe, ˇze bychom do (10) dosadili za d hodnoty 3, 5, 17, 257, ˇcili ˇc´ısla, jeˇz dˇel´ı modul. Pro praktick´e pouˇzit´ı je tedy l´epe pouˇz´ıt hodnotu m = 2n ± 1, pˇr´ıpadnˇe nejvˇetˇs´ı moˇzn´e prvoˇc´ıslo p < 2n . Samozˇrejmˇe, ˇze v nˇekter´ ych pˇr´ıpadech n´am nemus´ı menˇs´ı n´ahodnost ˇc´ıslic v prav´e ˇca´sti ˇc´ısla vadit. Pak m˚ uˇzeme pouˇz´ıt hodnotu m = 2n a v´ ypoˇcet bude snazˇs´ı. Pˇ r´ıklad 4. Zvol´ıme a = 3, c = 0, m = 25 , d = 28 , x0 = 35, pak je xn+1 = (3 · 35) mod 32 = 9 yn+1 = (3 · 35) mod 8 = 1 yn+1 = xn+1 mod 8 = 9 mod 8 = 1.

(11)

Pro volbu dalˇs´ıch konstant je uˇziteˇcn´e zn´at prvoˇc´ıseln´ y rozklad pˇr´ısluˇsn´ ych hodnot m (Tab. 1.). Hodnoty jsem z´ıskal z [1], kde je v tabulce na stranˇe 14 kompletn´ı pˇrehled. Pro naˇse potˇreby budou staˇcit uveden´e hodnoty (Tab. 1.). 2n − 1 n 2n + 1 3 · 5 · 17 · 257 16 65537 3 · 5 · 17 · 257 · 65537 32 641 · 6700417 3 · 5 · 17 · 257 · 641 · 65537 · 6700417 64 274177 · 67280421310721 Tabulka 1.: Prvoˇc´ıseln´ y rozklad nejpouˇz´ıvanˇejˇs´ıch ˇc´ısel mocnin´e ˇrady 2.

Nyn´ı potˇrebujeme zvolit dalˇs´ı konstanty a, c, x0 tak, aby cyklus v posloupnosti mˇel nejdelˇs´ı moˇznou d´elku, tedy m. Takov´a posloupnost existuje vˇzdy, jak ukazuje pˇr´ıklad volby a = 1 a c = 1, posloupnost je x0 , x0 + 1, x0 + 2, . . . , x0 + m. My vˇsak budeme potˇrebovat stanovit obecnˇejˇs´ı pravidla pro konstanty, abychom z´ıskali n´ahodnou posloupnost. Vˇ eta 3. [1] Line´arn´ı kongruentn´ı posloupnost m´a cyklus d´elky m tehdy a pouze tehdy, kdyˇz 1. c je nesoudˇeln´e s m; 2. (a − 1) je n´asobek p pro kaˇzd´e prvoˇc´ıslo p, kter´e dˇel´ı m; 3. (a − 1) je n´asobek 4, pokud m je n´asobek 4.

15

D˚ ukaz Vˇety 3 je uveden v [1]. Nyn´ı jeˇstˇe dva zaj´ımav´e postˇrehy. D´elky cyklu m m˚ uˇzeme dos´ahnout tehdy a pouze tehdy, kdyˇz se kaˇzd´e cel´e ˇc´ıslo x, 0 ≤ x < m vyskytne v cyklu pouze jednou. Cyklus d´elky m v posloupnosti je tedy moˇzn´ y tehdy a pouze tehdy, pokud je cyklus d´elky m v posloupnosti, kter´a m´a x0 = 0. M´ame-li potom obecn´ y tvar pro k-t´ y ˇclen line´arn´ı kongruentn´ı posloupnosti [1] xn+k = (ak xn +

(ak − 1)c ) mod m, a−1

k ≥ 0, n ≥ 0

(12)

a m˚ uˇzeme pˇredpokl´adat, ˇze x0 = 0, dostaneme [1] xn = (

ak − 1 )c mod m. a−1

(13)

Jestliˇze by tedy c bylo soudˇeln´e s m, nikdy by nemohlo nastat xn = 1. Proto je ve Vˇetˇe 3 prvn´ı podm´ınka nezbytn´a1 . Vr´at´ıme-li se zpˇet k pˇr´ıpadu (8), tedy c = 0, nemˇela by se objevit hodnota xn = 0, jak jsme si jiˇz uk´azali. D´ale pokud d bude dˇelitel m a objev´ı se xn , kter´e bude n´asobkem d, dalˇs´ı ˇcleny posloupnosti xn+1 , xn+2 , . . . budou opˇet n´asobky d. Pro dostateˇcnˇe n´ahodnou posloupnost tedy budeme cht´ıt, aby vˇsechna xn byla nesoudˇeln´a s m. T´ım je maxim´aln´ı d´elka cyklu omezena na φ(m), kde φ(m) je Eulerova funkce, kter´a vyjadˇruje poˇcet ˇc´ısel v intervalu 0 . . . m, jeˇz jsou nesoudˇeln´a s m. Definice 3. Necht’ a je nesoudˇeln´e s m, potom nejmenˇs´ı pˇrirozen´e ˇc´ıslo k nazveme ˇr´adem ˇc´ısla a modulo m, pokud plat´ı ak ≡ 1 (mod m). ˇ ıslo a nazveme primitivn´ım prvkem modulo m, pokud m´a ˇr´ Definice 4. C´ ad modulo m roven φ(m). M´a tedy maxim´aln´ı moˇzn´y ˇr´ ad modulo m. N´asleduj´ıc´ı vˇeta n´am potom ˇrekne, jak´e jsou podm´ınky dosaˇzen´ı maxim´aln´ı d´elky cyklu v pˇr´ıpadˇe line´arn´ı kongruentn´ı posloupnosti, kde c = 0 (8). Vˇ eta 4. [1] Line´arn´ı kongruentn´ı posloupnost, kde c = 0 (8), m´a maxim´aln´ı d´elku cyklu tehdy, kdyˇz 1. x0 je nesoudˇeln´e s m; 2. a je primitivn´ım prvkem modulo m. V pˇr´ıpadˇe, ˇze m = 2n , je a primitivn´ım prvkem modulo m tehdy, kdyˇz a ≡ 3 (mod m) nebo a ≡ 5 (mod m). Potom je maxim´aln´ı d´elka cyklu m/4 [1]. 1

Pokud jsou c a m nesoudˇeln´a, nem˚ uˇze naopak nastat xn = 0, protoˇze x0 = 0.

16

n > 0, coˇz n´am ale nevad´ı,

2.3.2.

RANDU

Metoda generov´an´ı n´ahodn´ ych ˇc´ısel zaloˇzen´a na line´arn´ı kongruenci. Obecn´ y tvar je stejn´ y jako u Lehmerovy metody (8). Volba konstant je a = 65539 a m = 231 , jako sem´ınko se pouˇz´ıv´a hodnota x0 , kde x0 je lich´e ˇc´ıslo. Posloupnost je d´ana pˇredpisem xn+1 = 65539 · xn mod 231 ,

n ∈ N0 .

(14)

Protoˇze x0 je lich´e ˇc´ıslo, 65539 · x0 je tak´e lich´e. V´ ysledkem je tedy vˇzdy lich´e ˇc´ıslo. Z toho vypl´ yv´a, ˇze maxim´aln´ı d´elka cyklu nem˚ uˇze b´ yt vˇetˇs´ı neˇz 231 /2. Pokud se pod´ıv´ame na volbu konstanty a a hodnotu x0 , vid´ıme, ˇze 65539 ≡ 3 (mod 8) a tedy 65539 je primitivn´ım elementem modulo 231 (viz Vˇeta 4) a cyklus v posloupnosti dos´ahne maxim´aln´ı moˇznou d´elku 231 /4. Tato metoda byla popul´arn´ı v 60. a na zaˇc´atku 70. let 20. stolet´ı. Popularita metody byla dan´a i t´ım, ˇze na (bin´arn´ım) poˇc´ıtaˇci lze tuto metodu implementovat velice snadno i bez pouˇzit´ı n´asoben´ı nebo dˇelen´ı. Staˇc´ı k tomu bitov´e operace a sˇc´ıt´an´ı, jak vid´ıme v algoritmu 4. (4) RANDU 1: procedure randu(previous) ▷ V´ ystupem je dalˇs´ı ˇc´ıslo posloupnosti 31 2: mask ← 2 − 1 3: result ← (previous <<16 ) + previous + (previous <<1 ) ▷ << Bitov´ y

posun vlevo o urˇcen´ y poˇcet bit˚ u 4: result ← result & mask 5: return result 6: end procedure

▷ & Bitov´a operace AND

Algoritmus je tedy velice rychl´ y a d´a se implementovat i na poˇc´ıtaˇc´ıch s omezen´ ymi zdroji, ale v roce 1968 uk´azal George Marsaglia, ˇze pokud pouˇzijeme vygenerovan´a n´ahodn´a ˇc´ısla jako souˇradnice bod˚ u v jednotkov´e krychli s dimenz´ı ≥ 3, body nebudou v prostoru rozpt´ yleny n´ahodnˇe, ale seˇrad´ı se do nˇekolika rovin [4], viz Obr. 3. V (15) m˚ uˇzeme vidˇet, jak jsou na sobˇe z´avisl´e vˇzdy 3 po sobˇe n´asleduj´ıc´ı prvky posloupnosti generovan´e algoritmem RANDU. Pokud pracujeme v aritmetice modulo 231 , pak xn+1 = (216 + 3) · xn xn+2 = (216 + 3) · xn+1 = (216 + 3)2 · xn = = (232 + 216 · 6 + 9)xn = (6 · 216 + 9)xn = = [6(216 + 3) − 9]xn = 6(216 + 3)xn − 9xn = = 6xn+1 − 9xn .

(15)

Obecnˇe m˚ uˇzeme xn+j prvek posloupnosti RANDU popsat jako xn+j = aj xn mod 231 , 17

(16)

Obr´azek 3.: Uspoˇra´d´an´ı n´ahodn´ ych ˇc´ısel generovan´ ych algoritmem RANDU do paraleln´ıch rovin. protoˇze ale m´ame a = 65539 = 216 + 3 a tedy xn+j = xn (216 + 3)j mod 231 = j ( ) ∑ j = xn · (216 )j−k · 3k mod 231 . k k=0

(17)

Jelikoˇz je 231+n ≡ 0 (mod 231 ), n ∈ N0 , vˇsechny ˇcleny polynomu, kde je j − k ≥ 2 budou rovny 0. Takov´ y probl´em by nenastal, pokud by modul byl zvolen napˇr´ıklad jako nejvˇetˇs´ı moˇzn´e prvoˇc´ıslo menˇs´ı neˇz 231 .

2.4.

Metoda Blum Blum Shub

Tato metoda je vhodn´a jako zdroj kvalitn´ıch pseudon´ahodn´ ych ˇc´ısel pro kryptografick´e u ´ˇcely. Naopak se pˇr´ıliˇs nehod´ı jako obecn´a funkce pro generov´an´ı pseu-

18

don´ahodn´ ych ˇc´ısel. Generuj´ıc´ı funkce je d´ana vztahem xn+1 = x2n mod m,

(18)

kde xn+1 je dalˇs´ı ˇclen posloupnosti, xn je aktu´aln´ı ˇclen posloupnosti a m je modul. V´ ystupem jedn´e iterace je nejm´enˇe v´ yznamn´ y bit ˇc´ısla xn+1 . Z´ıskan´ y bit se potom pˇripoj´ı zprava k v´ ysledn´emu ˇc´ıslu. Pokud tedy potˇrebujeme z´ıskat napˇr´ıklad 64 bitov´e pseudon´ahodn´e ˇc´ıslo, mus´ıme vygenerovat 64 ˇclen˚ u posloupnosti dan´e pˇredpisem (18). Tento gener´ator je vhodn´ y pˇredevˇs´ım ke kryptografick´ ym u ´ˇcel˚ um, protoˇze generov´an´ı kvalitn´ı posloupnosti je pomˇernˇe ˇcasovˇe n´aroˇcn´e. D´ale je tak´e probl´em, ˇze d´elka cyklu v posloupnosti je kratˇs´ı, neˇz hodnota modulu m. Nen´ı tedy snadn´e pˇrev´est ˇcleny posloupnosti na uniformn´ı rozdˇelen´ı. (5) Blum Blum Shub 1: procedure blum-blum-shub(previous, m, bits) 2: 3: 4: 5: 6: 7: 8: 9:

▷ V´ ystupem je dalˇs´ı ˇc´ıslo posloupnosti result ← 0 xn ← previous for i ← 1, bits do xn ← x2n mod m result ← (result <<1 )|(xn &1) ▷ & Bitov´a operace AND, << bitov´ y posun o urˇcen´ y poˇcet bit˚ u, | Bitov´a operace OR end for return (result, xn ) end procedure

Pˇri volbˇe sem´ınka x0 , bychom se mˇeli vyhnout hodnot´am 0 a 1. To je zˇrejm´e nebot’ jejich druh´a mocnina je opˇet stejn´e ˇc´ıslo. D´ale by x0 mˇelo b´ yt nesoudˇeln´e s m. Parametr m je souˇcin dvou prvoˇc´ısel p, q takov´ ych, ˇze p, q ≡ 3 (mod 4) a z´aroveˇ n p ̸= q. Vysvˇetlit detailnˇe probl´em, d´ıky nˇemuˇz je tento gener´ator povaˇzovan´ y za kryptograficky bezpeˇcn´ y, je nad r´amec t´eto pr´ace. Zjednoduˇsenˇe bychom mohli probl´em popsat: M´ame-li sloˇzen´e ˇc´ıslo n, urˇcete odmocninu ˇc´ısla x, kde x je ” kvadratick´e reziduum modulo n.“ Kvadratick´e reziduum modulo n je pak takov´e ˇc´ıslo a ∈ Zn 2 , ke kter´emu existuje ˇc´ıslo b ∈ Zn tak, ˇze b2 ≡ a (mod n). K vyˇreˇsen´ı tohoto probl´emu je tˇreba zn´at prvoˇc´ıseln´ y rozklad ˇc´ısla n, jehoˇz zjiˇstˇen´ı pomoc´ı faktorizace je pro velk´a ˇc´ısla v´ ypoˇcetnˇe sloˇzit´a u ´loha. Tedy rozliˇsit posloupnost bit˚ u, jeˇz jsou generov´any touto metodou (za pˇredpokladu vhodnˇe zvolen´ ych parametr˚ u) od ˇcistˇe n´ahodn´ ych bit˚ u je minim´alnˇe stejnˇe v´ ypoˇcetnˇe n´aroˇcn´e, jako faktorizace velk´ ych ˇc´ısel. 2

Zn znaˇc´ı mnoˇzinu zbytkov´ ych tˇr´ıd dˇelen´ı modulo n.

19

3.

Fyzik´ aln´ı jevy jako zdroj n´ ahodn´ ych ˇ c´ısel

Jako zdroj n´ahodn´ ych ˇc´ısel m˚ uˇzeme tak´e vyuˇz´ıt nˇekter´ ych fyzik´aln´ıch jev˚ u. M˚ uˇzeme pouˇz´ıt dva z´akladn´ı pˇr´ıstupy. Fyzik´aln´ı jev m˚ uˇze slouˇzit pro inicializaci gener´atoru n´ahodn´ ych ˇc´ısel, jako napˇr´ıklad v 3.1. nebo m˚ uˇzeme pouˇz´ıt pˇr´ımo tento jev jako zdroj n´ahodn´ ych ˇc´ısel 3.2.. Existuj´ı i dalˇs´ı fyzik´aln´ı jevy, kter´e lze pouˇz´ıt pro generov´an´ı n´ahodn´ ych ˇc´ısel. Napˇr´ıklad kvantov´e optick´e jevy, kter´e jsou z´akladem pro komerˇcnˇe dostupn´ y hardware pro generov´an´ı n´ahodn´ ych ˇc´ısel viz http://www.idquantique.com/random-number-generators/products.html. Tak´e lze pouˇz´ıt sledov´an´ı rozpadu radiaktivn´ıch ˇc´astic, coˇz pouˇz´ıv´a gener´ator HotBits viz http://www.fourmilab.ch/hotbits/. Z praktick´ ych d˚ uvod˚ u (bohuˇzel nem´am k dispozici patˇriˇcn´e vybaven´ı pro sledov´an´ı rozpadu ˇca´stic a jin´ ych jev˚ u) jsem navrhl gener´ator 3.2., kter´ y generuje n´ahodn´a ˇc´ısla pomoc´ı sledov´an´ı difuze v kapalin´ach a kter´ y jsem mohl i implementovat.

3.1.

Lavarand

Tato metoda vyuˇz´ıv´a jako zdroj pro sem´ınko gener´atoru n´ahodn´ ych ˇc´ısel obr´azek l´avov´e lampy. Metoda vznikla v roce 1996 ve firmˇe Silicon Graphics, Inc. L´avov´a lampa je dekoraˇcn´ı doplnˇek, kter´ y pomoc´ı fyzik´aln´ıho jevu, kdy hustˇejˇs´ı kapalina vytv´aˇr´ı bubliny v m´enˇe hust´e kapalinˇe, tvoˇr´ı n´ahodn´e obrazce. Takto bylo u sebe um´ıstˇen´ ych 6 l´avov´ ych lamp, kter´e byly sn´ım´any kamerou. V pravideln´ ych intervalech byly poˇrizov´any obr´azky, kter´e slouˇz´ı jako z´aklad pro vygenerov´an´ı sem´ınka [5]. Kaˇzd´ y sn´ımek obsahoval v´ıce neˇz 900 tis´ıc byt˚ u a bylo tˇreba z´ıskat z nˇej sem´ınko, kter´e m´a 140 byt˚ u. K tomu byla pouˇzita haˇsovac´ı funkce SHA-1. Z jednoho obr´azku se vygenerovalo 7 haˇs˚ u d´elky 160 bit˚ u (haˇsoval se vˇzdy kaˇzd´ y 7. byte) a v´ ysledkem bylo 140 bytov´e sem´ınko. Toto sem´ınko se pouˇzilo jako vstup pro Blum Blum Shub gener´ator (2.3.2.), kde modul byl ˇc´ıslo: 5360751114622011236087979022735306713592537659947455285353148181 8526455500785383194936281698585494806464721601253386562653528822 5543322562532917886396992291116815877218495559211688377961466145 0857446201926232198015028137924055146650866097197909406089918491 4133568666470293429076893274969016410915119621659901793350665953, coˇz je souˇcin dvou prvoˇc´ısel. Vzhledem k vlastnostem Blum Blum Shub gener´atoru a zp˚ usobu z´ısk´an´ı sem´ınka, se jednalo jistˇe o kvalitn´ı zdroj n´ahodn´ ych ˇc´ısel pro kryptografick´e u ´ˇcely. Bohuˇzel kv˚ uli probl´em˚ um a restrukturalizaci spoleˇcnosti Silicon Graphics, Inc. jiˇz str´anky vˇenovan´e tomuto gener´atoru neexistuj´ı. Rekonstrukce tohoto gener´atoru je nad r´amec t´eto pr´ace.

20

3.2.

Difuze v kapalin´ ach

Difuze je fyzik´aln´ı jev, kdy se ˇca´stice jedn´e l´atky rozptyluj´ı v l´atce jin´e. Pohyb kaˇzd´e ˇc´astice je n´ahodn´ y, ovˇsem postupnˇe doch´az´ı k pˇresunu ˇc´astic z m´ıst z vyˇsˇs´ı koncentrac´ı do m´ıst s niˇzˇs´ı koncentrac´ı. Je sice nad r´amec t´eto pr´ace popsat pˇresnˇe tento jev, pop´ıˇseme si ale zp˚ usob, jak´ ym lze tohoto jevu vyuˇz´ıt ke generov´an´ı posloupnosti n´ahodn´ ych ˇc´ısel. Vybereme si difuzi v kapalinˇe, kv˚ uli rychlosti a relativnˇe snadn´emu zachycen´ı tohoto jevu. Mˇejme tedy pr˚ uhlednou n´adobu s vodou a jinou kapalinu, barevnˇe v´ yraznˇe odliˇsnou. Napˇr´ıklad inkoust. Ve chv´ıli, kdy zaˇcne prob´ıhat difuze, zaˇcneme digit´aln´ım fotoapar´atem poˇrizovat sn´ımky. Tyto sn´ımky potom pˇrevedeme do ˇcernob´ıl´e palety (Obr. 4.). Z takto upraven´eho sn´ımku je jeˇstˇe vhodn´e oˇr´ıznout ˇr´adky, na kter´ ych je pouze jedna barva, tzn. ˇra´dky kter´e jsou bud’ cel´e b´ıl´e nebo cel´e ˇcern´e.

Obr´azek 4.: Sn´ımek difuze v kapalinˇe, pˇreveden´ y do ˇcernob´ıl´e palety. Z´ıskan´e sn´ımky potom pouˇzijeme k z´ısk´an´ı n´ahodn´ ych ˇc´ısel. Pro praktickou implementaci pˇrevedeme sn´ımek do form´atu XPM (X PixMap), coˇz je grafick´ y form´at, kter´ y se pouˇz´ıv´a pˇredevˇs´ım v X Window syst´emu. Data obr´azku jsou zde uloˇzena v zdrojov´em k´odu jazyka C, je tedy moˇzn´e tento soubor vloˇzit pˇr´ımo do programu v jazyku C. Na zaˇc´atku jsou uloˇzeny rozmˇery, poˇcet barev a definice barvov´e palety. Pak jiˇz n´asleduj´ı samotn´a obrazov´a data. U ˇcernob´ıl´eho sn´ımku jsou reprezentov´ana dvˇema znaky – “ (mezera) jako ˇcern´ y bod a .“ jako b´ıl´ y ” ” bod. N´ahodn´a ˇc´ısla budeme generovat pouze z obrazov´ ych dat. Z kaˇzd´eho ˇr´adku z´ısk´ame jedno ˇc´ıslo n´ahodn´e posloupnosti, takˇze d´elka posloupnosti z´ıskan´e z jed21

noho sn´ımku je shodn´a s vertik´aln´ım rozliˇsen´ım sn´ımku. Pokud je tˇreba delˇs´ı posloupnost, mus´ıme pouˇz´ıt v´ıce sn´ımk˚ u. N´ahodn´e ˇc´ıslo z vybran´eho ˇr´adku z´ısk´ame pomoc´ı haˇsovac´ı funkce (19). g(x) = h(x) mod 232 ,

(19)

kde x je ˇc´ıslo ˇr´adku a h(x) definujeme jako h(x) =

r ∑

pk · asc(k − 1),

(20)

k=1

kde r je horizont´aln´ı rozliˇsen´ı sn´ımku, p = 37 je prvoˇc´ıslo a asc(k) je funkce, kter´a pro znak v ˇretˇezci na pozici k, vr´at´ı jeho hodnotu v tabulce ASCII. (6) Diffusion 1: procedure diffusion(row[]) ▷ row[] je pole s obrazov´ ymi daty ˇra´dku 2: result ← 0 3: p ← 37 4: pk ← 1 5: i←0 6: ch ← 1 7: while (ch ← 1) ̸= 0 do 8: pk ← (pk · p) mod 232 9: result ← (result + ch · pk ) mod 232 10: i←i+1 11: end while 12: return result mod 232 13: end procedure

V pˇr´ıpadˇe Obr. 4. vznikne posloupnost 236 n´ahodn´ ych ˇc´ısel. Po pˇreveden´ı na uniformn´ı rozdˇelen´ı pomoc´ı 2.1., vid´ıme ˇc´ast posloupnosti v Tab. 2. Jeˇstˇe bych se zastavil u haˇsovac´ı funkce (19). Pouˇz´ıv´am zde operace v modulu 32 2 . Narozd´ıl napˇr´ıklad od line´arn´ı kongruentn´ı metody 2.2., kde maxim´aln´ı d´elka cyklu v posloupnosti je d´ana velikost´ı modulu, zde tomu tak nen´ı. U deterministick´e metody, kter´a generuje dalˇs´ı ˇc´ıslo v posloupnosti na z´akladˇe pˇredchoz´ıho prvku, staˇc´ı, aby se nˇekter´ y prvek objevil v posloupnosti podruh´e a dalˇs´ı prvky se jiˇz budou tak´e opakovat. U t´eto metody toto neplat´ı.

4.

Testov´ an´ı kvality n´ ahodn´ ych posloupnost´ı

Pokud m´ame k dispozici nˇejakou posloupnost ˇc´ısel, je dobr´e m´ıt k dispozici tak´e apar´at, kter´ y n´am umoˇzn´ı posoudit, jak moc je tato posloupnost n´ahodn´a. 22

1. 2. 3. 4. 5. .. .

0, 7039153126 0, 7489043886 0, 4302932111 0, 7928773211 0, 9961468480 .. .

236.

0, 3798935058

Tabulka 2.: Posloupnost n´ahodn´ ych ˇc´ısel z´ıskan´ ych z difuze.

ˇ ek totiˇz nen´ı schopen objektivnˇe zhodnotit, zda je urˇcit´a posloupnost ˇc´ısel Clovˇ n´ahodn´a. Pokud nˇekomu napˇr´ıklad d´ame za u ´kol napsat n´ahodnˇe 100 ˇc´ısel, m˚ uˇzeme poˇc´ıtat s t´ım, ˇze pˇr´ıliˇs n´ahodn´a nebudou. Naopak pokud bude m´ıt ˇclovˇek k dispozici posloupnost 100 n´ahodn´ ych ˇc´ısel, je pravdˇepodobn´e, ˇze v nich uvid´ı urˇcit´e vzory [1]. Dokonce dle [8] dva studenti prov´adˇeli v´ yzkum, kde uk´azali, ˇze lze pomˇernˇe pˇresnˇe urˇcit lidi na z´akladˇe posloupnosti n´ahodn´ ych ˇc´ısel, kter´a napsali. Testov´an´ı posloupnost´ı n´ahodn´ ych ˇc´ısel m˚ uˇze b´ yt d˚ uleˇzit´e v r˚ uzn´ ych oblastech lidsk´eho kon´an´ı. V pˇr´ıpadˇe voleb lze tˇreba urˇcit, zda nedoˇslo k manipulaci s v´ ysledky. V ´ır´ansk´ ych prezidentsk´ ych volb´ach v roce 2009, lze v poˇctech hlas˚ u narazit na nesrovnalosti. Pokud vezmeme pˇresn´e poˇcty odevzdan´ ych hlas˚ u v jednotliv´ ych volebn´ıch obvodech, mˇely by b´ yt v´ ysledkem n´ahodn´a ˇc´ısla. Tedy na m´ıstˇe posledn´ı ˇc´ıslice by se mˇelo vyskytovat vˇsech moˇzn´ ych 10 ˇc´ıslic pˇribliˇznˇe stejnˇe ˇcasto. Ve skuteˇcnosti se ale napˇr´ıklad ˇc´ıslice 7 vyskytovala v 17 % pˇr´ıpad˚ u, ˇc´ıslice 5 zase pouze ve 4 % pˇr´ıpad˚ u. To p˚ usob´ı podezˇrele a je pravdˇepodobn´e, ˇze v´ ysledky nˇekdo upravoval. U v´ ysledk˚ u voleb v jin´ ych st´atech se takov´e zvl´aˇstnosti neobjevuj´ı [8].

4.1.

Benford˚ uv z´ akon

Dalˇs´ı zaj´ımav´ y fenom´en vznik´a, pokud vezmeme ˇradu ˇc´ısel, kter´a jsou pozorov´an´ım nˇejak´e veliˇciny. Napˇr´ıklad ceny akci´ı na burze. Pokud se pod´ıv´ame na prvn´ı ˇc´ıslice kaˇzd´e z cen, pˇredpokl´adali bychom, ˇze kaˇzd´a z ˇc´ıslic 1 . . . 9 se v posloupnosti bude pr˚ umˇernˇe vyskytovat se stejnou ˇcetnost´ı – 11, 1 %. Ve skuteˇcnosti tomu tak ovˇsem nen´ı. Pokud bude cen alespoˇ n 100 a budou v rozsahu alespoˇ n tˇr´ı ˇra´d˚ u, dostaneme v´ ysledky podobn´e tˇem v Tab 3. Stejnˇe tak se toto rozdˇelen´ı projev´ı u n´ahodn´e posloupnosti, kde jednotliv´a ˇc´ısla nejsou rovnomˇernˇe rozdˇelena v urˇcit´em intervalu, ale jedn´a se o n´asobky, kter´e jsou rozdˇeleny pˇres nˇekolik ˇra´d˚ u. ˇ Cetnost v´ yskyt˚ u jednotliv´ ych ˇc´ısel z intervalu 1 . . . 9 na m´ıstˇe prvn´ı ˇc´ıslice se ˇr´ıd´ı pravidlem nazvan´ ym Benford˚ uv z´akon (21). Pravdˇepodobnost, ˇze jako prvn´ı 23

1 2 3 4 5 6 7 8 9

30, 103 17, 6091 12, 4939 9, 691 7, 91812 6, 69468 5, 79919 5, 11525 4, 57575

% % % % % % % % %

ˇ Tabulka 3.: Cetnosti v´ yskytu prvn´ıch ˇc´ıslic dle Benfordova z´akona.

ˇc´ıslice dan´eho ˇc´ısla v des´ıtkov´e soustavˇe bude ˇc´ıslo D, je dan´a jako: 1 ). (21) D Pokud budeme pˇredpokl´adat, ˇze toto pravidlo plat´ı, pak by mˇelo platit bez ohledu na zvolen´e mˇeˇr´ıtko. M´ame-li tedy napˇr´ıklad vzd´alenosti, je jedno zda je m´ame uvedeny v metrech nebo milimetrech. Rozdˇelen´ı by mˇelo b´ yt nemˇenn´e. Vezmeme nyn´ı funkci p(x), kter´a oznaˇcuje hustotu rozdˇelen´ı pravdˇepodobnosti veliˇciny a kter´a je pro n´as nezn´am´a. Pokud je rozdˇelen´ı nemˇenn´e, pro konstantu k plat´ı, ˇze [9] p(kx) = f (k)p(x). (22) ∫ ∫ Protoˇze pro hustotu rozdˇelen´ı plat´ı p(x) dx = 1, plat´ı p(kx) dx = k1 . Z toho plyne, ˇze f (x) = k1 . Budeme-li derivovat (22) vzhledem k promˇenn´e k, tak pro k = 1 dostaneme diferenci´aln´ı rovnici [9] PD = log10 (1 +

x · p′ (x) = −p(x)

(23)

1 y′ = − y x∫ ∫ 1 1 dy = − dx y x ∫ 1 ln(y) = − dx + ln(C) x

(24)

a po po substituci y = p(x)

y = C · e−

∫

1 x

dx

y = C · e− ln(x) C y= x 24

dostaneme p(x) = x1 za pˇredpokladu, ˇze integraˇcn´ı konstanta C = 1. Nyn´ı potˇrebujeme vyj´adˇrit pravdˇepodobnost, ˇze ˇc´ıslo zaˇc´ınaj´ıc´ı ˇc´ıslic´ı D padne do intervalu mezi D a D + 1. Do tohoto intervalu padne kaˇzd´e ˇc´ıslo, kter´e m´a jako prvn´ı ˇc´ıslici D. V des´ıtkov´e soustavˇe je poˇcet vˇsech moˇznost´ı d´an jako ∫ 10 p(x) dx (25) 1

a poˇcet pˇr´ızniv´ ych moˇznost´ı, kdy ˇc´ıslo padne do urˇcen´eho intervalu je pak ∫ D+1 p(x) dx. (26) D

Pravdˇepodobnost je potom ∫ D+1 p(x) dx ln(D + 1) − ln(D) 1 PD = ∫D10 = log10 (D+1)−log10 (D) = log10 (1+ ), = ln(10) − ln(1) D p(x) dx 1 (27) coˇz je (21). Poprv´e se o tomto fenom´enu zm´ınil v roce 1881 matematik a astronom Simon Newcomb bez dalˇs´ıho koment´aˇre. V roce 1938 tento jev popisuje podrobnˇe fyzik Frank Benford, kter´ y si vˇsiml, ˇze logaritmick´e tabulky jsou v´ıce ohmatan´e na stran´ach s ˇc´ısly, kter´a zaˇc´ınaj´ı ˇc´ıslem 1. V dneˇsn´ı dobˇe pouˇz´ıvaj´ı nˇekter´e st´aty Benfordova z´akona napˇr´ıklad k odhalov´an´ı faleˇsn´ ych daˇ nov´ ych pˇrizn´an´ı [8]. Nyn´ı se zamˇeˇr´ıme na to, jak´ ym zp˚ usobem urˇcit, zda je posloupnost ˇc´ısel n´ahodn´a. Existuje v´ıce postup˚ u, jak otestovat n´ahodnost posloupnosti. J´a jsem v t´eto pr´aci zvolil dva. Nejprve si pˇredstav´ıme χ2 test (4.2.), coˇz je z´akladn´ı statistick´ y test. Pot´e pop´ıˇseme π test (4.3.), kter´ y jsem navrhl v t´eto pr´aci, kde n´ahodnost posloupnosti urˇc´ıme pomoc´ı aproximace ˇc´ısla π.

4.2.

χ2 test

χ2 test (ch´ı-kvadr´at test), tak´e oznaˇcovan´ y jako test dobr´e shody, je z´akladn´ım statistick´ ym testem, kter´ y umoˇzn ˇuje urˇcit, jak se pozorov´an´ı jev˚ u liˇs´ı od pˇredpokladu. M˚ uˇzeme si to uk´azat na h´azen´ı ˇsestibokou hrac´ı kostkou. M´ameli klasickou hrac´ı kostku, v´ ysledkem hodu je ˇc´ıslo 1 aˇz 6. Pokud nen´ı kostka upraven´a, je pravdˇepodobnost, ˇze padne konkr´etn´ı ˇc´ıslo P = 16 . Provedemeli 36 pokus˚ u, mˇelo by kaˇzd´e ˇc´ıslo padnout 6 kr´at. Vˇsech moˇznost´ı, jak lze 36 kr´at za sebou hodit hrac´ı kostkou je 636 a vˇsechny moˇznosti jsou stejnˇe pravdˇepodobn´e. I to, ˇze 36 kr´at za sebou padne stejn´e ˇc´ıslo. Mus´ıme m´ıt tedy nˇejakou moˇznost poznat, kdy jsou hody opravdu n´ahodn´e a kdy se jedn´a o z´asah zvenˇc´ı. Sice nem˚ uˇzeme jednoznaˇcnˇe ˇr´ıci, zda jsou hody n´ahodn´e, ale m˚ uˇzeme s urˇcitou pravdˇepodobnost´ı tvrdit, ˇze by n´ahodn´e b´ yt mˇely. Pouˇzijeme k tomu 25

χ2 test. Rozdˇel´ıme obor hodnot n´ahodn´e veliˇciny do r disjunktn´ıch ˇca´st´ı. Je-li Yi n´ahodn´a veliˇcina s pˇredpokl´adan´ ym rozdˇelen´ım, potom 2

χ =

r ∑

Yi2

(28)

i=1

m´a χ2 rozdˇelen´ı s v stupni volnosti [7]. Z (28) odvod´ıme χ2 =

r ∑ (xi − npi )2

npi

i=1

,

(29)

kde xi znaˇc´ı, kolikr´at dan´e ˇc´ıslo i padlo, n je poˇcet pokus˚ u a pi je pravdˇepodobnost, ˇze jev nastane. Tedy npi je pˇredpokl´adan´a hodnota xi [1]. D´ale budeme definovat v = r − 1, jako stupeˇ n volnosti. Stupeˇ n volnosti ud´av´a poˇcet nez´avisle stanoven´ ych kategori´ı, do kter´ ych m˚ uˇzeme rozdˇelit v´ ysledky vˇsech pozorov´an´ı – definiˇcn´ı obor. Pokud rozdˇel´ıme zn´am´ y definiˇcn´ı obor n´ahodn´e veliˇciny na r ˇc´ast´ı, nez´avisl´ ych je jich pouze r − 1. Vyjdeme-li z toho, ˇze n=

r ∑

xi ,

(30)

i=1

kde n je definiˇcn´ı obor, x1 , . . . , xr jsou poˇcty pokus˚ u v jednotliv´ ych kategori´ıch a toho, ˇze zn´ame hodnotu n a hodnoty x1 . . . xr−1 , pak m˚ uˇzeme urˇcit xr = n − (x1 + . . . + xr−1 ).

(31)

Tedy xr nen´ı nez´avisl´a. Proto je v = r − 1. Pˇ r´ıklad 5. Pokud pouˇzijeme hodnoty ze skuteˇcn´ych 36 hod˚ u kostkou (Tab. 4.), m´ame n = 36. Vid´ıme, ˇze 1 padla 3 kr´at, 2 padla 10 kr´at, atd. M˚ uˇzeme tedy definovat x1 = 3, x2 = 10, x3 = 7, x4 = 6, x5 = 5. I kdybychom nevˇedˇeli, ˇze x6 = 5, mohli bychom pomoc´ı (31) urˇcit, ˇze x6 = 36 − (3 + 10 + 7 + 6 + 5) = 5.

(32)

Stejnˇe tak bychom mohli urˇcit libovolnou xi , pokud bychom znali zb´yvaj´ıc´ı. ˇ ıslo(i) C´ 1 Skuteˇ cnost(xi ) 3 Pˇ redpoklad(npi ) 6

2 3 10 7 6 6

4 6 6

5 5 6

6 5 6

Tabulka 4.: Skuteˇcn´ y a pˇredpokl´adan´ y v´ ysledek 36 hod˚ u kostkou.

26

M´ame-li hodnoty z pokusu s hrac´ı kostkou (Tab. 4.), m˚ uˇzeme spoˇc´ıtat hodnotu χ2 . ˇ adek Skuteˇcnost(xi ) oznaˇcuje, kolikr´at padlo dan´e ˇc´ıslo, ˇr´ R´ adek Pˇredpoklad(npi ) oznaˇcuje, kolikr´at mˇelo dan´e ˇc´ıslo padnout dle pravdˇepodobnosti. χ2 =

(3 − 6)2 (10 − 6)2 (7 − 6)2 (6 − 6)2 (5 − 6)2 (5 − 6)2 . + + + + + = 4, 67 (33) 6 6 6 6 6 6

Nyn´ı jeˇstˇe potˇrebujeme zjistit, zda v´ ysledek 4, 67 z Pˇr. 5 odpov´ıd´a naˇsim pˇredpoklad˚ um o n´ahodnosti hodu kostkou. Pouˇzijeme k tomu tabulku (Tab. 5.), kde jsou vypsan´e hodnoty χ2 pro vybran´e hladiny v´ yznamnosti a stupnˇe volnosti. Pod´ıv´ame-li se tedy do tabulky (Tab. 5.), vid´ıme, ˇze pro stupeˇ n volnosti v = 5

v v v v v v

=1 =2 =3 =4 =5 =6 .. .

p = 5% p = 25% 0, 00393 0, 1015 0, 1026 0, 5754 0, 3518 1, 213 0, 7107 1, 923 1, 1455 2, 675 1, 635 3, 455 .. .. . .

p = 50% 0, 4549 1, 386 2, 366 3, 357 4, 351 5, 348 .. .

p = 75% 1, 323 2, 773 4, 108 5, 385 6, 626 7, 841 .. .

p = 95% 3, 841 5, 991 7, 815 9, 488 11, 07 12, 59 .. .

Tabulka 5.: Hodnoty χ2 pro vybran´e hladiny v´ yznamnosti a stupnˇe volnosti [1].

se v hladinˇe v´ yznamnosti p = 95% nach´az´ı hodnota 11, 07. Hladina v´ yznamnosti n´am ˇr´ık´a, ˇze pokud prob´ıhaj´ı pozorov´an´ı jevu v souladu s pˇredpokladem, je hodnota χ2 ≤ 11, 07 v 95% pˇr´ıpad˚ u. Chceme-li testovat n´ahodnost posloupnosti, bylo 2 by dobr´e, aby se hodnota χ pohybovala kolem hodnoty pro hladinu v´ yznamnosti 50%. Pokud bude totiˇz pˇr´ıliˇs n´ızk´a, bude se bl´ıˇzit naˇsemu pˇredpokladu, coˇz ale znamen´a, ˇze posloupnost v´ ysledk˚ u pokusu nen´ı pˇr´ıliˇs n´ahodn´a (pˇripomeˇ nme, ˇze pˇredpoklad je v naˇsem pˇr´ıkladu 6 jedniˇcek, 6 dvojek, . . . ). Pokud bude pˇr´ıliˇs vysok´a, znamen´a to pravdˇepodobnˇe, ˇze ve v´ ysledku pokus˚ u je nˇejak´a anom´alie – nˇekter´e ˇc´ıslo pad´a ˇcastˇeji neˇz ostatn´ı (pˇri skuteˇcn´em h´azen´ı kost. kou se pravdˇepodobnˇe jedn´a o upravenou kostku). V Pˇr. 5 je hodnota χ2 = 4, 67, hodnota je tedy bl´ızko hodnoty pro hladinu v´ yznamnosti 50% ve stupni volnosti 5. M˚ uˇzeme prohl´asit, ˇze test byl pravdˇepodobnˇe proveden s neupravenou pravidelnou kostkou. Pro test n´ahodnosti posloupnosti budeme simulovat h´azen´ı kostkou a pro v´ ysledek pozorov´an´ı spoˇc´ıt´ame hodnotu χ2 . Pokud bude hodnota 2, 675 < χ2 < 6, 626 (tedy v rozsahu p = 25% aˇz p = 75% ve stupni volnosti 5, viz Tab. 5.),

27

prohl´as´ıme posloupnost za dostateˇcnˇe n´ahodnou. Pro jednoduˇsˇs´ı a rychlejˇs´ı implementaci si uprav´ıme (29) n´asledovnˇe r 1 ∑ (xi − npi )2 , χ = npi i=1 2

(34)

coˇz m˚ uˇzeme udˇelat, nebot’ pˇri h´azen´ı jednou kostkou je pravdˇepodobnost padnut´ı kaˇzd´eho ˇc´ısla 61 . Pomoc´ı (34) pak implementujeme algoritmus 7. (7) Chi-square-test 1: procedure chi-square-test(sequence) ▷ V´ ystupem je χ2 2: categories[6] ← 0, 0, 0, 0, 0, 0 ▷ Kategorie 3: for i ← 0, size-of(sequence) − 1 do 4: n ← sequence[i] · 6 5: categories[n − 1] ← categories[n − 1] + 1 6: end for 7: result ← 0 8: npi ← size-of(sequence)/6 ▷ Kaˇzd´e ˇc´ıslo padne s pravdˇepodobnost´ı 16 9: for i ← 0, 5 do 10: x ← categories[i] − npi 11: result ← result + x · x 12: end for 13: result ← result/npi 14: return result 15: end procedure

4.3.

π test

V r´amci t´eto pr´ace jsem navrhl test, kter´ y umoˇzn ˇuje urˇcit n´ahodnost posloupnosti ˇc´ısel pomoc´ı aproximace hodnoty ˇc´ısla π. Podstatou tohoto testu je geometrick´a pravdˇepodobnost a probl´em Buffonovy jehly [6]. Ten m˚ uˇzeme formulovat napˇr´ıklad takto: Mˇejme jehlu d´elky a a plochu, na kter´e jsou nakresleny rovnobˇeˇzn´e linky ve ” vzd´alenosti 2a. Jestliˇze na tuto plochu pouˇst´ıme jehlu, pak se pomˇer celkov´eho poˇctu pokus˚ u n k poˇctu pokus˚ u, kdy se jehla dot´ yk´a nˇekter´e linky h, bl´ıˇz´ı ˇc´ıslu π, nebo-li nh ≈ π.“ D´ale v t´eto kapitole budeme oznaˇcovat: • a d´elka jehly, 28

• e vzd´alenost mezi linkami (e = 2a), • n poˇcet pokus˚ u, • h poˇcet pokus˚ u, kdy se jehla dot´ yk´a linky nebo prot´ın´a linku. Pravdˇepodobnost P , ˇze jehla protne linku je P =

h . n

(35)

Tuto pravdˇepodobnost si nyn´ı vyj´adˇr´ıme tak´e pomoc´ı geometrick´e pravdˇepodobnosti, abychom mohli sestavit algoritmus pro testov´an´ı posloupnosti n´ahodn´ ych ˇc´ısel. Mˇejme tedy linky ve vzd´alenosti e = 2a, jedna z linek (α) je protnuta jehlou, coˇz je u ´seˇcka CD (Obr. 5.). Poloha jehly vzhledem k lince je d´ana 2 parametry. Prvn´ı je x, coˇz je vzd´alenost stˇredu jehly E od nejbliˇzˇs´ı linky α a druh´ y je u ´hel θ, coˇz je u ´hel, kter´ y sv´ır´a jehla s nejbliˇzˇs´ı linkou α (Obr. 5.). Stˇred jehly E nem˚ uˇze b´ yt, pˇri jak´emkoliv dopadu jehly, ve vˇetˇs´ı vzd´alenosti neˇz D 1 2a

α 1 2a

x

· sinθ

θ E

H

C

Obr´azek 5.: Protnut´ı linky α jehlou (´ useˇcka CD). a vzhledem k nejbliˇzˇs´ı lince. Tedy vˇsechny moˇznosti dopadu jehly jsou pak ∫ π a dθ. (36) 0

Aby jehla mohla protnout linku, je tˇreba, aby platilo x ≤ moˇznosti, kdy jehla prot´ın´a linku, m˚ uˇzeme vyj´adˇrit jako ∫ π 1 a · sinθ dθ. 0 2 29

1 a 2

· sinθ. Pˇr´ızniv´e

(37)

Pravdˇepodobnost protnut´ı linky jehlou urˇcujeme v rozsahu ⟨0; π⟩. Pokud je u ´hel θ roven π2 , m˚ uˇze x nab´ yvat hodnot ⟨0; a2 ⟩, aby doˇslo k protnut´ı linky. Naopak, pokud je θ rovno 0 nebo π, mus´ı b´ yt x = 0, jinak by k protnut´ı nedoˇslo. Pravdˇepodobnost je pak vyj´adˇrena vztahem (38) ∫π 1 ∫π 1 a · sinθ dθ a 0 sinθ dθ 1 2 0 2∫ P = = = . (38) π aπ π a dθ 0 Pˇribliˇznou hodnotu ˇc´ısla π z´ısk´ame pomoc´ı h 1 ≈ , n π

(39)

n . (40) h Vydˇel´ıme poˇcet vˇsech pokus˚ u poˇctem u ´spˇeˇsn´ ych pokus˚ u (kdy jehla protne linku) ˇ a z´ısk´ame pˇribliˇznou hodnotu π. C´ım v´ıce pokus˚ u provedeme, t´ım pˇresnˇejˇs´ı hodnotu z´ısk´ame. Test je tedy zaloˇzen na u ´vaze, ˇze pokud budeme m´ıt kvalitn´ı posloupnost n´ahodn´ ych ˇc´ısel, mˇeli bychom se bl´ıˇzit k hodnotˇe ˇc´ısla π. V algoritmu budeme potˇrebovat 2 parametry, x pro vzd´alenost stˇredu jehly od nejbliˇzˇs´ı linky (E na Obr. 5.) v rozsahu ⟨0; 1⟩ a u ´hel θ pro velikost u ´hlu, kter´ y sv´ır´a jehla a linka v rozsahu ⟨0; π⟩. Pouˇzijeme 2 n´ahodn´a ˇc´ısla z posloupnosti tak, ˇze x = xn a θ = πxn+1 . Potom porovn´ame, zda plat´ı x ≤ 0, 5 · sinθ. Pokud plat´ı, jehla prot´ın´a linku α a m˚ uˇzeme pokus oznaˇcit jako u ´spˇeˇsn´ y. Jestliˇze plat´ı x > 0, 5 · sinθ, potom jehla nem˚ uˇze linku α protnout a pokus je ne´ uspˇeˇsn´ y. Nakonec vydˇel´ıme poˇcet vˇsech pokus˚ u poˇctem u ´spˇeˇsn´ ych pokus˚ u a v´ ysledkem je aproximace ˇc´ısla π, viz algoritmus 8. π≈

4.4.

Hodnocen´ı gener´ ator˚ u n´ ahodn´ ych posloupnost´ı

Zde si struˇcnˇe pˇredstav´ıme v´ ysledky testov´an´ı posloupnost´ı n´ahodn´ ych ˇc´ısel, generovan´ ych jednotliv´ ymi metodami pˇredstaven´ ymi v t´eto pr´aci. Soubory s testovac´ımi daty jsou pˇriloˇzeny na CD v adres´aˇri data/. Pˇri hodnocen´ı budu vyuˇz´ıvat v´ ystupu z programu Vengeance 5.2. 4.4.1.

Middle square a middle square improved

Nejprve otestujeme p˚ uvodn´ı metodu middle square 2.2. a potom jej´ı variantu middle square improved. Testovac´ı data pro tuto metodu jsou uloˇzena v souborech AAAmiddle-square-12354871.txt, AAAmiddle-square-87564398.txt a AAAmiddle-square-53111760440.txt. Jako sem´ınko byla pouˇzita hodnota x0 = 12354871 a testovalo se 100000 hodnot.

30

(8) Pi-test 1: procedure pi-test(sequence) 2: n←0 3: h←0 4: i←0 5: while i < size-of(sequence) do 6: x ← sequence[i] 7: θ ← π · sequence[i + 1] 8: if x ≤ 0.5 · sin(θ) then 9: h←h+1 10: end if 11: n←n+1 12: i←i+1 13: end while 14: return n/h 15: end procedure

▷ V´ ystupem je aproximace ˇc´ısla π ▷ Poˇcet vˇsech pokus˚ u ▷ Poˇcet u ´spˇeˇsn´ ych pokus˚ u

********** Chi-square test Size of sequence: 100000 Chi-squared: 98817.531201 * Value is not in an expected interval. Randomness is insufficient. ********** Pi test Size of sequence: 100000 Pi approximation: 1.004046 Difference: 2.137546 Difference in %: 68.040213 D´ale byla jako sem´ınko pouˇzita hodnota x0 = 87564398 a testovalo se 100000 hodnot. ********** Chi-square test Size of sequence: 100000 Chi-squared: 69949.731549 * Value is not in an expected interval. Randomness is insufficient. ********** 31

Pi test Size of sequence: 100000 Pi approximation: 1.125809 Difference: 2.015783 Difference in %: 64.164381 Nakonec byla jako sem´ınko pouˇzita hodnota x0 = 53111760440 a testovalo se 1000000 hodnot. ********** Chi-square test Size of sequence: 1000000 Chi-squared: 40.428474 * Value is not in an expected interval. Randomness is insufficient. ********** Pi test Size of sequence: 1000000 Pi approximation: 3.148050 Difference: 0.006457 Difference in %: 0.205532 Nyn´ı spust´ıme testy s daty vygenerovan´ ymi metodou middle square improved. Vstupn´ı u ´daje jsou stejn´e. Data jsou uloˇzena v souborech AAAmiddlesquare-improved-12354871.txt, AAAmiddle-square-improved-87564398.txt a AAAmiddle-square-improved-53111760440.txt. Jako sem´ınko byla pouˇzita hodnota x0 = 12354871 a testovalo se 100000 hodnot. ********** Chi-square test Size of sequence: 100000 Chi-squared: 45.219849 * Value is not in an expected interval. Randomness is insufficient. ********** Pi test Size of sequence: 100000 Pi approximation: 3.166260 32

Difference: 0.024668 Difference in %: 0.785197 D´ale byla jako sem´ınko pouˇzita hodnota x0 = 87564398 a testovalo se 100000 hodnot. ********** Chi-square test Size of sequence: 100000 Chi-squared: 39.407536 * Value is not in an expected interval. Randomness is insufficient. ********** Pi test Size of sequence: 100000 Pi approximation: 3.160057 Difference: 0.018464 Difference in %: 0.587735 Nakonec byla jako sem´ınko pouˇzita hodnota x0 = 53111760440 a testovalo se 1000000 hodnot. ********** Chi-square test Size of sequence: 1000000 Chi-squared: 61.476306 * Value is not in an expected interval. Randomness is insufficient. ********** Pi test Size of sequence: 1000000 Pi approximation: 3.138161 Difference: 0.003432 Difference in %: 0.109244 Jak vid´ıme v tabulce Tab. 6., metoda middle square improved d´av´a obvykle lepˇs´ı v´ ysledky. To, ˇze hodnota χ2 je mimo oˇcek´avan´ y rozsah je d´ano nepˇr´ıliˇs kvalitn´ım algorimem renew viz algoritmus 3. Bylo by tedy vhodn´e tento algoritmus vylepˇsit. Zaj´ımav´ y v´ ysledek pak d´av´a posledn´ı test, kdy je pouˇzit vˇetˇs´ı rozsah generov´an´ı ˇc´ısel, kdy jsou v´ ysledky obou metod srovnateln´e. To je zp˚ usobeno t´ım, 33

x0 = 12354871 x0 = 87564398 x0 = 53111760440

middle square χ2 π≈ 98817, 531201 1, 004046 69949, 731549 1, 125809 40, 428474 3, 148050

middle square imp. χ2 π≈ 45, 219849 3, 166260 39, 407536 3, 160057 61, 476306 3, 138161

Tabulka 6.: Porovn´an´ı v´ ysledk˚ u metod middle square a middle square improved.

ˇze v pˇr´ıpadˇe vˇetˇs´ıho rozsahu hodnot, je menˇs´ı pravdˇepodobnost v´ yskytu problematick´eho ˇclenu posloupnosti. Co je problematick´ y ˇclen je pops´ano v ˇc´asti 2.2.. Pro praktick´e pouˇzit´ı lze tedy doporuˇcit sp´ıˇse metodu middle square improved, i kdyˇz v pˇr´ıpadˇe, ˇze se pouˇzij´ı vhodnˇe zvolen´e parametry, m˚ uˇze i metoda middle square d´avat sluˇsn´e v´ ysledky. 4.4.2.

Line´ arn´ı kongruentn´ı metoda

Do rodiny line´arn´ı kongruentn´ıch patˇr´ı i gener´ator RANDU 2.3.1., kter´ y nyn´ı otestujeme. Test provedeme s daty v souboru AAArandu-1.txt. Jako sem´ınko je zvoleno x0 = 1. ********** Chi-square test Size of sequence: 100000 Chi-squared: 5.240370 * Value is in an expected interval. Randomness is sufficient. ********** Pi test Size of sequence: 100000 Pi approximation: 3.162755 Difference: 0.021163 Difference in %: 0.673631 Druh´ y test provedeme s daty v souboru AAArandu-16385.txt. Sem´ınko je v tomto pˇr´ıpadˇe x0 = 16385. Jedn´a se tedy opˇet o lich´e ˇc´ıslo, coˇz je vstupn´ı podm´ınka pro gener´ator RANDU. ********** Chi-square test 34

Size of sequence: 100000 Chi-squared: 4.069003 * Value is in an expected interval. Randomness is sufficient. ********** Pi test Size of sequence: 100000 Pi approximation: 3.137058 Difference: 0.004535 Difference in %: 0.144340 Vid´ıme, ˇze v´ ysledky jsou dobr´e a algoritmus je pro urˇcit´e typy u ´loh vhodn´ y. Bohuˇzel jeho vlastnost, kdy se vygenerovan´e body v trojrozmˇern´em prostoru uspoˇra´d´avaj´ı do paraleln´ıch rovin, tyto statistick´e testy neodhal´ı. Pˇri praktick´em pouˇzit´ı bychom mˇeli zv´aˇzit, zda tato vlastnost neovlivn´ı kvalitu v´ ysledk˚ u. Ve prospˇech RANDU hovoˇr´ı pˇredevˇs´ım jednoduch´a a rychl´a implementace. 4.4.3.

Difuze

Jako posledn´ı otestujeme metodu z´ısk´av´an´ı n´ahodn´ ych ˇc´ısel pomoc´ı pozorov´an´ı difuze v kapalin´ach. Tato metoda se od pˇredchoz´ıch liˇs´ı, nebot’ se nejedn´a o pseudon´ahodn´a ˇc´ısla, generovan´a matematick´ ym pˇredpisem. Data jsou uloˇzena v souboru AAAdiffusion.txt. ********** Chi-square test Size of sequence: 1318 Chi-squared: 2.812785 * Value is in an expected interval. Randomness is sufficient. ********** Pi test Size of sequence: 1318 Pi approximation: 3.138095 Difference: 0.003497 Difference in %: 0.111326 Hodnota χ2 je v pˇredpokl´adan´em rozsahu a ukazuje na dobrou n´ahodnost posloupnosti. Hodnota aproximace π je tak´e velice dobr´a, i kdyˇz m´ame k dispozici pouze 1318 hodnot. Aby byla aproximace ˇc´ısla π pˇresnˇejˇs´ı, je tˇreba otestovat 35

v ide´aln´ı pˇr´ıpadˇe alespoˇ n desetitis´ıce hodnot. Tato metoda se jev´ı jako vhodn´a k z´ısk´av´an´ı n´ahodn´ ych ˇc´ısel a pˇri pouˇzit´ı dokonalejˇs´ı haˇsovac´ı funkce by mohla b´ yt pouˇziteln´a i pro kryptografii. Bylo by ovˇsem vhodn´e prov´est testov´an´ı na vˇetˇs´ım mnoˇzstv´ı dat.

5. 5.1.

Knihovna random a program Vengeance Knihovna random

V r´amci t´eto pr´ace jsem implementoval vˇsechny popisovan´e algoritmy v programovac´ım jazyku C. Tento programovac´ı jazyk jsem zvolil z d˚ uvodu dostupnosti prakticky na vˇsech platform´ach, snadn´emu linkov´an´ı z r˚ uzn´ ymi programovac´ımi jazyky a tak´e kv˚ uli vysok´emu v´ ykonu v´ ysledn´eho k´odu. Knihovnu by mˇelo b´ yt moˇzn´e pˇreloˇzit a pouˇz´ıvat na nejbˇeˇznˇejˇs´ıch platform´ach. J´a jsem ji vyv´ıjel a testoval na syst´emu OS X. V t´eto kapitole jsou pops´any veˇrejnˇe dostupn´e funkce t´eto knihovny. Knihovna obsahuje n´asleduj´ıc´ı funkce: unsigned long long middle_square(unsigned long long previous, int digits) Toto je implementace p˚ uvodn´ı metody middle square (2.2.). Vstupem je pˇredchoz´ı ˇclen posloupnosti a poˇcet ˇc´ıslic v´ ysledn´eho ˇc´ısla. unsigned long long middle_square_improved(unsigned long long previous, int digits) Tato funkce implementuje upravenou metodu middle square, jak je pops´ana v pˇr´ısluˇsn´e kapitole (2.2.). Vstupem je pˇredchoz´ı ˇclen posloupnosti a poˇcet ˇc´ıslic v´ ysledn´eho ˇc´ısla. unsigned long long lcm(unsigned long long m, int a, int c, unsigned long long x0) Tato funkce implementuje obecn´ y line´arn´ı kongruentn´ı gener´ator (2.2.). Vstupem jsou parametry m – modul, a – multiplikativn´ı konstanta, c – aditivn´ı konstanta a pˇredchoz´ı ˇclen posloupnosti. unsigned int randu(unsigned int previous) Tato funkce implementuje gener´ator RANDU (2.3.1.). I kdyˇz by ˇsel pouˇz´ıt obecn´ y line´arn´ı kongruentn´ı gener´ator, neprojevila by se hlavn´ı v´ yhoda gener´atoru – vysok´a rychlost. Vstupem je pˇredchoz´ı ˇclen posloupnosti. Jako sem´ınko se pouˇz´ıv´a lich´e ˇc´ıslo. 36

unsigned int diffusion(char *image) Implementace metody z´ısk´av´an´ı n´ahodn´ ych ˇc´ısel ze sn´ımku difuze. Jako vstup se pˇred´av´a adresa ˇretˇezce, reprezentuj´ıc´ı horizont´aln´ı ˇr´adek sn´ımku. Form´at dat je pops´an v kapitole 3.2. unsigned long long blum_blum_shub(unsigned long long *previous, unsigned long long modulus) Implementace metody Blum Blum Shub (2.3.2.). Pro kvalitnˇejˇs´ı v´ ystup by bylo vhodnˇejˇs´ı pouˇz´ıt vˇetˇs´ı ˇc´ısla. Z praktick´ ych d˚ uvod˚ u zde pouˇz´ıv´am pouze 64 bitov´a. Pˇri pouˇzit´ı vˇetˇs´ıch ˇc´ısel by bylo tˇreba pouˇz´ıt extern´ı knihovnu. Vstupem je pˇredchoz´ı hodnota a modul. Zdrojov´e k´ody knihovny jsou uloˇzeny v souborech random.h a random.c. Po pˇreloˇzen´ı pˇrekladaˇcem vznikne bin´arn´ı knihovna, kterou je jiˇz moˇzno pouˇz´ıt v programu napsan´em v jazyku C. Takto ji pouˇz´ıv´a program Vengeance 5.2.

5.2.

Program Vengeance

Pro testov´an´ı n´ahodnosti posloupnosti ˇc´ısel s uniformn´ım rozdˇelen´ım (2.1.), jsem v r´amci t´eto pr´ace vytvoˇril program Vengeance. Umoˇzn ˇuje otestovat n´ahodnost zadan´e posloupnosti, pˇr´ıpadnˇe i vygenerovat posloupnost pomoc´ı knihovny random (5.1.). Generov´an´ı posloupnosti je dostupn´e pouze ve verzi s GUI. Program je moˇzno provozovat jako GUI aplikaci na operaˇcn´ım syst´emu OS X nebo jako aplikaci pro textov´ y termin´al, kde by aplikace mˇela j´ıt pˇreloˇzit na nejbˇeˇznˇejˇs´ıch syst´emech s pˇrekladaˇcem jazyka C. GUI verze aplikace je sestavena a testov´ana na syst´emu OS X verze 10.8. 5.2.1.

Uˇ zivatelsk´ y pohled

V t´eto ˇca´sti si pˇredstav´ıme aplikaci z pohledu uˇzivatele. Nejprve se pod´ıv´ame na GUI verzi a potom se zbˇeˇznˇe zm´ın´ıme o verzi pro pˇr´ıkazovou ˇr´adku. Na Obr. 6. vid´ıme, jak vypad´a hlavn´ı okno aplikace. V lev´e ˇca´sti je tabulka, kter´a zobrazuje posloupnost ˇc´ısel. Prav´a ˇc´ast je vyhrazena pro zobrazen´ı v´ ysledk˚ u test˚ u. Pomoc´ı z´aloˇzek se lze pˇrep´ınat mezi obˇema testy. Tlaˇc´ıtkem Spustit je moˇzno spustit vybran´ y test. Aplikace se d´ale ovl´ad´a z hlavn´ıho menu. Pop´ıˇseme si pouze poloˇzky, kter´e se t´ ykaj´ı pˇr´ımo aplikace Vengeance, zbytek poloˇzek v menu je standardn´ı pro kaˇzdou aplikaci na syst´emu OS X. Nejprve si pop´ıˇseme poloˇzky v nab´ıdce Soubor. Ta obsahuje tyto poloˇzky: • Nov´a middle square. . . vytvoˇr´ı novou posloupnost pomoc´ı metody middle square; 37

Obr´azek 6.: Hlavn´ı okno aplikace Vengeance v GUI verzi. • Nov´a LC. . . vytvoˇr´ı novou posloupnost pomoc´ı line´arn´ı kongruentn´ı metody; • Nov´a RANDU. . . vytvoˇr´ı novou posloupnost pomoc´ı metody RANDU; • Otevˇr´ıt. . . otevˇre soubor, kter´ y obsahuje ˇc´ıselnou posloupnost. Data v souboru by mˇela b´ yt uspoˇra´d´ana tak, ˇze kaˇzd´e ˇc´ıslo je na zvl´aˇstn´ım ˇra´dku a jako oddˇelovaˇc desetinn´ ych m´ıst se pouˇz´ıv´a znak .“. Napˇr´ıklad: ” 0.0000305190 0.0001831097 0.0008239872 0.0032959362 Dalˇs´ı poloˇzkou v menu je nab´ıdka Akce, kde se nach´azej´ı poloˇzky pro ovl´ad´an´ı jednotliv´ ych test˚ u. Obsahuje tyto poloˇzky: • Spustit χ2 test vyvol´a stejnou akci, jako stisknut´ı tlaˇc´ıtka Spustit na z´aloˇzce χ2 test; • Spustit π test vyvol´a stejnou akci, jako stisknut´ı tlaˇc´ıtka Spustit na z´aloˇzce π test. V aplikaci je tak´e vestavˇena z´akladn´ı n´apovˇeda, kde je struˇcnˇe pops´ano ovl´ad´an´ı aplikace. Aplikace Vengeance je dostupn´a tak´e jako program urˇcen´ y pro pˇr´ıkazovou ˇra´dku. V t´eto verzi nefunguje generov´an´ı posloupnost´ı, je zamˇeˇrena pouze na testov´an´ı jiˇz vytvoˇren´e posloupnosti ze souboru. Pokud program vyvol´ame bez parametr˚ u napˇr´ıklad pˇr´ıkazem ./vengeancecmd, program vyp´ıˇse n´apovˇedu pouˇzit´ı. 38

Pokud chceme prov´est testy, je tˇreba program vyvolat pomoc´ı ./vengeancecmd jmeno-souboru a program naˇcte pˇr´ısluˇsn´ y soubor a spust´ı oba testy. V´ ysledek pak vyp´ıˇse na obrazovku. 5.2.2.

Program´ atorsk´ y pohled

V´ ykonn´a ˇca´st aplikace Vengeance je platformnˇe nez´avisl´a. Abychom toho dos´ahli, jsou v´ ykonn´e algoritmy naprogramov´any v jazyku C. Tyto algoritmy jsou uloˇzeny v souborech test module.h a test module.c. Funkce z tohoto modulu jsou pak vol´any jak z GUI aplikace, tak z aplikace pro pˇr´ıkazovou ˇra´dku. Modul test module obsahuje funkce: int load_data(char *) Naˇcte data ze zadan´eho souboru do pamˇeti. Postar´a se rovnˇeˇz o alokaci dostateˇcn´eho m´ısta v pamˇeti. Pokud nastane chyba, vr´at´ı ji v n´avratov´em k´odu. double chi_square(double *, int) Spoˇc´ıt´a hodnotu χ2 pro zadanou posloupnost. Jako druh´ y parametr je poˇcet ˇc´ısel v posloupnosti. double pi_test(double *, int) Spoˇc´ıt´a aproximaci hodnoty π pro zadanou posloupnost. Jako druh´ y parametr je poˇcet ˇc´ısel v posloupnosti. int int int int

new_middle_square(unsigned long long, int, int) new_middle_square_improved(unsigned long long, int, int) new_lcm(unsigned long long, int, int, unsigned long long, int) new_randu(unsigned int, int)

Vygeneruj´ı pˇr´ısluˇsn´e posloupnosti pomoc´ı metod, kter´e jsou implementovan´e v knihovnˇe random 5.1. Textov´a verze aplikace d´ale obsahuje v souboru main.c obsluˇzn´ y k´od pro zajiˇstˇen´ı komunikace pˇres pˇr´ıkazovou ˇr´adku. GUI verze aplikace je naps´ana v programovac´ım jazyku Objective-C a obsahuje 2 tˇr´ıdy, kter´e jsou nutn´e pro obsluhu grafick´eho rozhran´ı. Jedn´a se o tˇr´ıdy: • NITableViewDelegate je deleg´atn´ı tˇr´ıda, kter´a m´a na starosti obsluhu zobrazov´an´ı hodnot v tabulce, kter´a je v lev´e ˇc´asti hlavn´ıho okna aplikace (Obr. 6.); • NIAppDelegate je deleg´atn´ı tˇr´ıda cel´e aplikace, kde jsou oˇsetˇreny veˇsker´e ud´alosti v GUI. V GUI verzi je pak jeˇstˇe pˇr´ıtomen soubor MainMenu.xib, kter´ y obsahuje samotn´e hlavn´ı okno aplikace, menu a propojen´ı na metody tˇr´ıdy NIAppDelegate. Sestaven´ı bin´arn´ı aplikace je snadn´e. Staˇc´ı naˇc´ıst pˇr´ısluˇsn´ y projekt do v´ yvojov´eho prostˇred´ı Xcode a v menu zvolit Product – Build. 39

Z´ avˇ er Tato pr´ace pˇredstavuje problematiku z´ısk´av´an´ı a testov´an´ı posloupnost´ı n´ahodn´ ych ˇc´ısel. Jsou navrˇzena vylepˇsen´ı st´avaj´ıc´ı metody middle square a je tak´e navrˇzena nov´a metoda z´ısk´av´an´ı n´ahodn´ ych ˇc´ısel sledov´an´ım fyzik´aln´ıho jevu difuze. V pr´aci jsou pops´any dvˇe metody testov´an´ı n´ahodnosti ˇc´ıseln´ ych posloupnost´ı. Prvn´ı metoda je standardn´ı statistick´ y test, druh´a je novˇe navrˇzen´ y test pro testov´an´ı n´ahodnosti pomoc´ı aproximace hodnoty π. Posloupnosti, generovan´e pomoc´ı metod uveden´ ych v t´eto pr´aci, jsou pomoc´ı tˇechto test˚ u zhodnoceny a jsou tak´e uvedeny doporuˇcen´ı pro zlepˇsen´ı v´ ysledk˚ u. Vˇsechny metody jsou implementov´any v programovac´ım jazyku C a byla tak´e vytvoˇrena aplikace Vengeance pro testov´an´ı posloupnost´ı n´ahodn´ ych ˇc´ısel. Dalˇs´ı rozˇs´ıˇren´ı pr´ace by se mohlo zamˇeˇrit na popis dalˇs´ıch metod pro generov´an´ı n´ahodn´ ych ˇc´ısel a tak´e na pˇrid´an´ı dalˇs´ıch test˚ u do aplikace Vengeance.

40

Conclusions This thesis introduces problematics of obtaining and testing of random numbers sequences. There are proposals for improvements of existing method middle square and there is also design of new method for obtaining random numbers by observing a physical phenomena called diffusion. Two methods for testing randomness of number sequences are described. First method is standard statistical test, second is newly designed test for randomness by approximation of π. Sequences generated by methods described in this thesis is tested with those tests and some recommendation for improvements are given. At last, all methods are implemented in C programming language and application Vengeance for testing of random numbers sequences was created. Future enhancements could be focused mainly on describing more methods for generating random numbers and adding some more tests to Vengeance.

41

Reference [1] Knuth, Donald E. The Art of Computer Programming, Volume 2: Seminumerical Algorithms. Addison-Wesley, third edition, 1998. [2] Kapadia, Apu; Lu, Charng-da Random Numbers Generator. http://www.cs.indiana.edu/ kapadia/project2/project2.html, Elektronick´a publikace. 2001 (citov´ano 1.2.2013). [3] Thau, Robert S. Alan Turing’s Manual for the Ferranti Mk. I. http://www.computer50.org/kgill/mark1/RobertTau/turing.html, Elektronick´a publikace. 2000 (citov´ano 1.2.2013). [4] Marsaglia, George Random Numbers Fall Mainly in the Planes. In Proc National Academy of Sciences 61 (1). 1968. s. 25–28. [5] Mende, Robert G.; Noll, Landon C. How Lavarand Works. http://web.archive.org/web/19980521144845/ http://lavarand.sgi.com/cgi-bin/how.cgi, Elektronick´a 1998 (citov´ano 17.3.2013).

publikace.

[6] Weisstein, Eric W. Buffon’s Needle Problem. http://mathworld.wolfram.com/BuffonsNeedleProblem.html, Elektronick´a publikace. 2013 (citov´ano 2.4.2013). [7] Weisstein, Eric W. Chi-Squared Distribution. http://mathworld.wolfram.com/Chi-SquaredDistribution.html, Elektronick´a publikace. 2013 (citov´ano 11.4.2013). [8] Ziegler, G¨ unther M. Matematika v´am to spoˇc´ıt´ a: Pˇr´ıbˇehy kr´alovny vˇed. Kniˇzn´ı klub, Vyd´an´ı 1., Praha 2011. [9] Weisstein, Eric W. Benford’s Law. http://mathworld.wolfram.com/BenfordsLaw.html, Elektronick´a publikace. 2013 (citov´ano 30.4.2013).

42

A.

Obsah pˇ riloˇ zen´ eho CD

V samotn´em z´avˇeru pr´ace je uveden struˇcn´ y popis obsahu pˇriloˇzen´eho CD, tj. z´avazn´e adres´aˇrov´e struktury, d˚ uleˇzit´ ych soubor˚ u apod. bin/ Spustiteln´ y program Vengeance ve form´atu Disk Image, kter´ y je bˇeˇznˇe pouˇz´ıvan´ y na platformˇe OS X k distribuci aplikac´ı. doc/ Dokumentace pr´ace ve form´atu PDF, vytvoˇren´a dle z´avazn´eho stylu KI PˇrF pro diplomov´e pr´ace, vˇcetnˇe vˇsech pˇr´ıloh, a vˇsechny soubory nutn´e pro bezprobl´emov´e vygenerov´an´ı PDF souboru dokumentace (v ZIP archivu), tj. zdrojov´ y text dokumentace, vloˇzen´e obr´azky, apod. src/ Kompletn´ı zdrojov´e texty programu Vengeance se vˇsemi potˇrebn´ ymi zdrojov´ ymi texty, knihovnami a dalˇs´ımi soubory pro bezprobl´emov´e vytvoˇren´ı spustiteln´ ych verz´ı programu. readme.txt Instrukce pro instalaci a spuˇstˇen´ı programu Vengeance, vˇcetnˇe poˇzadavk˚ u pro jeho provoz. Nav´ıc CD obsahuje: data/ Uk´azkov´a a testovac´ı data pouˇzit´a v pr´aci a pro potˇreby obhajoby pr´ace.

43