Lineáris kongruens módszer

A lineáris kongruenciális módszer a pszeudo-véletlen számok generálásának egyik módszere . Egyszerű esetekben használják, és nincs kriptográfiai erőssége . Különböző fordítók standard könyvtáraiban megtalálható .

Leírás

A lineáris kongruenciális módszert D. G. Lehmer javasolta 1949-ben. [1] A módszer lényege, hogy véletlen számok sorozatát számítjuk ki , feltételezve $X_{{n}}$

X_{{n+1}}=(aX_{n}+c)~~{\bmod ~}~m,

ahol a modulus ( természetes szám , amelyhez viszonyítva az osztás maradékát számítjuk ; ), a szorzó ( ), a növekmény ( ), a kezdeti érték ( ). $m$ $m\geqslant 2$ $a$ $0\leqslant a<m$ $c$ $0\leqslant c<m$ $X_{{0}}$ $0\leqslant X_{0}<m$

Ezt a sorozatot lineáris kongruens sorozatnak nevezzük . Például a [2] sorozatot kapjuk $m=10,X_{{0}}=a=c=7$ $7,6,9,0,7,6,9,0,\pontok$

Tulajdonságok

Egy lineáris egybevágó sorozat, amelyet a , és számok határoznak meg , és periodikus , legfeljebb . Ebben az esetben az időszak hossza akkor és csak akkor egyenlő, ha [3] : $m$ $a$ $c$ $X_{{0}}$ $m$ $m$

Számok és viszonylag prím ; $c$ $m$
$b=a-1$ minden olyan prím többszöröse , amely osztója ; $p$ $p$ $m$
$b$ többszörös , ha többszörös . $négy$ $m$ $négy$

Ennek a tulajdonságnak a meglétét abban az esetben , ahol a bitek száma egy gépszóban , M. Greenberg bizonyította . [4] Ennek a tulajdonságnak az általános esetre való meglétét és a feltételek megfelelőségét TE Hull és AR Dobell bizonyította . [5] $m=2^{e}$ $e$

A lineáris kongruens sorozat generálásának módszerét multiplikatív kongruens módszernek , at vegyes kongruens módszernek nevezzük . A -val a generált számok periódusa rövidebb lesz, mint -nél , de bizonyos feltételek mellett kaphat egy hosszúságú periódust is , ha egy prímszám . Azt a tényt, hogy az állapot hosszabb időszakok megjelenéséhez vezethet, W. E. Thomson ( ang. WT Thomson ) és ettől függetlenül A. Rotenberg ( ang. A. Rotenberg ) állapította meg. [2] A maximális sorozatismétlési ciklus garantálásához paraméterértékként egy prímszámot kell választani. A leghíresebb ilyen típusú generátor az úgynevezett minimum standard véletlenszám-generátor, amelyet Stephen Park és Keith Miller javasoltak 1988 - ban . Neki is . [6] [7] $c=0$ $c\neq 0$ $c=0$ $c\neq 0$ $m-1$ $m$ $c\neq 0$ $c=0$ $m$ $a=16807$ $m=2147483647$

A pszeudo-véletlen számsorozatok generálására leggyakrabban alkalmazott módszer a vegyes kongruenciális módszer.

Gyakran használt paraméterek

A szám kiválasztásakor a következő feltételeket kell figyelembe venni: $m$

1) a számnak elég nagynak kell lennie, mivel a periódusnak nem lehet több eleme; $m$ $m$

2) a szám értéke olyan legyen, hogy gyorsan kiszámítható legyen. $m$ $(aX_{{n}}+c)\mod m$

A gyakorlatban a metódus implementálásakor a megadott feltételek alapján leggyakrabban válasszuk a -t , ahol a bitek száma a gépszóban . Ugyanakkor figyelembe kell venni, hogy az így előállított véletlen számok legkisebb jelentőségű bitjei a véletlentől távol álló viselkedést mutatnak, ezért csak a legjelentősebb bitek használata javasolt. Ez a helyzet nem fordul elő, ha , hol egy gépszó hossza. Ebben az esetben az alsó bitek ugyanolyan véletlenszerűen viselkednek, mint a magasabbak. [2] A szorzó és a növekmény megválasztása elsősorban a maximális időtartam eléréséhez szükséges feltétel teljesítésének szükségességéből fakad. $m=2^{e}$ $e$ $m=h\pm 1$ $w$ $X_{{n}}$ $a$ $c$

