Mersennen pyörre

Mersenne twister ( MT) on näennäissatunnaislukugeneraattori ( PRNG), jonka kehittivät vuonna 1997 japanilaiset tiedemiehet Makoto Matsumoto ( Jap.松本眞) ja Takuji Nishimura ( Jap.西村拓士). Mersennen pyörre perustuu Mersennen alkulukujen ominaisuuksiin (tästä nimi) ja tuottaa nopeasti korkealaatuisia pseudosatunnaislukuja satunnaisuuden kannalta.

Mersennen pyörteellä ei ole monia muille PRNG:ille luontaisia puutteita, kuten lyhyt ajanjakso, ennustettavuus ja helposti havaittavissa olevat tilastolliset kuviot.

Tämä generaattori ei kuitenkaan ole kryptografisesti turvallinen , mikä rajoittaa sen käyttöä kryptografiassa .

Algoritmista on ainakin kaksi yleistä muunnelmaa , jotka eroavat vain käytetyn Mersennen alkuluvun koosta , joista yleisin on MT19937- algoritmi , jonka jakso on 2 19937 − 1 (noin 4,3×10 6001 ).

Ominaisuudet

Mersennen pyörre on kierretty yleinen palautesiirtorekisteri ( TGFSR) [ 1] . "Whirlwind" on muunnos, joka varmistaa , että luodut näennäissatunnaiset luvut jakautuvat tasaisesti 623 ulottuvuuteen ( lineaarisissa kongruenssigeneraattoreissa se on rajoitettu viiteen ulottuvuuteen). Siksi kahden näytesekvenssin välinen korrelaatiofunktio Mersennen pyörteen lähtösekvenssissä on mitätön.

Mersennen pyörteen generoimalla näennäissatunnaisella sekvenssillä on hyvin suuri Mersennen lukua vastaava jakso, mikä on enemmän kuin riittävä moniin käytännön sovelluksiin.

On olemassa tehokkaita Mersenne Twist -toteutuksia, jotka ovat nopeampia kuin monet tavalliset PRNG:t (erityisesti 2–3 kertaa nopeampia kuin lineaariset kongruenssigeneraattorit). Mersennen vortex-algoritmi on toteutettu Boost [2] , Glib [3] ohjelmistokirjastossa ja standardikirjastoissa C++ , Python [4] [5] [6] , Ruby [7] , R [8] , PHP [9] , MATLAB [ 10] , Autoit [11] .

Mersennen pyörteen tuottamat pseudosatunnaislukusekvenssit läpäisevät DIEHARD-tilastotestit , mikä vahvistaa niiden hyvät tilastolliset ominaisuudet.

Generaattoria ei ole suunniteltu luomaan kryptografisesti vahvoja satunnaisia numerosarjoja . Salauksen vahvuuden varmistamiseksi generaattorin tulossekvenssi on käsiteltävä jollakin kryptografisista hajautusalgoritmeista [12] .

K -jakelu

Monia mahdollisesti "korkealaatuisia" generaattoreita on ehdotettu, mutta vain muutamaa voidaan käyttää vakavaan mallintamiseen, koska näennäissatunnaisten lukugeneraattoreiden "satunnaisuus" ei ole selkeä käsite, koska jokainen tutkija keskittyy tiettyihin satunnaisuuden parametreihin. . Monista tunnetuista mittareista vahvimpana pidetään korkeampaan tasajakaumaan perustuvia testejä, kuten alla kuvattu spektritesti ja k-jakaumatesti.

Määritelmä

Jakson P näennäissatunnaisella sekvenssillä x i , joka koostuu w -bittisistä kokonaisluvuista, sanotaan olevan k -jakauma v -bitin tarkkuudella, jos se täyttää seuraavan ehdon: Olkoon trunc v (x) ensimmäisen v :n muodostama luku sekvenssin x i bittiä , harkitse muotoa [13] olevia P vektoreita, joiden pituus on kv bittiä. Tällöin kukin 2 kv :n mahdollisista bittiyhdistelmistä esiintyy yhtä monta kertaa, lukuun ottamatta kokonaan nollien yhdistelmää, joka esiintyy yhden kerran vähemmän.
$({\text{trunc}}_{v}(x_{i}),\,{\text{trunc}}_{v}(x_{{i+1}}),\,...,\ ,{\text{trunc}}_{v}(x_{{i+k-1))))\quad (0\leq i<P)$

Geometrinen tulkinta

