Linjär kongruent metod

Den linjära kongruentialmetoden  är en av metoderna för att generera pseudoslumptal . Det används i enkla fall och har ingen kryptografisk styrka . Ingår i standardbiblioteken för olika kompilatorer .

Beskrivning

Den linjära kongruentiella metoden föreslogs av D. G. Lehmer 1949. [1] Kärnan i metoden är att beräkna en sekvens av slumpmässiga tal , förutsatt

där  är modulen ( naturligt tal , i förhållande till vilket resten av divisionen beräknas ; ),  är multiplikatorn ( ),  är ökningen ( ),  är det initiala värdet ( ).

Denna sekvens kallas en linjär kongruent sekvens . Till exempel, för vi får sekvensen [2]

Egenskaper

En linjär kongruent sekvens definierad av siffrorna , och är periodisk med en period som inte överstiger . I det här fallet är längden på perioden lika om och endast om [3] :

  1. Tal och relativt primtal ;
  2. är en multipel av varje primtal som är en divisor av ;
  3. flera , om flera .

Förekomsten av denna egenskap för fallet , där  är antalet bitar i ett maskinord , bevisades av M. Greenberg . [4] Förekomsten av denna egendom för det allmänna fallet och villkorens tillräcklighet bevisades av TE Hull och AR Dobell . [5]   

Metoden att generera en linjär kongruent sekvens vid kallas den multiplikativa kongruenta metoden och vid den  blandade kongruenta metoden . Med kommer de genererade talen att ha en kortare period än med , men under vissa förhållanden kan du få en längdperiod , om  är ett primtal . Att tillståndet kan leda till uppkomsten av längre perioder fastställdes av W. E. Thomson ( eng. WT Thomson ) och oberoende av A. Rotenberg ( eng. A. Rotenberg ). [2] För att garantera maximal sekvensupprepningscykel vid , är det nödvändigt att välja ett primtal som parametervärde. Den mest kända generatorn av detta slag är den så kallade minimistandarden för slumptalsgenerator som föreslogs av Stephen Park och Keith Miller 1988 . För honom också . [6] [7]    

Den vanligaste metoden för att generera sekvenser av pseudoslumptal är den blandade kongruentiella metoden.

Vanligt använda parametrar

När du väljer ett nummer måste följande villkor beaktas:

1) antalet måste vara ganska stort, eftersom perioden inte kan ha fler element;

2) värdet på numret bör vara sådant att det kan beräknas snabbt.

I praktiken, när du implementerar metoden, baserat på de angivna villkoren, väljer du oftast , där  är antalet bitar i maskinordet . Samtidigt bör man ta hänsyn till att de minst signifikanta bitarna av de slumptal som genereras på detta sätt visar beteende som är långt ifrån slumpmässigt, så det rekommenderas att endast använda de mest signifikanta bitarna. Denna situation uppstår inte när , var  är längden på ett maskinord. I det här fallet beter sig de lägre bitarna lika slumpmässigt som de högre. [2] Valet av multiplikator och inkrement beror främst på behovet av att uppfylla villkoret för att uppnå den maximala längdperioden.

Tabell över goda konstanter för linjära kongruentialgeneratorer

Alla ovanstående konstanter säkerställer driften av generatorn med en maximal period. Tabellen är sorterad efter den största produkten som inte orsakar spill i ett ord av den angivna längden. [åtta]

Bräddar kl 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 312500
2 35 84589 45989 217728

Den "misslyckade" (när det gäller kvaliteten på utdatasekvensen) RANDU- algoritmen , som har använts i olika kompilatorer i många decennier, är ökänd.

För att förbättra de statistiska egenskaperna hos en talsekvens använder många pseudo-slumptalsgeneratorer endast en delmängd av resultatbitarna. Till exempel tillhandahåller ISO/IEC 9899 C-standarden (men anger inte som obligatorisk) ett exempel på en rand()-funktion som tvingar de låga 16s och en hög siffra att kasseras.

#define RAND_MAX 32767 static unsigned long int next = 1 ; int rand ( void ) { nästa = nästa * 1103515245 + 12345 ; return ( osignerad int )( nästa / 65536 ) % ( RAND_MAX + 1 ); } void srand ( osignerad int seed ) { nästa = frö ; }

Så här används rand()-funktionen i Watcom C/C++-kompilatorerna . De numeriska parametrarna för andra algoritmer som används i olika kompilatorer och bibliotek är kända.

Källa m faktor a term c bitar som används
Numeriska recept [9] 2 32 1664525 1013904223
Borland C/C++ 2 32 22695477 ett bitar 30..16 i rand() , 30..0 i lrand()
glibc (används av GCC ) [10] 2 31 1103515245 12345 bitar 30..0
ANSI C : Watcom , Digital Mars , CodeWarrior , IBM VisualAge C/C++ [11] 2 31 1103515245 12345 bitar 30...16
C99 , C11 : Förslag i ISO/IEC 9899 [12] 2 32 1103515245 12345 bitar 30...16
Borland Delphi , Virtual Pascal 2 32 134775813 ett bitar 63..32 av (seed * L)
Microsoft Visual/Quick C/C++ 2 32 214013 ( 343FD16 ) 2531011 (269EC3 16 ) bitar 30...16
Microsoft Visual Basic (6 och tidigare) [13] 2 24 1140671485 (43FD43FD 16 ) 12820163 (C39EC3 16 )
RtlUniform från Native API [14] 2 31 − 1 2147483629 (7FFFFFED 16 ) 2147483587 (7FFFFFC3 16 )
Apple CarbonLib , C++11 :s minstd_rand0[15] 2 31 − 1 16807 0 se MINSTD
C++11 :or minstd_rand[15] 2 31 − 1 48271 0 se MINSTD
MMIX av Donald Knuth 264 _ 6364136223846793005 1442695040888963407
Newlib 264 _ 6364136223846793005 ett bitar 63…32
VAX :s MTH$RANDOM , [16] gamla versioner av glibc 2 32 69069 ett
Java 248 _ 25214903917 elva bitar 47…16
Tidigare i många kompilatorer:
RANDU 2 31   65539 0

