Metoda lineární kongruence

Lineární kongruenciální metoda  je jednou z metod generování pseudonáhodných čísel . Používá se v jednoduchých případech a nemá kryptografickou sílu . Zahrnuto ve standardních knihovnách různých kompilátorů .

Popis

Lineární kongruenciální metoda byla navržena D. G. Lehmerem v roce 1949. [1] Podstatou metody je vypočítat posloupnost náhodných čísel za předpokladu

kde  je modul ( přirozené číslo , vzhledem ke kterému se vypočítá zbytek dělení ; ),  je násobitel ( ),  je přírůstek ( ),  je počáteční hodnota ( ).

Tato posloupnost se nazývá lineární kongruentní posloupnost . Například pro dostaneme sekvenci [2]

Vlastnosti

Lineární kongruentní posloupnost definovaná čísly , , a je periodická s tečkou nepřesahující . V tomto případě je délka období stejná právě tehdy, když [3] :

  1. Čísla a relativně prvočísla ;
  2. je násobkem každého prvočísla , které je dělitelem ;
  3. vícenásobný , je - li vícenásobný .

Přítomnost této vlastnosti pro případ , kde  je počet bitů ve strojovém slově , dokázal M. Greenberg . [4] Existenci této vlastnosti pro obecný případ a dostatečnost podmínek prokázali TE Hull a AR Dobell . [5]   

Metoda generování lineární kongruentní posloupnosti se nazývá multiplikativní kongruentní metoda au  smíšená kongruentní metoda . S , vygenerovaná čísla budou mít kratší tečku než s , ale za určitých podmínek můžete získat tečku délky , pokud  je prvočíslo . Skutečnost, že stav může vést ke vzniku delších období, zjistil W. E. Thomson ( eng. WT Thomson ) a nezávisle na tom A. Rotenberg ( eng. A. Rotenberg ). [2] Aby byl zaručen maximální cyklus opakování sekvence při , je nutné jako hodnotu parametru zvolit prvočíslo. Nejznámějším generátorem tohoto druhu je takzvaný minimální standardní generátor náhodných čísel navržený Stephenem Parkem a Keithem Millerem v roce 1988 . Pro něj také . [6] [7]    

Nejběžněji praktikovanou metodou pro generování posloupností pseudonáhodných čísel je smíšená kongruenciální metoda.

Běžně používané parametry

Při výběru čísla je třeba vzít v úvahu následující podmínky:

1) číslo musí být poměrně velké, protože období nemůže mít více prvků;

2) hodnota čísla by měla být taková, aby se dala rychle vypočítat.

V praxi se při implementaci metody na základě zadaných podmínek nejčastěji volí , kde  je počet bitů ve strojovém slově . Zároveň je třeba vzít v úvahu, že nejméně významné bity takto generovaných náhodných čísel vykazují chování, které není náhodné, proto se doporučuje používat pouze nejvýznamnější bity. Tato situace nenastane, když , kde  je délka strojového slova. V tomto případě se nižší bity chovají stejně náhodně jako ty vyšší. [2] Volba násobiče a přírůstku je dána především nutností splnit podmínku pro dosažení maximální délky periody.

Tabulka dobrých konstant pro lineární kongruenciální generátory

Všechny výše uvedené konstanty zajišťují provoz generátoru s maximální periodou. Tabulka je řazena podle největšího produktu, který nezpůsobuje přetečení ve slově zadané délky. [osm]

Přetéká v 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 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 175 000
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 243 000
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 312 500
2 35 84589 45989 217728

Neblaze proslulý je „neúspěšný“ (z hlediska kvality výstupní sekvence) algoritmus RANDU , který se v různých kompilátorech používá již řadu desetiletí.

Pro zlepšení statistických vlastností číselné sekvence používá mnoho generátorů pseudonáhodných čísel pouze podmnožinu výsledných bitů. Například norma ISO/IEC 9899 C poskytuje (avšak nespecifikuje jako povinný) příklad funkce rand(), která vynutí vyřazení nízkých 16s a jedné vysoké číslice.

#define RAND_MAX 32767 static unsigned long int next = 1 ; int rand ( neplatné ) { další = další * 1103515245 + 12345 ; return ( unsigned int )( next / 65536 ) % ( RAND_MAX + 1 ); } void srand ( nepodepsané int seed ) { další = semeno ; }

Takto se funkce rand() používá v kompilátorech Watcom C/C++ . Numerické parametry dalších algoritmů používaných v různých překladačích a knihovnách jsou známy.

Zdroj m faktor a termín c použité bity
Numerické recepty [9] 2 32 1664525 1013904223
Borland C/C++ 2 32 22695477 jeden bity 30..16 v rand() , 30..0 v lrand()
glibc (používá GCC ) [10] 2 31 1103515245 12345 bity 30..0
ANSI C : Watcom , Digital Mars , CodeWarrior , IBM VisualAge C/C++ [11] 2 31 1103515245 12345 bity 30..16
C99 , C11 : Návrh v ISO/IEC 9899 [12] 2 32 1103515245 12345 bity 30..16
Borland Delphi , virtuální Pascal 2 32 134775813 jeden bity 63..32 z (semena * L)
Microsoft Visual/Quick C/C++ 2 32 214013 ( 343FD16 ) 2531011 (269EC3 16 ) bity 30..16
Microsoft Visual Basic (6 a starší) [13] 2 24 1140671485 (43FD43FD 16 ) 12820163 (C39EC3 16 )
RtlUniform z Native API [14] 2 31 − 1 2147483629 (7FFFFFED 16 ) 2147483587 (7FFFFFC3 16 )
Apple CarbonLib , C++11 [ minstd_rand015] 2 31 − 1 16807 0 viz MINISTR
C++11 [ minstd_rand15] 2 31 − 1 48271 0 viz MINISTR
MMIX od Donalda Knutha 264 _ 6364136223846793005 1442695040888963407
Newlib 264 _ 6364136223846793005 jeden bity 63…32
VAX 's MTH$RANDOM , [16] staré verze glibc 2 32 69069 jeden
Jáva 248 _ 25214903917 jedenáct bity 47…16
Dříve v mnoha kompilátorech:
RANDU 2 31   65539 0

