Vortexul Mersenne

Sucitorul Mersenne ( MT ) este un generator de numere pseudo-aleatoare (PRNG) dezvoltat în 1997 de oamenii de știință japonezi Makoto Matsumoto ( Jap. 松本眞) și Takuji Nishimura ( Jap. 西村拓士). Vortexul Mersenne se bazează pe proprietățile primelor Mersenne (de unde și numele) și oferă o generare rapidă de numere pseudoaleatoare de înaltă calitate în ceea ce privește aleatoriu.

Vortexul Mersenne este lipsit de multe dintre deficiențele inerente altor PRNG-uri, cum ar fi o perioadă scurtă, predictibilitate și modele statistice ușor de detectat.

Cu toate acestea, acest generator nu este sigur din punct de vedere criptografic , ceea ce limitează utilizarea sa în criptografie .

Există cel puțin două variante generale ale algoritmului , care diferă doar prin dimensiunea primului Mersenne utilizat , dintre care cel mai comun este algoritmul MT19937 , care are o perioadă de 2 19937 − 1 (aproximativ 4,3×10 6001 ).

Proprietăți

Vortexul Mersenne este un registru de deplasare cu feedback generalizat răsucit ( TGFSR) [ 1] . „Vârtejul” este o transformare care asigură că numerele pseudoaleatoare generate sunt distribuite uniform în 623 de dimensiuni (pentru generatoarele congruențiale liniare este limitată la 5 dimensiuni). Prin urmare, funcția de corelație între două secvențe de eșantioane din secvența de ieșire a unui vortex Mersenne este neglijabilă.

Secvența pseudo-aleatorie generată de vortexul Mersenne are o perioadă foarte mare egală cu numărul Mersenne, care este mai mult decât suficientă pentru multe aplicații practice.

Există implementări eficiente ale Mersenne Twist care sunt mai rapide decât multe PRNG-uri standard (în special, de 2-3 ori mai rapide decât generatoarele congruențiale liniare). Algoritmul vortex Mersenne este implementat în biblioteca software Boost [2] , Glib [3] și bibliotecile standard pentru C++ , Python [4] [5] [6] , Ruby [7] , R [8] , PHP [9] , MATLAB [ 10] , Autoit [11] .

Secvențele de numere pseudoaleatoare produse de vortexul Mersenne trec cu succes testele statistice DIEHARD , ceea ce le confirmă proprietățile statistice bune.

Generatorul nu este proiectat pentru a genera secvențe aleatoare de numere criptografic puternice . Pentru a asigura puterea criptografică, secvența de ieșire a generatorului trebuie procesată de unul dintre algoritmii de hashing criptografic [12] .

K -distribuție

Au fost propuși mulți generatori de „înaltă calitate”, dar doar câțiva pot fi utilizați pentru modelare serioasă din cauza lipsei unui concept clar de „aleatorie” pentru generatorii de numere pseudoaleatoare, deoarece fiecare cercetător se concentrează pe parametrii specifici ai aleatoriei. . Dintre multele măsuri binecunoscute, testele bazate pe o distribuție uniformă mai mare, cum ar fi testul spectral și testul de distribuție k descrise mai jos, sunt considerate cele mai puternice.

Definiție

Se spune că o secvență pseudoaleatoare x i a perioadei P , constând din numere întregi de w -biți, are o distribuție k cu precizie de v -biți dacă îndeplinește următoarea condiție:
Fie trunc v (x) numărul format de primul v biți ai șirului x i , se consideră P vectori de forma [13] , de lungime kv biți. Apoi, fiecare dintre cele 2 kv combinații posibile de biți apare de un număr egal de ori, cu excepția unei combinații constând în întregime din zerouri, care apare o dată mai puțin. $({\text{trunc}}_{v}(x_{i}),\,{\text{trunc}}_{v}(x_{{i+1}}),\,...,\ ,{\text{trunc}}_{v}(x_{{i+k-1))))\quad (0\leq i<P)$

Interpretare geometrică

