3

I want a simple (non-cryptographic) random number generation algorithm where I can freely choose the period.

One candidate would be a special instance of LCG:

X(n+1) = (aX(n)+c) mod m (m,c relatively prime; (a-1) divisible by all prime factors of m and also divisible by 4 if m is).

This has period m and does not restrict possible values of m.

I intend to use this RNG to create a permutation of an array by generating indices into it. I tried the LCG and it might be OK. However, it may not be "random enough" in that distances between adjacent outputs have very few possible values (i.e, plotting x(n) vs n gives a wrapped line). The arrays I want to index into have some structure that has to do with this distance and I want to avoid potential issues with this.

Of course, I could use any good PRNG to shuffle (using e.g. Fisher–Yates) an array [1,..., m]. But I don't want to have to store this array of indices. Is there some way to capture the permuted indices directly in an algorithm?

I don't really mind the method ending up biased w.r.t choice of RNG seed. Only the period matters and the permuted sequence (for a given seed) being reasonably random.

Adomas Baliuka
  • 1,384
  • 2
  • 14
  • 29
  • 2
    https://en.wikipedia.org/wiki/Format-preserving_encryption – David Eisenstat Jan 27 '23 at 19:54
  • 1
    You might consider an [xorshift generator](https://en.wikipedia.org/wiki/Xorshift). You'll have to do a little reading (see the first reference for the original paper), but as I recall you can select the parameters to give whatever period you like. – Jim Mischel Jan 28 '23 at 05:04
  • 1
    Use any RNG with a seed, and reset the generator to the original seed when you reach the period? – Paul Hankin Jan 28 '23 at 12:19

1 Answers1

1

Encryption is a one-to-one operation. If you encrypt a range of numbers, you will get the same count of apparently random numbers back. In this case the period will be the size of the chosen range. So for a period of 20, encrypt the numbers 0..19.

If you want the output numbers to be in a specific range, then pick a block cipher with an appropriately sized block and use Format Preserving Encryption if needed, as @David Eisenstat suggests.

It is not difficult to set up a cipher with almost any reasonable block size, so long as it is an even number of bits, using the Feistel structure. If you don't require cryptographic security then four or six Feistel rounds should give you enough randomness.

Changing the encryption key will give you a different ordering of the numbers.

rossum
  • 15,344
  • 1
  • 24
  • 38
  • That sounds like an interesting idea but perhaps a slight overkill for my application, where I'm almost happy with the LCG already. Ideally, I'd like something "simple", for example, something that can be done in <200 lines of C code. I also want it to be fast. My block sizes can be ~10^6. Any suggestions for what ciphers I should look into? – Adomas Baliuka Jan 28 '23 at 01:15
  • 10^6 is just below 2^20 (1048576) so you need a 20-bit block size. [Hasty Pudding](https://en.wikipedia.org/wiki/Hasty_Pudding_cipher) cipher allows that, but can be difficult to track down; not many crypto libraries offer it. You can use any cipher, such as AES, along with format preservation to get the 128 bit AES output down to 20 bits. – rossum Jan 28 '23 at 08:51