Lineaarinen kongruenttimenetelmä

Lineaarinen kongruenssimenetelmä  on yksi menetelmistä pseudosatunnaislukujen generoimiseksi . Sitä käytetään yksinkertaisissa tapauksissa, eikä sillä ole kryptografista vahvuutta . Sisältyy eri kääntäjien vakiokirjastoihin .

Kuvaus

Lineaarista kongruenssimenetelmää ehdotti D. G. Lehmer vuonna 1949. [1] Menetelmän ydin on laskea satunnaislukusarja olettaen

missä  on moduuli ( luonnollinen luku , johon suhteutettuna jaon jäännös lasketaan ; ),  on kerroin ( ),  on lisäys ( ),  on alkuarvo ( ).

Tätä sekvenssiä kutsutaan lineaariseksi kongruenttiksi sekvenssiksi . Esimerkiksi saamme sekvenssin [2]

Ominaisuudet

Lineaarinen yhtenevä sarja, joka määritellään luvuilla , ja on jaksollinen jakson ollessa enintään . Tässä tapauksessa jakson pituus on yhtä suuri, jos ja vain jos [3] :

  1. Numerot ja suhteellisen alkuluku ;
  2. on kerrannainen jokaisen prime , joka on jakaja ;
  3. useita , jos useita .

Tämän ominaisuuden olemassaolon tapaukselle , jossa  on konesanan bittien määrä , osoitti M. Greenberg . [4] TE Hull ja AR Dobell todistivat tämän ominaisuuden olemassaolon yleisessä tapauksessa ja ehtojen riittävyyden . [5]   

Menetelmää lineaarisen yhteneväisen sekvenssin generoimiseksi osoitteessa kutsutaan multiplikatiiviseksi kongruenttimenetelmäksi ja  sekakongruenttimenetelmäksi . Kun , luoduilla luvuilla on lyhyempi jakso kuin , mutta tietyin edellytyksin voit saada jakson, jonka pituus on , jos  on alkuluku . W.E. Thomson ( eng. WT Thomson ) ja itsenäisesti A. Rotenberg ( eng. A. Rotenberg ) totesivat sen tosiasian, että tila voi johtaa pitempien ajanjaksojen ilmaantumiseen . [2] Jotta taataan sekvenssin maksimitoistojakso kohdassa , on tarpeen valita parametrin arvoksi alkuluku. Tunnetuin tällainen generaattori on Stephen Parkin ja Keith Millerin vuonna 1988 ehdottama niin kutsuttu vähimmäisstandardi-satunnaislukugeneraattori . Myös hänelle . [6] [7]    

Yleisimmin käytetty menetelmä näennäissatunnaisten lukujen sekvenssien muodostamiseksi on sekakongruenssimenetelmä.

Yleisesti käytetyt parametrit

Numeroa valittaessa on otettava huomioon seuraavat ehdot:

1) numeron on oltava melko suuri, koska jaksossa ei voi olla enemmän elementtejä;

2) luvun arvon tulee olla sellainen, että se voidaan laskea nopeasti.

Käytännössä menetelmää toteutettaessa valitaan määritettyjen ehtojen perusteella useimmiten , jossa  on konesanan bittien määrä . Samalla on otettava huomioon, että tällä tavalla muodostettujen satunnaislukujen vähiten merkitsevät bitit osoittavat käyttäytymistä, joka on kaukana satunnaisesta, joten on suositeltavaa käyttää vain merkittävimpiä bittejä. Tätä tilannetta ei synny, kun , missä  on konesanan pituus. Tässä tapauksessa alemmat bitit käyttäytyvät yhtä satunnaisesti kuin korkeammat bitit. [2] Kertoimen ja lisäyksen valinta johtuu pääasiassa tarpeesta täyttää enimmäispituusjakson saavuttamisen ehto.

Lineaaristen kongruenssigeneraattoreiden hyvien vakioiden taulukko

Kaikki yllä olevat vakiot varmistavat generaattorin toiminnan maksimijaksolla. Taulukko on järjestetty suurimman tuotteen mukaan, joka ei aiheuta ylivuotoa määritetyn pituisessa sanassa. [kahdeksan]

Ylivuoto klo 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 14 000
2 25 1741 2731 12960
2 25 1291 4621 21870
2 25 205 29573 139968
2 26 421 17117 81 000
2 26 1255 6173 29282
2 26 281 28411 134456
2 27 1093 18257 86436
2 27 421 54773 259 200
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 175 000
2 29 4081 25673 121500
2 29 3661 30809 145 800
2 30 3877 29573 139968
2 30 3613 45289 214326
2 30 1366 150889 714025
2 31 8121 28411 134456
2 31 4561 51349 243 000
2 31 7141 54773 259 200
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