Pentru fiecare v = 1, 2,., w , fie k(v) numărul maxim astfel încât secvența să fie k- distribuită cu precizie v -bit. Împărțiți fiecare număr întreg x i la 2 w pentru a se normaliza într-un număr real pseudoaleator x i din intervalul [0, 1]. Să plasăm P puncte în cubul k -dimensional cu coordonatele ( x i , x i+1 …, x i+k-1 )(i = 0, 1,…, P-1) pentru întreaga perioadă. Fiecare dintre axele cubului k - dimensional dat este împărțită în 2 v intervale. Astfel, am împărțit cubul în cuburi mici de 2 kv . O secvență este k- distribuită cu precizie v - bit dacă fiecare cub mic conține un număr egal de puncte, cu excepția cubului de la origine, care conține un punct mai puțin. Prin urmare, cu cât k(v) este mai mare pentru fiecare v , cu atât distribuția va fi mai multivariată cu precizie de v -biți. Testând distribuția k , vom însemna obținerea valorilor lui k(v) .

Descriere

x va desemna vectorii w -dimensionali peste câmpul = {0,1} $F_{{2}}$ corespunzător cuvintelor mașină de dimensiunea w . Vortexul Mersenne generează o secvență de vectori care sunt numere întregi pseudoaleatoare din intervalul 0 la 2 w - 1. Prin împărțirea la 2 w - 1, puteți obține și un număr real pseudo-aleatoriu din intervalul [0,1] .

Algoritmul se bazează pe următoarea formulă recurentă :

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

Unde:

n este un număr întreg care denotă ordinea recurenței,
m - întreg, 1 ≤ m < n ,
A este o matrice de dimensiune w×w , cu elemente din , $F_{{2}}$
$\mid$ - SAU pe biți (SAU),
$\oplus$ - adunare modulo doi (XOR).

În partea dreaptă, x k u indică „ biții wr mai mari” x k și x k+1 l „ biții r inferiori ” x k+1 . Vectorul ( x k u | x k+1 l ) este concatenarea biților wr mari ai x k și biților r inferiori ai x k+1 . Să luăm ( x 0 , x 1 ,…, x n-1 ) ca umplere inițială. Atunci generatorul va calcula x n prin expresia recursivă la k = 0. Presupunând k = 1,2, …, generatorul va calcula x n+1 , x n+2 ,… Forma matricei A este aleasă pe baza viteza inmultirii cu A :

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}}

Și calculul lui x A se reduce la operații pe bit:

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

Unde

{\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}}})

Matrice incomplete

Secvența MT ( x k+n , x k+n-1 ,…, x k+1 u ) formează o matrice (n × w — r) . Deoarece r biți sunt eliminați, matricea este numită matrice incompletă [13] . Fiecare element se obține din relația de recurență (1). Schimbarea stării MT are loc și după o relație liniară și se determină folosind o transformare liniară B .

Conform teoriei generale a secvențelor liniare recurente, fiecare valoare dintr-o matrice ( n × w − r ) este o secvență liniară recurentă corespunzătoare polinomului caracteristic φ B ( t ) al transformării B . Matricea B are dimensiuni ( n × w − r ) × ( n × w − r ) și are următoarea formă:

$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{ --lea rând}}\\\\\\\\\end{matrice}}$

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

Unde este o matrice de identitate r × r . $eu_{{r}}$

Căci se realizează . Polinomul caracteristic φ B ( t ) al transformării B are forma [13] : $l=0,1,\ldots$ $(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}$

Secvența atinge perioada maximă 2 ( nw-r ) −1 dacă și numai dacă φ B ( t ) -primitive [13] .

temperare

Secvențele brute generate de recursivitate (1) au o distribuție uniformă slabă pe dimensiuni mari. Pentru a remedia acest lucru, este utilizată metoda de temperare [ 13 ] , a cărei ieșire este secvența finală pseudo-aleatorie. Metoda este ca fiecare cuvânt generat să fie înmulțit în dreapta cu o matrice specială inversabilă T de dimensiunea w × w . Pentru matricea T : x → z = x T , se aleg următoarele transformări secvențiale:

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

unde l , s , t și u sunt numere întregi, iar b și c sunt măști de biți cu lungimea unui cuvânt alese special și ( x ≫u) denotă o operație de deplasare la dreapta pe biți cu u biți.

Algoritm