Možnost použití v kryptografii

Přestože lineární kongruenciální metoda generuje statisticky dobrou pseudonáhodnou posloupnost čísel, není kryptograficky bezpečná. Generátory založené na lineární kongruenciální metodě jsou předvídatelné, takže je nelze použít v kryptografii. Lineární kongruenciální generátory byly nejprve hacknuty Jimem Reedsem a později Joan Boyar. Podařilo se jí také otevřít kvadratické a kubické generátory. Jiní výzkumníci rozšířili Boyarovy myšlenky vývojem způsobů, jak rozbít jakýkoli polynomiální generátor. Byla tak prokázána nepoužitelnost generátorů založených na kongruentních metodách pro kryptografii. Lineární kongruenciální generátory však zůstávají užitečné pro nekryptografické aplikace, jako je simulace. Jsou účinné a vykazují dobrou statistickou výkonnost ve většině použitých empirických testů [8] .

Viz také

Poznámky

  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] Archivováno 24. prosince 2013 na Wayback Machine
  2. ↑ 1 2 3 Donald Knuth . Svazek 2. Odvozené metody // Umění programování. Dekret. op. - S. 21-37.
  3. ↑ D. E. Knut, Umění programování. Svazek 2. Odvozené metody - Williams. 2001. str. 21-37
  4. ↑ M. Greenberger, Metoda náhodnosti, Comm. ACM 8 (1965), 177-179. [2] Archivováno 24. prosince 2013 na Wayback Machine
  5. ↑ TE Hull a AR Dobell „Generátory náhodných čísel“, SIAM Review 4-3(1962), 230-254 [3] Archivováno 24. prosince 2013 na Wayback Machine
  6. ↑ "D.M. Bucknell. Základní algoritmy a datové struktury v Delphi. Programmer's Library. 2002. Delphi Informant Magazine. Kapitola 6.
  7. ↑ Stephen K. Park a Keith W. Miller (1988). Generátory náhodných čísel: Dobré se těžko hledají. Communications of the ACM 31 (10): 1192-1201 [4] Archivováno 4. dubna 2019 na Wayback Machine
  8. ↑ 1 2 Bruce Schneier . Kapitola 16. // Aplikovaná kryptografie. Triumph. 2002. Dekret. op. — S. 275. [5] Archivováno 28. února 2014 na Wayback Machine
  9. ↑ Numerické receptury v C. Umění vědeckého počítání. 2. vydání. - Cambridge University Press, 1992. - 925 s.
  10. ↑ Knihovna GNU C rand() v stdlib.h používá jednoduchý (jednostavový) lineární kongruenciální generátor pouze v případě, že je stav deklarován jako 8 bajtů. Pokud je stav větší (pole), generátor se stává generátorem aditivní zpětné vazby a perioda se zvyšuje. Viz zjednodušený kód Archived 2 February 2015 at Wayback Machine , který reprodukuje náhodnou sekvenci z této knihovny.
  11. ↑ Sbírka vybraných generátorů pseudonáhodných čísel s lineárními strukturami, K. Entacher, 1997 . Získáno 16. června 2012. Archivováno z originálu 5. června 2013.
  12. ↑ Poslední veřejný návrh výboru z 12. dubna 2011, strana 346f . Získáno 21. prosince 2014. Archivováno z originálu dne 25. prosince 2021.
  13. ↑ Jak Visual Basic generuje pseudonáhodná čísla pro funkci RND . Podpora společnosti Microsoft . Microsoft. Získáno 17. června 2011. Archivováno z originálu 17. dubna 2011.
  14. ↑ Navzdory dokumentaci na MSDN Archived 8. března 2016 na Wayback Machine používá RtlUniform LCG, a nikoli Lehmerův algoritmus, implementace před Windows Vista jsou chybné, protože výsledek násobení je před aplikací modulo oříznut na 32 bitů.
  15. ↑ 12 ISO/IEC 14882 :2011 . ISO (2. září 2011). Získáno 3. září 2011. Archivováno z originálu 17. května 2013.
  16. ↑ GNU Scientific Library: Jiné generátory náhodných čísel . Datum přístupu: 10. ledna 2015. Archivováno z originálu 11. prosince 2014.

Literatura

  • Donald E. Knuth . Kapitola 3. Náhodná čísla // Umění počítačového programování. - 3. vyd. - M .: Williams , 2000. - V. 2. Získané algoritmy. — 832 s. - 7000 výtisků.  - ISBN 5-8459-0081-6 (ruština) ISBN 0-201-89684-2 (anglicky).

Odkazy