"Epäonnistunut" (tulosjonon laadun kannalta) RANDU -algoritmi , jota on käytetty useissa kääntäjissä vuosikymmeniä, on surullisen kuuluisa.

Lukusarjan tilastollisten ominaisuuksien parantamiseksi monet näennäissatunnaislukugeneraattorit käyttävät vain tulosbittien osajoukkoa. Esimerkiksi ISO/IEC 9899 C -standardi tarjoaa (mutta ei määrittele pakolliseksi) esimerkin rand()-funktiosta, joka pakottaa hylkäämään matalat 16s ja yksi korkea numero.

#define RAND_MAX 32767 staattinen etumerkitön pitkä int seuraava = 1 ; int rand ( tyhjä ) { seuraava = seuraava * 1103515245 + 12345 ; paluu ( unsigned int )( seuraava / 65536 ) % ( RAND_MAX + 1 ); } void srand ( unsigned int seed ) { seuraava = siemen ; }

Näin rand()-funktiota käytetään Watcom C/C++ -kääntäjässä . Muiden eri kääntäjissä ja kirjastoissa käytettyjen algoritmien numeeriset parametrit tunnetaan.

Lähde m tekijä a termi c käytettyjä bittejä
Numeeriset reseptit [9] 2 32 1664525 1013904223
Borland C/C++ 2 32 22695477 yksi bitit 30..16 in rand() , 30..0 in lrand()
glibc ( GCC :n käyttämä ) [10] 2 31 1103515245 12345 bittiä 30...0
ANSI C : Watcom , Digital Mars , CodeWarrior , IBM VisualAge C/C++ [11] 2 31 1103515245 12345 bittiä 30...16
C99 , C11 : Ehdotus standardissa ISO/IEC 9899 [12] 2 32 1103515245 12345 bittiä 30...16
Borland Delphi , Virtual Pascal 2 32 134775813 yksi bitit 63..32 / (siemen * L)
Microsoft Visual/Quick C/C++ 2 32 214013 ( 343FD16 ) 2531011 (269EC3 16 ) bittiä 30...16
Microsoft Visual Basic (6 ja aikaisemmat) [13] 2 24 1140671485 (43FD43FD 16 ) 12820163 (C39EC3 16 )
RtlUniform alkuperäisestä sovellusliittymästä [14] 2 31 - 1 2147483629 (7FFFFFED 16 ) 2147483587 (7FFFFFC3 16 )
Apple CarbonLib , C++11 's minstd_rand0[15] 2 31 - 1 16807 0 katso MINSTD
C++11 :t minstd_rand[15] 2 31 - 1 48271 0 katso MINSTD
Donald Knuthin MMIX 264 _ 6364136223846793005 1442695040888963407
Newlib 264 _ 6364136223846793005 yksi bitit 63…32
VAX :n MTH$RANDOM , [16] glibc :n vanhat versiot 2 32 69069 yksi
Java 248 _ 25214903917 yksitoista bitit 47…16
Aiemmin monissa kääntäjissä:
RANDU 2 31   65539 0

Mahdollisuus käyttää kryptografiassa

Vaikka lineaarinen kongruenssimenetelmä tuottaa tilastollisesti hyvän näennäissatunnaisen numerosarjan, se ei ole kryptografisesti turvallinen. Lineaariseen kongruenssimenetelmään perustuvat generaattorit ovat ennakoitavissa, joten niitä ei voida käyttää kryptografiassa. Lineaariset yhtenevät generaattorit hakkeroivat ensin Jim Reeds ja myöhemmin Joan Boyar. Hän onnistui myös avaamaan neliö- ja kuutiogeneraattoreita. Muut tutkijat ovat laajentaneet Boyarin ideoita kehittämällä tapoja rikkoa mikä tahansa polynomigeneraattori. Siten todettiin kongruentteihin menetelmiin perustuvien generaattoreiden hyödyttömyys kryptografialle. Lineaariset kongruenssigeneraattorit ovat kuitenkin edelleen hyödyllisiä ei-salauksen sovelluksissa, kuten simulaatiossa. Ne ovat tehokkaita ja osoittavat hyvää tilastollista suorituskykyä useimmissa käytetyissä empiirisissa testeissä [8] .

