Xorshift

Xorshift (även " skiftregistergeneratorer ") är en klass av pseudo-slumptalsgeneratorer som upptäckts av George Marsaglia [1] . Generatorer av denna typ är en delmängd av linjära återkopplingsskiftregister (LFSR), vilket gör att de kan implementeras effektivt utan överdriven användning av glesa polynom [2] . Generering av nästa nummer i sekvensen sker genom att upprepade gånger XORing det aktuella numret och dess bitskifte , vilket gör xorshift extremt snabbt på modern datorarkitektur. Som alla LFSRs kräver xorshifts noggrant urval av initiala parametrar för att erhålla längre periodiska sekvenser [3] .

Xorshift-generatorer är bland de snabbaste kryptografiskt svaga slumptalsgeneratorerna, och deras implementering involverar inte stora mängder kod eller ihållande systemtillstånd. Även om de inte klarar alla statistiska test av slumpmässighet i sin råa form, är denna brist välkänd och kan lätt korrigeras genom att lägga till en icke-linjär funktion till deras struktur, vilket resulterar i generatorer som xorshift+ eller xorshift*. En C-implementering av xorshift+-generatorn som klarar alla tester i BigCrush-sviten (med en storleksordning färre fel än Mersenne Twist eller WELL ) kräver vanligtvis mindre än 10 cykler på x86 för att generera ett slumpmässigt tal på grund av instruktionspipelining [4] .

Scramblers, kända som + och *, är svaga i de låga bitarna [5] och är utformade för att generera flyttal, eftersom omvandling av ett slumpmässigt tal till ett reellt tal kastar bort de låga bitarna. I allmänhet tillåter scramblern ** (uttalas "starstar") att LFSR klarar tester på alla bitar.

Eftersom enkla xorshift-generatorer (utan ett icke-linjärt steg) misslyckas med flera statistiska test, anses de vara opålitliga [3] :360 .

Implementeringsexempel

Nedan är implementeringen av 128-bitarsversionen av xorshift i C . Ovanstående implementering lagrar fyra 32-bitars nummer som tillstånd och har en period på .

struktur xorshift128_state { uint32_t a , b , c , d ; }; /* Tillståndsmatrisen måste initieras för att inte bara vara noll */ uint32_t xorshift128 ( struct xorshift128_state * state ) { /* Algoritmen "xor128" från sid. 5 av Marsaglia, "Xorshift RNGs" */ uint32_t t = tillstånd -> d ; uint32_t const s = tillstånd -> a ; tillstånd -> d = tillstånd -> c ; tillstånd -> c = tillstånd -> b ; tillstånd -> b = s ; t ^= t << 11 ; t ^= t >> 8 ; returnera tillstånd -> a = t ^ s ^ ( s >> 19 ); }

Den här implementeringen klarar de hårda testerna , men klarar inte MatrixRank- och LinearComp-testerna från BigCrush-testsviten i TestU01- paketet .

Anteckningar

  1. ↑ Marsaglia, George (juli 2003). Xorshift RNGs. Journal of Statistical Software . 8 (14). DOI : 10.18637/jss.v008.i14 .
  2. ↑ Brent, Richard P. (augusti 2004). "Anmärkning om Marsaglias Xorshift slumptalsgeneratorer". Journal of Statistical Software . 11 (5). DOI : 10.18637/jss.v011.i05 .
  3. ↑ 1 2 Panneton, Francois; L'Ecuyer, Pierre (oktober 2005). "På xorshift slumptalsgeneratorerna" (PDF) . ACM-transaktioner på modellering och datorsimulering . 15 (4): 346-361. DOI : 10.1145/1113316.1113319 . S2CID  11136098 . Arkiverad (PDF) från originalet 2021-01-26 . Hämtad 2021-01-10 . Utfasad parameter används |deadlink=( hjälp )
  4. ↑ Vigna, Sebastiano xorshift*/xorshift+ generatorer och PRNG shootout . Hämtad 25 oktober 2014. Arkiverad från originalet 4 augusti 2019.
  5. ↑ Lemire, Daniel; O'Neill, Melissa E. (april 2019). "Xorshift1024*, Xorshift1024+, Xorshift128+ och Xoroshiro128+ misslyckas med statistiska tester för linjäritet." Beräknings- och tillämpad matematik . 350 :139-142. arXiv : 1810.05313 . DOI : 10.1016/j.cam.2018.10.019 . S2CID  52983294 . Vi rapporterar att dessa förvrängda generatorer systematiskt misslyckas med Big Crush - särskilt de linjära komplexitets- och matrisrankningstesterna som detekterar linjäritet - när de tar de 32 lägsta ordningens bitar i omvänd ordning från varje 64-bitars ord.