Möjlighet att använda i kryptografi

Även om den linjära kongruentialmetoden genererar en statistiskt bra pseudo-slumpmässig sekvens av tal, är den inte kryptografiskt säker. Generatorer baserade på den linjära kongruentiella metoden är förutsägbara, så de kan inte användas i kryptografi. Linjära kongruentialgeneratorer hackades först av Jim Reeds och senare av Joan Boyar. Hon lyckades också öppna kvadratiska och kubiska generatorer. Andra forskare har utökat Boyars idéer genom att utveckla sätt att bryta vilken polynomgenerator som helst. Således bevisades onödigheten av generatorer baserade på kongruenta metoder för kryptografi. Linjära kongruentialgeneratorer förblir dock användbara för icke-kryptografiska applikationer som simulering. De är effektiva och visar goda statistiska prestanda i de flesta empiriska tester som används [8] .

Se även

Anteckningar

  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, s. 141-146. MR 0044899 (13 495 f) [1] Arkiverad 24 december 2013 på Wayback Machine
  2. ↑ 1 2 3 Donald Knuth . Volym 2. Härledda metoder // Konsten att programmera. Dekret. op. - S. 21-37.
  3. ↑ D. E. Knut, Konsten att programmera. Volym 2. Härledda metoder - Williams. 2001. s.21-37
  4. ↑ M. Greenberger, Method in randomness, Comm. ACM 8 (1965), 177-179. [2] Arkiverad 24 december 2013 på Wayback Machine
  5. ↑ TE Hull och AR Dobell "Random Number Generators", SIAM Review 4-3(1962), 230-254 [3] Arkiverad 24 december 2013 på Wayback Machine
  6. ↑ "D.M. Bucknell. Grundläggande algoritmer och datastrukturer i Delphi. Programmers bibliotek. 2002. Delphi Informant Magazine. Kapitel 6.
  7. ↑ Stephen K. Park och Keith W. Miller (1988). Slumptalsgeneratorer: Bra är svåra att hitta. Communications of ACM 31 (10): 1192-1201 [4] Arkiverad 4 april 2019 på Wayback Machine
  8. ↑ 1 2 Bruce Schneier . Kapitel 16. // Tillämpad kryptografi. Triumph. 2002. Dekret. op. — S. 275. [5] Arkiverad 28 februari 2014 på Wayback Machine
  9. ↑ Numeriska recept i C. Konsten av vetenskaplig beräkning. 2:a upplagan. - Cambridge University Press, 1992. - 925 s.
  10. ↑ GNU C-bibliotekets rand() i stdlib.h använder en enkel (enkeltillstånd) linjär kongruentialgenerator endast om tillståndet deklareras som 8 byte. Om tillståndet är större (en array) blir generatorn en additiv återkopplingsgenerator och perioden ökar. Se den förenklade koden Arkiverad 2 februari 2015 på Wayback Machine som återger den slumpmässiga sekvensen från detta bibliotek.
  11. ↑ En samling utvalda pseudoslumptalsgeneratorer med linjära strukturer, K. Entacher, 1997 . Hämtad 16 juni 2012. Arkiverad från originalet 5 juni 2013.
  12. ↑ Senaste offentliga kommittéutkast från 12 april 2011, sidan 346f . Hämtad 21 december 2014. Arkiverad från originalet 25 december 2021.
  13. ↑ Hur Visual Basic genererar pseudo-slumptal för RND-funktionen . Microsoft Support . Microsoft. Hämtad 17 juni 2011. Arkiverad från originalet 17 april 2011.
  14. ↑ Trots dokumentation på MSDN Arkiverad 8 mars 2016 på Wayback Machine , använder RtlUniform LCG, och inte Lehmers algoritm, är implementeringar före Windows Vista felaktiga, eftersom resultatet av multiplikationen skärs till 32 bitar, innan modulo tillämpas
  15. ↑ 12 ISO/IEC 14882 :2011 . ISO (2 september 2011). Hämtad 3 september 2011. Arkiverad från originalet 17 maj 2013.
  16. ↑ GNU Scientific Library: Andra slumptalsgeneratorer . Datum för åtkomst: 10 januari 2015. Arkiverad från originalet den 11 december 2014.

Litteratur

  • Donald E. Knuth . Kapitel 3. Slumptal // Konsten att programmera datorer. - 3:e uppl. - M. : Williams , 2000. - V. 2. Erhållna algoritmer. — 832 sid. - 7000 exemplar.  - ISBN 5-8459-0081-6 (ryska) ISBN 0-201-89684-2 (engelska).

Länkar