Lineáris kongruenciális generátorok jó állandóinak táblázata

A fenti állandók mindegyike biztosítja a generátor maximális időtartamú működését. A táblázat a legnagyobb termék szerint van rendezve, amely nem okoz túlcsordulást a megadott hosszúságú szóban. [nyolc]

Túlcsordul a	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	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	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

Hírhedt a "sikertelen" (a kimeneti sorrend minőségét tekintve) RANDU algoritmus , amelyet évtizedek óta használnak különféle fordítók.

A számsorozat statisztikai tulajdonságainak javítása érdekében sok pszeudo-véletlen számgenerátor csak az eredménybitek egy részhalmazát használja. Például az ISO/IEC 9899 C szabvány példát ad (de nem írja elő kötelezőként) a rand() függvényre, amely az alacsony 16-os és egy magas számjegy elvetését kényszeríti ki.

#define RAND_MAX 32767 statikus előjel nélküli long int next = 1 ; int rand ( érvénytelen ) { következő = következő * 1103515245 + 12345 ; return ( unsigned int )( következő / 65536 ) % ( RAND_MAX + 1 ); } void srand ( unsigned int seed ) { következő = mag ; }

Így használatos a rand() függvény a Watcom C/C++ fordítóiban . A különféle fordítóprogramokban és könyvtárakban használt más algoritmusok numerikus paraméterei ismertek.

Forrás	m	faktor a	kifejezés c	használt bitek
Numerikus receptek [9]	2 32	1664525	1013904223
Borland C/C++	2 32	22695477	egy	30..16 bit a rand() -ban, 30..0 az lrand() -ban
glibc (a GCC használja ) [10]	2 31	1103515245	12345	bitek 30...0
ANSI C : Watcom , Digital Mars , CodeWarrior , IBM VisualAge C/C++ [11]	2 31	1103515245	12345	bitek 30...16
C99 , C11 : Javaslat az ISO/IEC 9899-ben [12]	2 32	1103515245	12345	bitek 30...16
Borland Delphi , Virtual Pascal	2 32	134775813	egy	63..32. bit (mag * L)
Microsoft Visual/Quick C/C++	2 32	214013 ( 343FD16 )	2531011 (269EC3 16 )	bitek 30...16
Microsoft Visual Basic (6 és korábbi) [13]	2 24	1140671485 (43FD43FD 16 )	12820163 (C39EC3 16 )
RtlUniform a natív API -ból [14]	2 31-1 _	2147483629 (7FFFFED 16 )	2147483587 (7FFFFFC3 16 )
Apple CarbonLib , C++11 [ minstd_rand015]	2 31-1 _	16807	0	lásd MINSTD
C++11 [ minstd_rand15]	2 31-1 _	48271	0	lásd MINSTD
MMIX – Donald Knuth	264 _	6364136223846793005	1442695040888963407
Newlib	264 _	6364136223846793005	egy	bitek 63…32
VAX MTH$RANDOM , [16] a glibc régi verziói	2 32	69069	egy
Jáva	248 _	25214903917	tizenegy	bitek 47…16
Korábban sok fordítónál:
RANDU	2 31	65539	0

A kriptográfiában való felhasználás lehetősége

Bár a lineáris kongruenciális módszer statisztikailag jó pszeudo-véletlen számsort generál, kriptográfiailag nem biztonságos. A lineáris kongruenciális módszeren alapuló generátorok megjósolhatók, így a kriptográfiában nem használhatók. A lineáris kongruenciális generátorokat először Jim Reeds, majd később Joan Boyar törte fel. Sikerült négyzetes és köbös generátorokat is kinyitnia. Más kutatók kiterjesztették Boyar elképzeléseit azáltal, hogy módszereket dolgoztak ki bármilyen polinomgenerátor megtörésére. Így bebizonyosodott a kongruens módszereken alapuló generátorok kriptográfiára való haszontalansága. A lineáris kongruenciális generátorok azonban továbbra is hasznosak maradnak a nem kriptográfiai alkalmazásokhoz, például a szimulációhoz. Hatékonyak és jó statisztikai teljesítményt mutatnak a legtöbb alkalmazott empirikus tesztben [8] .

Lásd még

Jegyzetek