Katso myös

Muistiinpanot

  1. ↑ D.H. Lehmer, Matemaattiset menetelmät suuren mittakaavan laskentayksiköissä, 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] Arkistoitu 24. joulukuuta 2013 Wayback Machinessa
  2. ↑ 1 2 3 Donald Knuth . Osa 2. Johdetut menetelmät // Ohjelmoinnin taito. asetus. op. - S. 21-37.
  3. ↑ D. E. Knut, Ohjelmoinnin taito. Osa 2. Johdetut menetelmät - Williams. 2001. s. 21-37
  4. ↑ M. Greenberger, Method in randomness, Comm. ACM 8 (1965), 177-179. [2] Arkistoitu 24. joulukuuta 2013 Wayback Machinessa
  5. ↑ TE Hull ja AR Dobell "Random Number Generators", SIAM Review 4-3(1962), 230-254 [3] Arkistoitu 24. joulukuuta 2013 Wayback Machinessa
  6. ↑ "D.M. Bucknell. Delphin perusalgoritmit ja tietorakenteet. Ohjelmoijan kirjasto. 2002. Delphi Informant Magazine. Luku 6.
  7. ↑ Stephen K. Park ja Keith W. Miller (1988). Satunnaislukugeneraattorit: Hyviä on vaikea löytää. ACM 31:n (10) viestintä: 1192-1201 [4] Arkistoitu 4. huhtikuuta 2019 Wayback Machinessa
  8. ↑ 1 2 Bruce Schneier . Luku 16. // Sovellettu kryptografia. Triumph. 2002. asetus. op. — s. 275. [5] Arkistoitu 28. helmikuuta 2014 Wayback Machinessa
  9. ↑ Numeeriset reseptit C:ssä. Tieteellisen laskennan taide. 2. painos. - Cambridge University Press, 1992. - 925 s.
  10. ↑ GNU C -kirjaston rand() stdlib.h : ssa käyttää yksinkertaista (yksitila) lineaarista kongruenssigeneraattoria vain siinä tapauksessa, että tila on ilmoitettu 8 tavua. Jos tila on suurempi (joukko), generaattorista tulee additiivinen takaisinkytkentägeneraattori ja jakso kasvaa. Katso yksinkertaistettu koodi Arkistoitu 2. helmikuuta 2015 Wayback Machinessa , joka toistaa satunnaisen sekvenssin tästä kirjastosta.
  11. ↑ Kokoelma valikoituja näennäissatunnaislukugeneraattoreita lineaarisilla rakenteilla, K. Entacher, 1997 . Haettu 16. kesäkuuta 2012. Arkistoitu alkuperäisestä 5. kesäkuuta 2013.
  12. ↑ Viimeisin julkinen valiokuntaluonnos 12. huhtikuuta 2011, sivu 346f . Haettu 21. joulukuuta 2014. Arkistoitu alkuperäisestä 25. joulukuuta 2021.
  13. ↑ Kuinka Visual Basic luo pseudosatunnaislukuja RND-funktiolle . Microsoftin tuki . Microsoft. Haettu 17. kesäkuuta 2011. Arkistoitu alkuperäisestä 17. huhtikuuta 2011.
  14. ↑ Huolimatta MSDN -dokumentaatiosta, joka on arkistoitu 8. maaliskuuta 2016 Wayback Machinessa , RtlUniform käyttää LCG:tä, ei Lehmerin algoritmia, Windows Vistaa edeltävät toteutukset ovat virheellisiä, koska kertolaskutulos leikataan 32 -bittiseksi ennen modulon käyttöönottoa.
  15. ↑ 12 ISO/IEC 14882 :2011 . ISO (2. syyskuuta 2011). Haettu 3. syyskuuta 2011. Arkistoitu alkuperäisestä 17. toukokuuta 2013.
  16. ↑ GNU Scientific Library: Muut satunnaislukugeneraattorit . Käyttöpäivä: 10. tammikuuta 2015. Arkistoitu alkuperäisestä 11. joulukuuta 2014.

Kirjallisuus

  • Donald E. Knuth . Luku 3. Satunnaisluvut // Tietokoneohjelmoinnin taito. - 3. painos - M .: Williams , 2000. - V. 2. Saadut algoritmit. — 832 s. - 7000 kappaletta.  - ISBN 5-8459-0081-6 (venäjä) ISBN 0-201-89684-2 (englanniksi).

Linkit