Vortexul Mersenne este implementat algoritmic prin două părți principale: recursiv și întărire . Partea recursivă este un registru de deplasare cu feedback liniar , în care toți biții din cuvântul său sunt definiți recursiv; fluxul de biți de ieșire este de asemenea determinat recursiv de funcția de biți de stare.

Registrul de schimb este format din 624 de intrări, pentru un total de 19937 de celule. Fiecare element are o lungime de 32 de biți, cu excepția primului element, care are doar 1 bit din cauza unei retrageri de biți.

Procesul de generare începe cu o înmulțire logică cu o mască de biți, eliminând 31 de biți (cu excepția celor mai semnificativi).

Următorul pas este să inițializați ( x 0 , x 1 ,…, x 623 ) cu orice numere întregi pe 32 de biți fără semn. Următorii pași includ combinarea și starea de tranziție.

Spațiul de stare are 19937 biți (624 32 - 31). Următoarea stare este generată prin deplasarea unui cuvânt vertical în sus și inserarea unui cuvânt nou la sfârșit. Cuvântul nou se calculează prin scalarea părții din mijloc cu cea exclusă [14] . Secvența de ieșire începe de la x 624 , x 625 ,...

Algoritmul este produs în șase etape:

Pasul 0. Valoarea constantelor u1 , h1 , a u1 ← 10…0 masca de biți a biților cu wr mare , h1 ← 01…1 masca de biți a biților r scăzut, a ← a w-1 a w-2 …a 0 este ultimul rând al matricei A. _
Pasul 1. x [0], x [1],…, x [n-1] ← umplutură inițială
Pasul 2. Calcul ( x i u | x i+1 l ) y ← ( x [i] AND u1 ) SAU ( x [(i + 1) mod n] ȘI h 1)
Pasul 3. Calculați valoarea următorului element al secvenței expresie recursivă (1) x [i] ← x [(i + m) mod n] XOR ( y >>1) XOR a dacă bitul mic y = 1
Sau x [i] ← x [(i + m) mod n] XOR ( y >>1) XOR 0 dacă bitul cel mai puțin semnificativ al lui y = 0 Pasul 4. Calculați x [i] T y ← x [i] y ← y XOR ( y >> u ) y ← y XOR (( y << s ) ȘI b ) y ← y XOR (( y << t ) ȘI c ) z ← y XOR ( y >> l ) ieșire z Pasul 5. i ← (i + 1) mod n
Pasul 6. Treceți la pasul 2.

Parametrii generatorului MT pe 32 de biți

Parametrii MT au fost aleși cu atenție pentru a atinge proprietățile menționate mai sus. Parametrii n și r sunt aleși astfel încât polinomul caracteristic să fie primitiv sau nw - r să fie egal cu numărul Mersenne 19937. Rețineți că valoarea lui w este echivalentă cu dimensiunea cuvântului computerului. În acest caz, este de 32 de biți. În timp ce valorile lui n , m , r și w sunt fixe, valoarea ultimului rând al matricei A este aleasă la întâmplare. Pentru numerele Mersenne, testul de primalitate pentru numere întregi este mult mai ușor. Astfel, sunt cunoscute multe numere prime Mersenne (adică prime de forma 2 p −1), până la p=43112609 [1] . Parametrii de temperare sunt selectați astfel încât să putem obține o distribuție uniformă bună . Toți parametrii MT sunt prezentați în Tabelul 1.

tabelul 1

n	624
w	32
r	31
m	397
A	9908B0DF16 _
u	unsprezece
s	7
t	cincisprezece
l	optsprezece
b	9D2C5680 16
c	EFC60000 16

Alte implementări

Datorită schimbărilor de tehnologie, în special, creșterea performanței procesorului, au fost inventate versiunile MT pe 64 și 128 de biți. Versiunea pe 64 de biți a fost propusă de Takuji Nishimura în 2000, [15] versiunea pe 128 de biți în 2006 [16] [17] tot de Takuji Nishimura. Ambele versiuni au aceeași perioadă ca și MT original.

MT pe 64 de biți are două versiuni. Prima versiune folosește aceeași relație recursivă, încă doi vectori au fost adăugați la a doua versiune, ceea ce a crescut numărul de termeni ai polinomului caracteristic:

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)

În comparație cu MT pe 32 de biți, versiunea pe 64 de biți este mai rapidă. Toți parametrii pentru versiunea pe 64 de biți sunt prezentați în Tabelul 2.

