Metoda liniară congruentă

Metoda congruențială liniară  este una dintre metodele de generare a numerelor pseudoaleatoare . Este folosit în cazuri simple și nu are putere criptografică . Inclus în bibliotecile standard ale diferitelor compilatoare .

Descriere

Metoda congruențială liniară a fost propusă de D. G. Lehmer în 1949. [1] Esența metodei este de a calcula o succesiune de numere aleatoare , presupunând

unde  este modulul ( numărul natural , relativ la care se calculează restul diviziunii ; ),  este multiplicatorul ( ),  este incrementul ( ),  este valoarea inițială ( ).

Această secvență se numește o secvență liniară congruentă . De exemplu, pentru că obținem secvența [2]

Proprietăți

O secvență liniară congruentă definită de numerele , și este periodică cu o perioadă care nu depășește . În acest caz, lungimea perioadei este egală dacă și numai dacă [3] :

  1. Numere și prime relativ ;
  2. este un multiplu al fiecărui prim care este divizor al lui ;
  3. multiplu , dacă multiplu .

Prezența acestei proprietăți pentru cazul în care  este numărul de biți dintr-un cuvânt mașină a fost dovedită de M. Greenberg . [4] Existența acestei proprietăți pentru cazul general și suficiența condițiilor au fost dovedite de TE Hull și AR Dobell . [5]   

Metoda de generare a unei secvențe congruente liniare la se numește metoda congruentă multiplicativă , iar la metoda congruentă  mixtă . Cu , numerele generate vor avea o perioadă mai scurtă decât cu , dar în anumite condiții, puteți obține o perioadă de lungime , dacă  este un număr prim . Faptul că afecțiunea poate duce la apariția unor perioade mai lungi a fost stabilit de W. E. Thomson ( ing. WT Thomson ) și independent de A. Rotenberg ( ing. A. Rotenberg ). [2] Pentru a garanta ciclul maxim de repetiție a secvenței la , este necesar să alegeți un număr prim ca valoare a parametrului. Cel mai faimos generator de acest gen este așa-numitul generator de numere aleatoare standard minime propus de Stephen Park și Keith Miller în 1988 . Pentru el , de asemenea . [6] [7]    

Metoda cea mai des practicată pentru generarea de secvențe de numere pseudoaleatoare este metoda congruențială mixtă.

Parametrii utilizați în mod obișnuit

Atunci când alegeți un număr , trebuie luate în considerare următoarele condiții:

1) numărul trebuie să fie destul de mare, deoarece perioada nu poate avea mai multe elemente;

2) valoarea numărului trebuie să fie astfel încât să poată fi calculată rapid.

În practică, atunci când implementați metoda, pe baza condițiilor specificate, alegeți cel mai adesea , unde  este numărul de biți din cuvântul mașină . În același timp, trebuie avut în vedere faptul că biții mai puțin semnificativi ai numerelor aleatoare generate în acest fel demonstrează un comportament departe de a fi aleatoriu, de aceea se recomandă folosirea doar a biților cei mai semnificativi. Această situație nu apare atunci când , unde  este lungimea unui cuvânt de mașină. În acest caz, biții inferiori se comportă la fel de aleatoriu ca și cei superiori. [2] Alegerea multiplicatorului și a incrementului se datorează în principal necesității de a îndeplini condiția de realizare a perioadei de lungime maximă.

Tabel de constante bune pentru generatoarele liniare congruențiale

Toate constantele de mai sus asigură funcționarea generatorului cu o perioadă maximă. Tabelul este ordonat după cel mai mare produs care nu provoacă debordare într-un cuvânt de lungimea specificată. [opt]