Kunkin v = 1, 2,., w , olkoon k(v) suurin luku siten, että sekvenssi on k - jakautunut v -bitin tarkkuudella. Jaa jokainen kokonaisluku x i 2 w :llä normalisoidaksesi näennäissatunnaiseksi reaaliluvuksi x i väliltä [0, 1]. Laitetaan P pistettä k -ulotteiseen kuutioon, jonka koordinaatit ( x i , x i+1 …, x i+k-1 )(i = 0, 1,…, P-1) koko jaksolle. Annetun k -ulotteisen kuution kukin akseli on jaettu 2 v :n väliin. Näin ollen olemme jakaneet kuution 2 kv :n pieniksi kuutioiksi. Jakso on k - jakautunut v -bitin tarkkuudella, jos jokaisessa pienessä kuutiossa on yhtä monta pisteitä, paitsi origon kuutiossa, jossa on yksi piste vähemmän. Siksi mitä suurempi k(v) jokaiselle v :lle, sitä monimuuttujaisempi jakauma on v - bitin tarkkuudella. Testaamalla k - jakaumaa tarkoitamme k(v) arvojen saamista .

Kuvaus

x merkitsee w -ulotteisia vektoreita kentän = {0,1} $F_{{2}}$ yli, jotka vastaavat konesanoja , joiden koko on w . Mersennen pyörre generoi sekvenssin vektoreita, jotka ovat näennäissatunnaisia kokonaislukuja välillä 0 - 2 w - 1. Jakamalla luvulla 2 w - 1, saat myös näennäissatunnaisen reaaliluvun alueelta [0,1] .

Algoritmi perustuu seuraavaan toistuvaan kaavaan :

x_{k+n}:=x_{k+m}\oplus ({x_{k))^{u}\mid {x_{k+1))^{l})A,\qquad k =0,1,\ldots \qquad(1)

missä:

n on kokonaisluku, joka ilmaisee toistumisjärjestyksen,
m - kokonaisluku, 1 ≤ m < n ,
A on matriisi, jonka koko on w×w ja jonka elementit ovat peräisin , $F_{{2}}$
$\mid$ - bittikohtainen TAI (OR),
$\oplus$ - Modulo two -lisäys (XOR).

Oikealla puolella x k u tarkoittaa "korkeampaa wr - bittiä" x k ja x k+1 l "alempaa r - bittiä" x k+1 . Vektori ( x k u | x k+1 l ) on x k :n korkeiden wr - bittien ja xk+1 : n alhaisten r - bittien ketjutus . Otetaan ( x 0 , x 1 ,…, x n-1 ) alkutäytöksi. Sitten generaattori laskee x n :n rekursiivisella lausekkeella kohdassa k = 0. Olettaen , että k = 1,2, …, generaattori laskee x n+1 , x n+2 ,… Matriisin A muoto valitaan kertolaskunopeus A :lla:

A={\begin{pmatrix}0&1&&&&\\0&0&1&&&\\0&\cdots &\cdots &\ddots &&\\&&&&\ddots &\\&&&&1\\a_{{w-1}}&a_{{w-2} }&\cdots &\cdots &\cdots &a_{{0}}\end{pmatrix}}

Ja x A : n laskenta vähennetään bittikohtaisiin operaatioihin:

{\boldsymbol {x}}A={\begin{cases}{\boldsymbol {x}}\gg 1&x_{0}=0\\({\boldsymbol {x}}\gg 1)\oplus {\boldsymbol { a}}&x_{0}=1\end{cases}}

missä

{\boldsymbol {x}}:=({x_{k}}^{u}\mid {x_{{k+1}}}^{l})\qquad \qquad k=0,1,\ldots

{\boldsymbol {a}}:=({a_{{w-1}}},{a_{{w-2}}},\ldots ,{a_{{0}}})

{\boldsymbol {x}}:=({x_{{w-1}}},{x_{{w-2}}},\ldots ,{x_{{0}}})

Epätäydelliset taulukot

MT-sekvenssi ( xk +n , xk +n-1 ,…, xk+ 1u ) muodostaa (n × w — r) -taulukon. Koska r bittiä hylätään, taulukkoa kutsutaan epätäydelliseksi taulukoksi [13] . Jokainen elementti saadaan toistuvuusrelaatiosta (1). Tilanmuutos MT tapahtuu myös lineaarisen suhteen mukaan ja määritetään lineaarimuunnoksen B avulla .