masa 2

ID	Pentru relația recursivă (1)		Pentru relația recursivă (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	28AAF6CDBDB40000 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

Note

↑ Twisted GFSR generators, 1992 .
↑ boost/random/mersenne_twister.hpp . Boost C++ biblioteci . Preluat la 29 mai 2012. Arhivat din original la 19 noiembrie 2012. (nedefinit)
↑ Modificări la GLib . Manual de referință GLib . Preluat la 29 mai 2012. Arhivat din original la 19 noiembrie 2012. (nedefinit)
↑ 9.6 aleatoriu - Generați numere pseudoaleatoare . Documentația Python v2.6.8 . Preluat la 29 mai 2012. Arhivat din original la 19 noiembrie 2012. (nedefinit)
↑ 8.6 aleatoriu - Generați numere pseudoaleatoare . Documentația Python v3.2 . Preluat la 29 mai 2012. Arhivat din original la 19 noiembrie 2012. (nedefinit)
↑ aleatoriu - Generați numere pseudoaleatoare - Documentația Python 3.8.3 . Documentația Python 3.8.3 . Preluat la 23 iunie 2020. Arhivat din original la 28 iulie 2021. (nedefinit)
↑ Documentația clasei „aleatorie” . Documentația Ruby 1.9.3 . Preluat la 29 mai 2012. Arhivat din original la 26 iunie 2021. (nedefinit)
↑ Generatoare de numere aleatorii . CRAN Task View: Distribuții de probabilitate . Preluat la 29 mai 2012. Arhivat din original la 19 noiembrie 2012. (nedefinit)
↑ mt_srand . documentație php . Preluat la 29 mai 2012. Arhivat din original la 19 noiembrie 2012. (nedefinit)
↑ Control generarea numerelor aleatoare (RNG) . Documentație Matlab . Consultat la 23 noiembrie 2015. Arhivat din original la 12 septembrie 2010. (nedefinit)
↑ Funcție aleatorie . Preluat la 22 martie 2014. Arhivat din original la 6 aprilie 2021. (nedefinit)
↑ CryptMT Stream Cipher .
↑ 1 2 3 4 5 Matsumoto, Nishimura, 2017 .
↑ Criptografic Mersenne Twister și Fubuki Stream/Block Cipher, 2005 .
↑ Nishimura, 2000 .
↑ Fast Mersenne Twister (SFMT) orientat spre SIMD . Consultat la 15 noiembrie 2012. Arhivat din original pe 9 noiembrie 2020. (nedefinit)
↑ SFMT: Comparație de viteză . Consultat la 15 noiembrie 2012. Arhivat din original la 8 ianuarie 2020. (nedefinit)

Literatură

M. Matsumoto, T. Nishimura. Mersenne twister: Un generator de numere pseudoaleatoare uniforme cu 623 de dimensiuni echidistribuite // ACM Trans. on Modeling and Computer Simulations: journal. - 1998. - Vol. 8 , nr. 1 . - P. 3-30 . doi : 10.1145 / 272991.272995 .
Matsumoto, M.; Kurita, Y. Generatoare Twisted GFSR (nedefinite) // ACM Trans. pe modelare și simulări pe calculator. - 1992. - V. 2 , nr 3 . - S. 179-194 . - doi : 10.1145/146382.146383 .
Matsumoto, Makoto; Nishimura, Takuji; Hagita, Mariko; Saito, Mutsuo. Criptografic Mersenne Twister și Fubuki Stream/Block Cipher (engleză) : jurnal. — 2005.
T. Nishimura. Tabelele de răsucitori Mersenne pe 64 de biți (nedefinite) // ACM Trans. pe modelare și simulări pe calculator. - 2000. - T. 10 , nr 4 . - S. 248-357 . - doi : 10.1145/369534.369540 .
Matsumoto M., Saito M., Nishimura T., Hagita M. CryptMT Stream Cipher Ver. 3.Proiectul eSTREAM (neopr.) .

Link -uri

Makoto Matsumoto, Publicații academice despre MT
Pagina de pornire Mersenne Twister, cu cod C
Cuba - o bibliotecă pentru integrarea numerică multidimensională
Twisterul Mersenne