↑ D. H. Lehmer, Matematikai módszerek nagyméretű számítási egységekben, 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] Archiválva : 2013. december 24. a Wayback Machine -nél
↑ 1 2 3 Donald Knuth . 2. kötet. Származtatott módszerek // A programozás művészete. Rendelet. op. - S. 21-37.
↑ D. E. Knut, A programozás művészete. 2. kötet. Származtatott módszerek - Williams. 2001. pp.21-37
↑ M. Greenberger, Method in randomness, Comm. ACM 8 (1965), 177-179. [2] Archiválva : 2013. december 24. a Wayback Machine -nél
↑ TE Hull és AR Dobell "Véletlenszám-generátorok", SIAM Review 4-3(1962), 230-254 [3] Archiválva : 2013. december 24. a Wayback Machine -nél
↑ "D.M. Bucknell. Alapvető algoritmusok és adatstruktúrák a Delphiben. Programozói könyvtár. 2002. Delphi Informant Magazine. 6. fejezet.
↑ Stephen K. Park és Keith W. Miller (1988). Véletlenszám-generátorok: Nehéz jókat találni. Az ACM 31 (10): 1192-1201 kommunikációja [4] Archiválva : 2019. április 4. a Wayback Machine -nél
↑ 1 2 Bruce Schneier . 16. fejezet // Alkalmazott kriptográfia. Triumph. 2002. Rendelet. op. — P. 275. [5] Archivált 2014. február 28-án a Wayback Machine -nél
↑ Numerical recipies in C. A tudományos számítástechnika művészete. 2. kiadás. - Cambridge University Press, 1992. - 925 pp.
↑ A GNU C könyvtár rand() -ja az stdlib.h -ban csak akkor használ egyszerű (egyállapotú) lineáris kongruenciális generátort, ha az állapot 8 bájtként van deklarálva. Ha az állapot nagyobb (egy tömb), a generátor additív visszacsatolás generátorrá válik, és a periódus növekszik. Tekintse meg az egyszerűsített kódot , amely 2015. február 2-án archivált a Wayback Machine -nél , amely a könyvtár véletlenszerű sorozatát reprodukálja.
↑ Lineáris szerkezetű, válogatott pszeudovéletlen számgenerátorok gyűjteménye, K. Entacher, 1997 . Letöltve: 2012. június 16. Az eredetiből archiválva : 2013. június 5.. (határozatlan)
↑ Utolsó nyilvános bizottsági tervezet, 2011. április 12., 346f. oldal . Letöltve: 2014. december 21. Az eredetiből archiválva : 2021. december 25. (határozatlan)
↑ Hogyan generál a Visual Basic pszeudo-véletlen számokat az RND függvényhez ? Microsoft támogatás . Microsoft. Letöltve: 2011. június 17. Az eredetiből archiválva : 2011. április 17.. (határozatlan)
↑ Az MSDN dokumentációja ellenére, 2016. március 8-án archiválva a Wayback Machine -nél, az RtlUniform LCG-t használ, nem Lehmer algoritmusát, a Windows Vista előtti implementációk hibásak, mert a szorzás eredménye 32 bitre van vágva a modulo alkalmazása előtt
↑ 12 ISO/IEC 14882 :2011 . ISO (2011. szeptember 2.). Letöltve: 2011. szeptember 3. Az eredetiből archiválva : 2013. május 17. (határozatlan)
↑ GNU Tudományos Könyvtár: Egyéb véletlenszám-generátorok . Hozzáférés időpontja: 2015. január 10. Az eredetiből archiválva : 2014. december 11. (határozatlan)

Irodalom

Donald E. Knuth . 3. fejezet Véletlen számok // A számítógépes programozás művészete. - 3. kiadás - M .: Williams , 2000. - V. 2. Megszerzett algoritmusok. — 832 p. - 7000 példány. - ISBN 5-8459-0081-6 (orosz) ISBN 0-201-89684-2 (angol).

Linkek

L. Barash. Az AKS-algoritmus a számok egyszerűségének ellenőrzésére és pszeudo-véletlenszám-generátorok állandóinak keresésére // Információs technológiák biztonsága. - 2005. - 2. sz . - S. 27-38 .
Stephen K. Park és Keith W. Miller. Véletlenszám-generátorok: Nehéz jókat találni . - 1988. - 2. sz . - S. 1192-1201 .
Bucknell D.M. Alapvető algoritmusok és adatstruktúrák a Delphiben.Programozói könyvtár. [6] // Delphi Informant Magazine . – 2002.