Random for Everyone: A Chaotic Guide

**Disclaimer** This guide is neither theoretically nor practically comprehensive. It covers only a limited subset of non-crypto PRNG algorithms found in the wild (LCGs and \(\mathbb{F}_2\)-linears in particular) and is just a random (pun intended) collection of notes, thoughts, and observations.
It also assumes that you’re familiar with modular arithmetics and linear algebra basics.

• In Part 1, we’ll review the general structure of PRNGs and the properties they have.
• Part 2 will cover LCGs and their special cases and notable properties.
• Part 3 will focus on XorShift-like generators in particular and \(\mathbb{F}_2\)-linear in general.
• And finally, in Part 4, we’ll discuss how to extend LCGs to achieve arbitrarily large period and \(k\)-dimensional equidistribution.

In this guide, I will use the following sources:

• Hull, Dobell. “Random number generators” https://hdl.handle.net/1828/3142

• O’Neill. “PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation” https://api.semanticscholar.org/CorpusID:3489282

• Blackman, Vigna. “Scrambled Linear Pseudorandom Number Generators” https://doi.org/10.48550/arXiv.1805.01407

• Jenkins. “The testing and design of small state noncryptographic pseudorandom number generators” https://burtleburtle.net/bob/rand/talksmall.html

• Steele, Vigna. “LXM: better splittable pseudorandom number generators (and almost as fast)” https://doi.org/10.1145/3485525

• Steele, Lea, Flood. “Fast splittable pseudorandom number generators” https://api.semanticscholar.org/CorpusID:9250860

• Brown. “Random number generation with arbitrary strides” https://mcnp.lanl.gov/reference_collection.html#random_number_generation_and_random_sampling

• Et cetera. Wait for the end of thread for the full list.

#computerscience #random #prng #rng #algorithms

UPD: Forgot the pic

"Funds of every wallet created with the Trust Wallet browser extension could have been stolen without any user interaction"

https://blog.ledger.com/Funds-of-every-wallet-created-with-the-Trust-Wallet-browser-extension-could-have-been-stolen/

#security #infosec #prng #cryptocurrencies

That's interesting. Every time I ask Google's #bard for random whole numbers, it gives me sawtooth-like ramping patterns. This is a great example for a stochastic simulation/numerical methods course -- uniformity, but not independence (i.e., bad random number generator).
#GPT #bard #LLM #randomness #PRNG #RNG

Just started to compare pure-rand random number generators #prng with the ones coming within other #npm libraries and it is blazing fast 🤯 (guess what? it is now used by @fbjest🤫)

I've made a fast soft-saturated #Gaussian approximation #PRNG.

https://joelkp.frama.io/blog/ran-softsat-gauss.html

It's based on the Box-Muller transform, but changes it to:
1) Map each 32-bit integer input to two "independent" 32-bit uniform random numbers.
2) Use polynomials to transform those into the output, instead of sqrt(), log(), and sin() or cos().

For audio, when bounded amplitude is wanted, I think it's better than a real Gaussian PRNG. It's also in saugns v0.4.0 (https://sau.frama.io/language.html#rasg).

@SonarResearch Reminds me of a slightly different exploitable bug in #Gambio's password reset which I had discovered (probably not been the first one).

They used mt_srand with only 1000000 possible seeds based on time to generate the password reset token. Might have been possible to predict it based on time (did not work out so well) or brute-force it with educated guesses (noisy, slow), but the code did worse:

When sending the token it generated a captcha which was based on the same #PRNG sequence. Requesting the captcha manually, one could solve it offline to find the PRNG seed which was also used to generate the password reset token.

This wasn't the 90's, but I saw it still in use in 2020. Later versions fixed this in different ways, for example by using a stronger RNG without using a bad seed.

As if the Pokemon Scarlet and Violet mess couldn't get worse...

Online play (battle stadium) apparently gets seeded with the same PRNG seed.

Every match where the first move used has an accuracy stat ≤ 90% will always miss.

This was followed up by discovering that a Fake Out + Sheer Cold (a 30% accuracy move for a non-Ice type with guaranteed KO) combination will cause Sheer Cold to hit 100% of the time.

#Pokemon #PRNG #videogames

As if the Pokemon Scarlet and Violet mess couldn't get worse...

Online play (battle stadium) apparently gets seeded with the same PRNG seed.

Every match where the first move used has an accuracy stat ≤ 90% will always miss.

This was followed up by discovering that a Fake Out + Sheer Cold (a 30% accuracy move for a non-Ice type with guaranteed KO) combination will cause Sheer Cold to hit 100% of the time.

#Pokemon #PRNG #videogames

Challenge: Given a 33 bit shift register based random number generator, shifting 32 times to make a random integer, we observe that a given value will always appear twice in the sequence. Generally unevenly spaced. How to find a value which has the closest repeat?

We could run for 2^33 iterations and keep a record in a many gigabyte array, but I imagine there's a better way.

Boosts OK!

@ColinTheMathmo

#math #maths #polynomials #lfsr #prng #pseudorandom

#HowTo get #entropy for #PRNG #PseudoRandomNumberGeneration on old hardware? #nondeterministic #RetroComputing

My #Amiga #A500 running my software makes the same sounds in the same order when powered on, when I really want it to be different each time. I seed based on `time()` but either libc from VBCC does not support it or the machine has no battery-backed real time clock or both.

Maybe I could use a #ParallelPort #sampler cartridge and hope its noise floor isn't too good? Allocate memory without clearing and hash it before using it (would that survive a cold boot?).

Someone pointed me towards Halton sequences for low-discrepancy pseudo #random number generation. The difference compared to Burtle integer #hash independent uniform #PRNG is quite large, here is an image excerpt rendered with 64 samples, the top half uses independent uniform randoms and the bottom half low-discrepancy randoms.

https://en.wikipedia.org/wiki/Halton_sequence
http://www.burtleburtle.net/bob/hash/integer.html