Debordează la A c m
2 20 106 1283 6075
2 21 211 1663 7875
222 _ 421 1663 7875
2 23 430 2531 11979
2 23 936 1399 6655
2 23 1366 1283 6075
2 24 171 11213 53125
2 24 859 2531 11979
2 24 419 6173 29282
2 24 967 3041 14406
2 25 141 28411 134456
2 25 625 6571 31104
2 25 1541 2957 14000
2 25 1741 2731 12960
2 25 1291 4621 21870
2 25 205 29573 139968
2 26 421 17117 81000
2 26 1255 6173 29282
2 26 281 28411 134456
2 27 1093 18257 86436
2 27 421 54773 259200
2 27 1021 24631 116640
2 28 1277 24749 117128
2 28 2041 25673 121500
2 29 2311 25367 120050
2 29 1597 51749 244944
2 29 2661 36979 175000
2 29 4081 25673 121500
2 29 3661 30809 145800
2 30 3877 29573 139968
2 30 3613 45289 214326
2 30 1366 150889 714025
2 31 8121 28411 134456
2 31 4561 51349 243000
2 31 7141 54773 259200
2 32 9301 49297 233280
2 32 4096 150889 714025
2 33 2416 374441 1771875
2 34 17221 107839 510300
2 34 36261 66037 312500
2 35 84589 45989 217728

Algoritmul RANDU „nereușit” (în ceea ce privește calitatea secvenței de ieșire) , care a fost folosit în diferite compilatoare de multe decenii, este infam.

Pentru a îmbunătăți proprietățile statistice ale unei secvențe de numere, mulți generatori de numere pseudoaleatoare folosesc doar un subset de biți de rezultat. De exemplu, standardul ISO/IEC 9899 C furnizează (dar nu specifică ca fiind obligatoriu) un exemplu de funcție rand() care forțează eliminarea cifrei 16 mici și a unei cifre înalte.

#define RAND_MAX 32767 static unsigned long int next = 1 ; int rand ( vod ) { următorul = următorul * 1103515245 + 12345 ; return ( unsigned int )( next / 65536 ) % ( RAND_MAX + 1 ); } void srand ( sedinta int nesemnata ) { următorul = sămânță ; }

Acesta este modul în care funcția rand() este utilizată în compilatoarele Watcom C/C++ . Sunt cunoscuți parametrii numerici ai altor algoritmi utilizați în diverse compilatoare și biblioteci.

Sursă m factorul a termenul c biți folosiți
Rețete numerice [9] 2 32 1664525 1013904223
Borland C/C++ 2 32 22695477 unu biți 30..16 în rand() , 30..0 în lrand()
glibc (utilizat de GCC ) [10] 2 31 1103515245 12345 biți 30..0
ANSI C : Watcom , Digital Mars , CodeWarrior , IBM VisualAge C/C++ [11] 2 31 1103515245 12345 biții 30..16
C99 , C11 : Sugestie în ISO/IEC 9899 [12] 2 32 1103515245 12345 biții 30..16
Borland Delphi , Virtual Pascal 2 32 134775813 unu biți 63..32 din (sămânță * L)
Microsoft Visual/Quick C/C++ 2 32 214013 ( 343FD16 ) 2531011 (269EC3 16 ) biții 30..16
Microsoft Visual Basic (6 și anterioare) [13] 2 24 1140671485 (43FD43FD 16 ) 12820163 (C39EC3 16 )
RtlUniform din API-ul nativ [14] 2 31 − 1 2147483629 (7FFFFFED 16 ) 2147483587 (7FFFFFC3 16 )
Apple CarbonLib , C++11 [ minstd_rand015] 2 31 − 1 16807 0 vezi MINSTD
C++11 [ minstd_rand15] 2 31 − 1 48271 0 vezi MINSTD
MMIX de Donald Knuth 264 _ 6364136223846793005 1442695040888963407
Newlib 264 _ 6364136223846793005 unu biții 63...32
MTH$RANDOM al lui VAX , [16] versiuni vechi ale glibc 2 32 69069 unu
Java 248 _ 25214903917 unsprezece biții 47...16
Mai devreme în multe compilatoare:
RANDU 2 31   65539 0

Posibilitate de utilizare în criptografie

Deși metoda congruențială liniară generează o secvență pseudo-aleatoare de numere statistic bună, nu este sigură criptografic. Generatoarele bazate pe metoda congruențială liniară sunt predictibile, deci nu pot fi utilizate în criptografie. Generatoarele liniare congruențiale au fost piratate mai întâi de Jim Reeds și mai târziu de Joan Boyar. De asemenea, a reușit să deschidă generatoare pătratice și cubice. Alți cercetători au extins ideile lui Boyar dezvoltând modalități de a sparge orice generator de polinom. Astfel, s-a dovedit inutilitatea generatoarelor bazate pe metode congruente pentru criptografie. Cu toate acestea, generatoarele congruențiale liniare rămân utili pentru aplicații non-criptografice, cum ar fi simularea. Sunt eficiente și prezintă performanțe statistice bune în majoritatea testelor empirice utilizate [8] .

