r/RNG

LFSR based PRNGs are very widespread and fast, we all known xorshift, xoroshiro, etc. But its period verification usually requires its translation to some mathematical notation, computation of characteristic polynomials etc. So I've made a tool (a new lfsr battery for SmokeRand) that allows to make this work without an explicit usage of all that "clever formula", the detailed description is given here.

https://github.com/alvoskov/SmokeRand/blob/main/docs/lfsr.md

The entire idea is fairly simple:

• Restore the transition matrix by a direct manipulation of the LFSR state, so C code becomes a mathematical formula itself. So it mustn't contain counters, pointers, file descriptors etc. And only PRNG with state size of 32, 48, 64, 96, 128, 160, 192, 256, 320, 512 or 1024 bits.
• Verify if the period is maximal using the transition matrix.
• Restore the charateristic polynomial using Krylov matrix and Gaussian elimination, transform it into a jump polynomial. I've used S.Vigna jump functions to check myself here.

It also can be used for LFSR parameters search, I've used it to obtain two new 16-bit versions of xoroshiro (just for fun). That program also reproduces classic Marsaglia shifts triples for xorshift32/64:

https://github.com/alvoskov/SmokeRand/blob/main/apps/find_xorshift_params.c