Lineaaristen toistuvien sekvenssien yleisen teorian mukaan jokainen arvo ( n × w − r )-taulukossa on lineaarinen toistuva sekvenssi , joka vastaa muunnoksen B ominaispolynomia φ B ( t ) . Matriisilla B on mitat ( n × w - r ) × ( n × w - r ) ja sen muoto on seuraava:

$B={\begin{pmatrix}0&I_{{w}}&\cdots &0&0\\\vdots &&&&\\I_{{w}}&\vdots &\ddots &\vdots &\vdots \\\vdots &&&&\\ 0&0&\cdots &I_{{w}}&0\\0&0&\cdots &0&I_{{wr}}\\S&0&\cdots &0&0\end{pmatrix}}{\begin{matrix}\\\\\leftarrow m{\hbox{ -rivi}}\\\\\\\\\end{matriisi}}$

$S={\begin{pmatrix}0&I_{{r}}\\I_{{wr}}&0\end{pmatrix}}A$

Missä on r × r - identiteettimatriisi . $minä_{{r}}$

Sillä suoritetaan . Muunnoksen B ominaispolynomi φ B ( t ) on muotoa [13] : $l=0,1,\lpistettä$ $(x_{{l+n}},x_{{l+n-1}},\ldots ,x_{{l+1}}):=(x_{{l+n-1}},x_{{ l+n-2}},\ldots ,x_{{l}})B$

$\Phi _{B}(t)=(t^{n}+t^{m})^{wr}\cdot (t^{n-1}+t^{m-1})^ {r}+a_{0}(t^{n}+t^{m})^{wr}\cdot (t^{n-1}+t^{m-1})^{r-1} +...+a_{r-2}(t^{n}+t^{m})^{wr}\cdot (t^{n-1}+t^{m-1})+a_{ r-1}(t^{n}+t^{m})^{wr}+a_{r}(t^{n}+t^{m})^{wr-1}+...+ a_{w-2}(t^{n}+t^{m})+a_{w-1}$

Sekvenssi saavuttaa maksimijakson 2 ( nw-r ) −1 jos ja vain jos φ B ( t ) -primitiivi [13] .

Karkaisu

Rekursion (1) generoimilla raakasekvensseillä on huono tasainen jakautuminen suurille ulottuvuuksille. Tämän korjaamiseksi käytetään temperointimenetelmää [ 13 ] , jonka tulos on lopullinen näennäissatunnainen sekvenssi. Menetelmä on, että jokainen generoitu sana kerrotaan oikealla erityisellä käännettävällä matriisilla T , jonka koko on w × w . Matriisille T : x → z = x T valitaan seuraavat peräkkäiset muunnokset:

y := x ⊕ ( x >> u ) y := : y ⊕ ( ( y << s ) & b ) y := : y ⊕ ( ( y << t ) & c ) z := y ⊕ ( y >> l )

missä l , s , t ja u ovat kokonaislukuja ja b ja c ovat erityisesti valittuja sananpituisia bitimaskeja ja ( x ≫u) tarkoittaa bittikohtaista siirtoa oikealle u bitillä.

Algoritmi

Mersennen pyörre on algoritmisesti toteutettu kahdella pääosalla: rekursiivisella ja karkaisulla . Rekursiivinen osa on lineaarinen takaisinkytkentäsiirtorekisteri , jossa sen sanan kaikki bitit määritetään rekursiivisesti; lähtöbittivirta määräytyy myös rekursiivisesti tilabittifunktiolla.

Siirtorekisteri koostuu 624 merkinnästä, yhteensä 19937 solua. Jokainen elementti on 32 bittiä pitkä paitsi ensimmäinen elementti, jossa on vain 1 bitti bitin hylkäämisen vuoksi.

Luontiprosessi alkaa loogisella kertomisella bittimaskilla, hylkäämällä 31 bittiä (paitsi merkittävimmät).

Seuraava vaihe on alustaa ( x 0 , x 1 ,…, x 623 ) millä tahansa etumerkittömällä 32-bittisellä kokonaisluvulla. Seuraavat vaiheet sisältävät tilojen yhdistämisen ja siirtymisen.

Tilaavaruudessa on 19937 bittiä (624 32 - 31). Seuraava tila luodaan siirtämällä yksi sana pystysuunnassa ylöspäin ja lisäämällä uusi sana loppuun. Uusi sana lasketaan skaalaamalla keskiosa poissuljetulla [14] . Tulostussarja alkaa x 624 , x 625 ,…

Algoritmi tuotetaan kuudessa vaiheessa:

Vaihe 0. Vakioiden u1 , h1 , a u1 ← 10…0 bitin maski korkeiden wr - bittien, h1 ← 01…1 bitin maski alhaisen r bittien, a ← a w-1 a w-2 …a 0 arvo on matriisin A viimeinen rivi. _
Vaihe 1. x [0], x [1],…, x [n-1] ← alkutäyttö
Vaihe 2. Laskenta ( x i u | x i+1 l ) y ← ( x [i] JA u1 ) TAI ( x [(i + 1) mod n] JA h 1)
Vaihe 3. Laske sekvenssin seuraavan elementin arvo rekursiivinen lauseke (1) x [i] ← x [(i + m) mod n] XOR ( y >>1) XOR a jos pieni bitti y = 1
Tai x [i] ← x [(i + m) mod n] XOR ( y >>1) XOR 0, jos y :n vähiten merkitsevä bitti= 0 Vaihe 4. Laske x [i] T y ← x [i] y ← y XOR ( y >> u ) y ← y XOR ( ( y << s ) JA b ) y ← y XOR ( ( y << t ) JA c ) z ← y XOR ( y >> l ) lähtö z Vaihe 5. i ← (i + 1) mod n
Vaihe 6. Siirry vaiheeseen 2.

32-bittisen MT-generaattorin parametrit

MT-parametrit on valittu huolellisesti edellä mainittujen ominaisuuksien saavuttamiseksi. Parametrit n ja r valitaan siten, että ominaispolynomi on primitiivinen tai nw - r on yhtä suuri kuin Mersennen luku 19937. Huomaa, että w :n arvo vastaa tietokoneen sanan kokoa. Tässä tapauksessa se on 32 bittiä. Kun arvot n , m , r ja w ovat kiinteitä, matriisin A viimeisen rivin arvo valitaan sattumanvaraisesti. Mersennen luvuille kokonaislukujen primaalisuustesti on paljon helpompi. Näin ollen tunnetaan monia Mersennen alkulukuja (eli alkulukuja muotoa 2 p −1) aina p=43112609 asti [1] . Karkaisuparametrit valitaan niin , että saadaan hyvä tasainen jakautuminen . Kaikki MT-parametrit on esitetty taulukossa 1.

pöytä 1

n	624
w	32
r	31
m	397
a	9908B0DF16 _
u	yksitoista
s	7
t	viisitoista
l	kahdeksantoista
b	9D2C5680 16
c	EFC60000 16

Muut toteutukset

Tekniikan muutosten, erityisesti prosessorin suorituskyvyn kasvun vuoksi, MT:stä keksittiin 64- ja 128-bittiset versiot. 64-bittistä versiota ehdotti Takuji Nishimura vuonna 2000, [15] 128-bittistä versiota vuonna 2006 [16] [17] myös Takuji Nishimura. Molemmilla versioilla on sama aikajakso kuin alkuperäisellä MT:llä.

64-bittisestä MT:stä on kaksi versiota. Ensimmäinen versio käyttää samaa rekursiivista suhdetta, toiseen versioon lisättiin kaksi vektoria, mikä lisäsi ominaispolynomin termien määrää:

x_{{k+n}}:=x_{{k+m2}}\oplus x_{{k+m1}}\oplus x_{{k+m0}}\oplus ({x_{k}}^{u }\mid {x_{{k+1}}}^{l})A\qquad (2)

32-bittiseen MT:hen verrattuna 64-bittinen versio on nopeampi. Kaikki 64-bittisen version parametrit on esitetty taulukossa 2.

taulukko 2

ID	Rekursiiviselle suhteelle (1)		Rekursiiviselle suhteelle (2)
n	312	312	312	312	312
w	64	64	64	64	64
r	31	31	31	31	31
m	156	156
m0_ _			63	63	63
m 1			151	151	151
m2 _			224	224	224
a	B5026F5AA96619E9 16	F6A3F020F058B7A7 16	B3815B624FC82E2F 16	8EBD4AD46CB39A1E 16	CACB98F78EBCD4ED 16
b	D66B5EF5B4DA0000 16	28AAF6CDDBB40000 16	599CFCBFCA660000 16	656BEDFFD9A40000 16	A51DBEFFDA6C0000 16
c	FDED6BE000000000 16	FDEDEAE000000000 16	FFFAAFFE00000000 16	FDFECE7E00000000 16	FFEE9BF600000000 16
u	29	29	26	26	26
s	17	17	17	17	17
t	37	37	33	33	33
l	41	41	39	39	39

Muistiinpanot

