Lineær kongruent metode

Den lineære kongruentielle metode er en af metoderne til at generere pseudo-tilfældige tal . Det bruges i simple tilfælde og har ikke kryptografisk styrke . Inkluderet i standardbibliotekerne for forskellige compilere .

Beskrivelse

Den lineære kongruentielle metode blev foreslået af D. G. Lehmer i 1949. [1] Essensen af metoden er at beregne en sekvens af tilfældige tal , forudsat $X_{{n}}$

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

hvor er modulet ( naturligt tal , i forhold til hvilket resten af divisionen beregnes ; ), er multiplikatoren ( ), er tilvæksten ( ), er startværdien ( ). $m$ $m\geqslant 2$ $-en$ $0\leqslant a<m$ $c$ $0\leqslant c<m$ $X_{{0}}$ $0\leqslant X_{0}<m$

Denne sekvens kaldes en lineær kongruent sekvens . For eksempel får vi sekvensen [2] $m=10,X_{{0}}=a=c=7$ $7,6,9,0,7,6,9,0,\prikker$

Egenskaber

En lineær kongruent sekvens defineret af tallene , og er periodisk med en periode, der ikke overstiger . I dette tilfælde er længden af perioden lig, hvis og kun hvis [3] : $m$ $-en$ $c$ $X_{{0}}$ $m$ $m$

Tal og relativt primtal ; $c$ $m$
$b=a-1$ er et multiplum af hvert primtal , der er en divisor af ; $s$ $s$ $m$
$b$ flere , hvis flere . $fire$ $m$ $fire$

Tilstedeværelsen af denne egenskab for sagen , hvor er antallet af bits i et maskinord , blev bevist af M. Greenberg . [4] Eksistensen af denne ejendom for den generelle sag og tilstrækkeligheden af betingelserne blev bevist af TE Hull og AR Dobell . [5] $m=2^{e}$ $e$

Metoden til at generere en lineær kongruent sekvens ved kaldes den multiplikative kongruente metode og ved den blandede kongruente metode . Med , vil de genererede tal have en kortere periode end med , men under visse betingelser kan du få en periode med længde , hvis er et primtal . Det faktum, at tilstanden kan føre til fremkomsten af længere perioder, blev fastslået af W. E. Thomson ( eng. WT Thomson ) og selvstændigt af A. Rotenberg ( eng. A. Rotenberg ). [2] For at garantere den maksimale sekvensgentagelsescyklus ved , er det nødvendigt at vælge et primtal som parameterværdi. Den mest berømte generator af denne art er den såkaldte minimum standard tilfældige talgenerator foreslået af Stephen Park og Keith Miller i 1988 . Også for ham . [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$

Den mest almindeligt praktiserede metode til at generere sekvenser af pseudo-tilfældige tal er den blandede kongruentielle metode.

Almindeligt anvendte parametre

Når du vælger et nummer , skal følgende forhold tages i betragtning: $m$

1) tallet skal være ret stort, da perioden ikke kan have flere elementer; $m$ $m$

2) værdien af tallet skal være sådan, at det kan beregnes hurtigt. $m$ $(aX_{{n}}+c)\mod m$

I praksis, når man implementerer metoden, baseret på de angivne betingelser, vælger man oftest , hvor er antallet af bits i maskinordet . Samtidig skal det tages i betragtning, at de mindst signifikante bits af de tilfældige tal, der genereres på denne måde, viser adfærd, der er langt fra tilfældig, så det anbefales kun at bruge de mest signifikante bits. Denne situation opstår ikke, når , hvor er længden af et maskinord. I dette tilfælde opfører de lavere bits sig lige så tilfældigt som de højere. [2] Valget af multiplikator og stigning skyldes primært behovet for at opfylde betingelsen for at opnå den maksimale længdeperiode. $m=2^{e}$ $e$ $m=w\pm 1$ $w$ $X_{{n}}$ $-en$ $c$

Tabel over gode konstanter for lineære kongruentiale generatorer

Alle ovenstående konstanter sikrer driften af generatoren med en maksimal periode. Tabellen er sorteret efter det største produkt, der ikke forårsager overløb i et ord af den angivne længde. [otte]

Overløb kl	-en	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

Den "mislykkede" (med hensyn til kvaliteten af outputsekvensen) RANDU- algoritme , som har været brugt i forskellige compilere i mange årtier, er berygtet.

For at forbedre de statistiske egenskaber af en talsekvens bruger mange pseudo-tilfældige talgeneratorer kun en delmængde af resultatbittene. For eksempel giver ISO/IEC 9899 C-standarden (men angiver ikke som obligatorisk) et eksempel på en rand()-funktion, der tvinger de lave 16'ere og et højt ciffer til at blive kasseret.

#define RAND_MAX 32767 statisk unsigned long int next = 1 ; int rand ( ugyldig ) { næste = næste * 1103515245 + 12345 ; return ( usigneret int )( næste / 65536 ) % ( RAND_MAX + 1 ); } void srand ( usigneret int seed ) { næste = frø ; }

Sådan bruges rand()-funktionen i Watcom C/C++-kompilatorerne . De numeriske parametre for andre algoritmer, der anvendes i forskellige compilere og biblioteker, er kendte.