Vezi și

Note

  1. ↑ D.H. Lehmer, Mathematical methods in large-scale computing units, Proceedings of a Second Symposium on Large-Scale Digital Calculating Machinery, 1949, Harvard University Press, Cambridge, Mass., 1951, pp. 141-146. MR 0044899 (13.495f) [1] Arhivat 24 decembrie 2013 la Wayback Machine
  2. ↑ 1 2 3 Donald Knuth . Volumul 2. Metode derivate // Arta programarii. Decret. op. - S. 21-37.
  3. ↑ D. E. Knut, Arta programarii. Volumul 2. Metode derivate - Williams. 2001. pp.21-37
  4. ↑ M. Greenberger, Method in randomness, Comm. ACM 8 (1965), 177-179. [2] Arhivat pe 24 decembrie 2013 la Wayback Machine
  5. ^ TE Hull și AR Dobell „Random Number Generators”, SIAM Review 4-3 (1962), 230-254 [3] Arhivat pe 24 decembrie 2013 la Wayback Machine
  6. ↑ „D.M. Bucknell. Fundamental Algorithms and Data Structures in Delphi. Programmer's Library. 2002. Delphi Informant Magazine. Capitolul 6.
  7. ↑ Stephen K. Park și Keith W. Miller (1988). Generatoare de numere aleatorii: cele bune sunt greu de găsit. Comunicații ale ACM 31 (10): 1192-1201 [4] Arhivat 4 aprilie 2019 la Wayback Machine
  8. ↑ 1 2 Bruce Schneier . Capitolul 16. // Criptografia aplicată. Triumph. 2002. Decret. op. — P. 275. [5] Arhivat la 28 februarie 2014 la Wayback Machine
  9. ↑ Rețete numerice în C. Arta calculului științific. editia a 2-a. - Cambridge University Press, 1992. - 925 p.
  10. ↑ Rand() din biblioteca GNU C din stdlib.h folosește un generator congruențial liniar simplu (o singură stare) numai în cazul în care starea este declarată ca 8 octeți. Dacă starea este mai mare (o matrice), generatorul devine un generator de feedback aditiv și perioada crește. Vezi codul simplificat Arhivat 2 februarie 2015 la Wayback Machine care reproduce secvența aleatorie din această bibliotecă.
  11. ↑ O colecție de generatoare de numere pseudoaleatoare selectate cu structuri liniare, K. Entacher, 1997 . Consultat la 16 iunie 2012. Arhivat din original pe 5 iunie 2013.
  12. ↑ Ultimul proiect public al Comisiei din 12 aprilie 2011, pag. 346f . Preluat la 21 decembrie 2014. Arhivat din original la 25 decembrie 2021.
  13. ↑ Cum generează Visual Basic numere pseudoaleatoare pentru funcția RND . Asistență Microsoft . Microsoft. Consultat la 17 iunie 2011. Arhivat din original la 17 aprilie 2011.
  14. ↑ În ciuda documentației de pe MSDN , arhivată la 8 martie 2016 la Wayback Machine , RtlUniform folosește LCG, și nu algoritmul lui Lehmer, implementările înainte de Windows Vista sunt defecte, deoarece rezultatul înmulțirii este redus la 32 de biți, înainte ca modulo să fie aplicat.
  15. ↑ 12 ISO/IEC 14882 :2011 . ISO (2 septembrie 2011). Preluat la 3 septembrie 2011. Arhivat din original la 17 mai 2013.
  16. ↑ Biblioteca științifică GNU: Alți generatori de numere aleatorii . Data accesului: 10 ianuarie 2015. Arhivat din original pe 11 decembrie 2014.

Literatură

  • Donald E. Knuth . Capitolul 3. Numere aleatorii // Arta programarii pe computer. - Ed. a 3-a. - M. : Williams , 2000. - V. 2. Algoritmi obținuți. — 832 p. - 7000 de exemplare.  - ISBN 5-8459-0081-6 (rusă) ISBN 0-201-89684-2 (engleză).

Link -uri