↑ Twisted GFSR generaattorit, 1992 .
↑ boost/random/mersenne_twister.hpp . Tehosta C++-kirjastoja . Haettu 29. toukokuuta 2012. Arkistoitu alkuperäisestä 19. marraskuuta 2012. (määrätön)
↑ Muutoksia GLibiin . GLib-viiteopas . Haettu 29. toukokuuta 2012. Arkistoitu alkuperäisestä 19. marraskuuta 2012. (määrätön)
↑ 9.6 satunnainen - Luo pseudosatunnaislukuja . Python v2.6.8 -dokumentaatio . Haettu 29. toukokuuta 2012. Arkistoitu alkuperäisestä 19. marraskuuta 2012. (määrätön)
↑ 8.6 satunnainen - Luo näennäissatunnaisia lukuja . Python v3.2 -dokumentaatio . Haettu 29. toukokuuta 2012. Arkistoitu alkuperäisestä 19. marraskuuta 2012. (määrätön)
↑ satunnainen - Luo pseudosatunnaislukuja - Python 3.8.3 -dokumentaatio . Python 3.8.3 -dokumentaatio . Haettu 23. kesäkuuta 2020. Arkistoitu alkuperäisestä 28. heinäkuuta 2021. (määrätön)
↑ "Satunnainen" luokan dokumentaatio . Ruby 1.9.3 - dokumentaatio . Haettu 29. toukokuuta 2012. Arkistoitu alkuperäisestä 26. kesäkuuta 2021. (määrätön)
↑ Satunnaislukugeneraattorit . CRAN-tehtävänäkymä: Todennäköisyysjakaumat . Haettu 29. toukokuuta 2012. Arkistoitu alkuperäisestä 19. marraskuuta 2012. (määrätön)
↑ mt_srand . php dokumentaatio . Haettu 29. toukokuuta 2012. Arkistoitu alkuperäisestä 19. marraskuuta 2012. (määrätön)
↑ Ohjaa satunnaislukujen generointia (RNG) . Matlabin dokumentaatio . Haettu 23. marraskuuta 2015. Arkistoitu alkuperäisestä 12. syyskuuta 2010. (määrätön)
↑ Toiminto Satunnainen . Haettu 22. maaliskuuta 2014. Arkistoitu alkuperäisestä 6. huhtikuuta 2021. (määrätön)
↑ CryptMT Stream Cipher .
↑ 1 2 3 4 5 Matsumoto, Nishimura, 2017 .
↑ Kryptografinen Mersenne Twister ja Fubuki Stream/Block Cipher, 2005 .
↑ Nishimura, 2000 .
↑ SIMD-suuntautunut Fast Mersenne Twister (SFMT) . Haettu 15. marraskuuta 2012. Arkistoitu alkuperäisestä 9. marraskuuta 2020. (määrätön)
↑ SFMT: Nopeuden vertailu . Haettu 15. marraskuuta 2012. Arkistoitu alkuperäisestä 8. tammikuuta 2020. (määrätön)

Kirjallisuus

M. Matsumoto, T. Nishimura. Mersenne twister: 623-ulotteisesti tasajakoinen yhtenäinen näennäissatunnaislukugeneraattori // ACM Trans. mallintamisesta ja tietokonesimulaatioista: Journal. - 1998. - Voi. 8 , ei. 1 . - s. 3-30 . doi : 10.1145 / 272991.272995 .
Matsumoto, M.; Kurita, Y. Kierretyt GFSR-generaattorit (määrittämätön) // ACM Trans. mallintamisesta ja tietokonesimulaatioista. - 1992. - V. 2 , nro 3 . - S. 179-194 . - doi : 10.1145/146382.146383 .
Matsumoto, Makoto; Nishimura, Takuji; Hagita, Mariko; Saito, Mutsuo. Cryptographic Mersenne Twister ja Fubuki Stream/Block Cipher (englanniksi) : päiväkirja. – 2005.
T. Nishimura. 64-bittisten Mersennen twistereiden taulukot (määrittämätön) // ACM Trans. mallintamisesta ja tietokonesimulaatioista. - 2000. - T. 10 , nro 4 . - S. 248-357 . - doi : 10.1145/369534.369540 .
Matsumoto M., Saito M., Nishimura T., Hagita M. CryptMT Stream Cipher Ver. 3. eSTREAM-projekti (uuspr.) .

Linkit

Makoto Matsumoto, MT:n akateemiset julkaisut
Mersenne Twisterin kotisivu C- koodilla
Kuuba - kirjasto moniulotteiseen numeeriseen integrointiin
Mersenne Twister