Kilde	m	faktor a	sigt c	brugte bits
Numeriske opskrifter [9]	2 32	1664525	1013904223
Borland C/C++	2 32	22695477	en	bits 30..16 i rand() , 30..0 i lrand()
glibc (brugt af GCC ) [10]	2 31	1103515245	12345	bit 30..0
ANSI C : Watcom , Digital Mars , CodeWarrior , IBM VisualAge C/C++ [11]	2 31	1103515245	12345	bit 30..16
C99 , C11 : Forslag i ISO/IEC 9899 [12]	2 32	1103515245	12345	bit 30..16
Borland Delphi , Virtual Pascal	2 32	134775813	en	bits 63..32 af (seed * L)
Microsoft Visual/Quick C/C++	2 32	214013 ( 343FD16 )	2531011 (269EC3 16 )	bit 30..16
Microsoft Visual Basic (6 og tidligere) [13]	2 24	1140671485 (43FD43FD 16 )	12820163 (C39EC3 16 )
RtlUniform fra Native API [14]	2 31 - 1	2147483629 (7FFFFFED 16 )	2147483587 (7FFFFFC3 16 )
Apple CarbonLib , C++ 11'er minstd_rand0[15]	2 31 - 1	16807	0	se MINSTD
C++ 11'er minstd_rand[15]	2 31 - 1	48271	0	se MINSTD
MMIX af Donald Knuth	264 _	6364136223846793005	1442695040888963407
Newlib	264 _	6364136223846793005	en	bit 63…32
VAX 's MTH$RANDOM , [16] gamle versioner af glibc	2 32	69069	en
Java	248 _	25214903917	elleve	bit 47…16
Tidligere i mange compilere:
RANDU	2 31	65539	0

Mulighed for brug i kryptografi

Selvom den lineære kongruentielle metode genererer en statistisk god pseudo-tilfældig række af tal, er den ikke kryptografisk sikker. Generatorer baseret på den lineære kongruentielle metode er forudsigelige, så de kan ikke bruges i kryptografi. Lineære kongruentielle generatorer blev først hacket af Jim Reeds og senere af Joan Boyar. Hun formåede også at åbne kvadratiske og kubiske generatorer. Andre forskere har udvidet Boyars ideer ved at udvikle måder at bryde enhver polynomiegenerator på. Således blev ubrugeligheden af generatorer baseret på kongruente metoder til kryptografi bevist. Imidlertid forbliver lineære kongruentielle generatorer nyttige til ikke-kryptografiske applikationer såsom simulering. De er effektive og viser god statistisk ydeevne i de fleste af de anvendte empiriske tests [8] .

Se også

Noter

↑ 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, s. 141-146. MR 0044899 (13.495f) [1] Arkiveret 24. december 2013 på Wayback Machine
↑ 1 2 3 Donald Knuth . Bind 2. Afledte metoder // Kunsten at programmere. Dekret. op. - S. 21-37.
↑ D. E. Knut, Kunsten at programmere. Bind 2. Afledte metoder - Williams. 2001. s. 21-37
↑ M. Greenberger, Method in randomness, Comm. ACM 8 (1965), 177-179. [2] Arkiveret 24. december 2013 på Wayback Machine
↑ TE Hull og AR Dobell "Random Number Generators", SIAM Review 4-3(1962), 230-254 [3] Arkiveret 24. december 2013 på Wayback Machine
↑ "D.M. Bucknell. Fundamentale algoritmer og datastrukturer i Delphi. Programmers bibliotek. 2002. Delphi Informant Magazine. Kapitel 6.
↑ Stephen K. Park og Keith W. Miller (1988). Tilfældige talgeneratorer: Gode er svære at finde. Kommunikation af ACM 31 (10): 1192-1201 [4] Arkiveret 4. april 2019 på Wayback Machine
↑ 1 2 Bruce Schneier . Kapitel 16. // Anvendt kryptografi. Triumph. 2002. Dekret. op. — S. 275. [5] Arkiveret 28. februar 2014 på Wayback Machine
↑ Numeriske opskrifter i C. The art of scientific computing. 2. udgave. - Cambridge University Press, 1992. - 925 s.
↑ GNU C-bibliotekets rand() i stdlib.h bruger en simpel (enkelttilstand) lineær kongruentialgenerator kun i tilfælde af, at tilstanden er erklæret som 8 bytes. Hvis tilstanden er større (et array), bliver generatoren en additiv feedback-generator, og perioden øges. Se den forenklede kode Arkiveret 2. februar 2015 på Wayback Machine , der gengiver den tilfældige sekvens fra dette bibliotek.
↑ En samling af udvalgte pseudorandom-talgeneratorer med lineære strukturer, K. Entacher, 1997 . Hentet 16. juni 2012. Arkiveret fra originalen 5. juni 2013. (ubestemt)
↑ Sidste offentlige udvalgsudkast fra 12. april 2011, side 346f . Hentet 21. december 2014. Arkiveret fra originalen 25. december 2021. (ubestemt)
↑ Hvordan Visual Basic genererer pseudo-tilfældige tal til RND-funktionen . Microsoft Support . Microsoft. Hentet 17. juni 2011. Arkiveret fra originalen 17. april 2011. (ubestemt)
↑ På trods af dokumentation på MSDN Arkiveret 8. marts 2016 på Wayback Machine , bruger RtlUniform LCG, og ikke Lehmers algoritme, er implementeringer før Windows Vista fejlbehæftede, fordi resultatet af multiplikation skæres til 32 bit, før modulo anvendes
↑ 12 ISO/IEC 14882 :2011 . ISO (2. september 2011). Hentet 3. september 2011. Arkiveret fra originalen 17. maj 2013. (ubestemt)
↑ GNU Scientific Library: Andre tilfældige talgeneratorer . Dato for adgang: 10. januar 2015. Arkiveret fra originalen 11. december 2014. (ubestemt)

Litteratur

Donald E. Knuth . Kapitel 3. Tilfældige tal // Kunsten at programmere computer. - 3. udg. - M. : Williams , 2000. - V. 2. Opnåede algoritmer. — 832 s. - 7000 eksemplarer. - ISBN 5-8459-0081-6 (russisk) ISBN 0-201-89684-2 (engelsk).