Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
12
1020Generatoryfizyczne
Algorytm1.1.AlgorytmkwadratowyvonNeumanna
1.WeźwylosowanąwcześniejliczbęlosowąXn11.
2.ObliczYn=X2
n11.
3.Jeślitopotrzebne,dopiszodpowiedniąliczbęzernapoczątkuYn,tak,
abyotrzymaćliczbę2m-cyfrową.
4.ZaXnprzyjmijmśrodkowychcyfrzmodyfikowanejliczbyYn.
Rozwiązanie:OtrzymujemyY1=0144,X1=14,Y2=0196,X2=19,
Y3=0361,X3=36,Y4=1296,X4=29,...
⋄
Innymisłowy,ogólniealgorytmvonNeumannamożnazapisaćwpostaci
Xn=f(Xn11),
(1.1)
gdzief(.)jestpewnąściśleokreślonąfunkcjąmatematyczną.Jakłatwoza-
uważyć,niezbędnejestzainicjalizowanietakiegoalgorytmupewną,wybraną
nręcznie”lubwylosowanąwinnysposób,wartościąXo.Wartośćta,nazy-
wanaziarnemlubwartościąinicjalizującączyteżwartościąstartową
(awj.ang.określanajakoseed),musizostaćwcześniejustalona.
Należypamiętaćopewnychograniczeniachalgorytmówokreślonychwzo-
rem(1.1).Jestnimzjawiskookresowości.Otóżdlawygenerowanegociągu
Xo,X1,X2,...,Xm,Xm+1,...,Xm+p,Xm+p+1,...
(1.2)
zawszeistniejątakieliczbymip,żeXi=Xi+jpdlaź>mij=1,2,...
Zatemcopewienczaswszystkieliczbypowtarzająsięwdokładnietakim
samymukładziezłożonymzpelementów.Woczywistysposóbprzykon-
strukcjigeneratorastaramysię,abyp,zwaneokresemciągu,byłojak
największe.Zawpełnilosowemożemybowiemuważaćtylkoliczbyzciągu
Xo,X1,...,Xm+p,zwanegookresemaperiodycznościciągu.Zazwyczaj
przytymzoczywistychpowodówwartośćinicjalizującąXoodrzucasięzwy-
generowanejpróby.
1.2.
Generatoryfizyczne
Takzwanegeneratoryfizyczne(TRNG–TrueRandomNumberGenera-
tors)sąurządzeniami,któregenerująliczbylosowe,wykorzystujączjawiska