18
$\begingroup$

PRNGs (pseudorandom number generators) generally have a bit length for the binary numbers they generate (e.g. 32 bits, 64 bits). This is the universe of their possible numbers.

It seems that they typically cycle when they reach their 2^bitlen number.

Is there one that, before it cycles, will generate each possible number in its universe, exactly once, without repetition, for larger bitspaces (e.g. 64, 128, 256), without large memory requirements (such as storing numbers generated so far, or a shuffled list of future numbers).

Another way to put this: Is there an algorithm than exhaustively “traverses” or “visits” each binary number in a bitspace, exactly once, in a pseudorandom order? (with large bitspace and low memory usage, as above)

EDITS:

I now have the impression that, while PRNGs do typically eventually cycle (repeat their sequence), the point at which one cycles is specific to the algorithm, and is usually NOT after 2^bitlen numbers (where bitlen is the size in bits of their binary output). Please correct this if wrong.

I expect that a PRNG is still a PRNG if it generates a duplicate number (within its period, before it cycles), or if it never generates (within its period) some numbers that are possible in the bitspace of its output. I'm not looking for these kinds.

I'm looking for an algorithm that works as if it's just reading off N-bit binary numbers from a massive randomly-shuffled list of all N-bit binary numbers, but without the massive memory requirement of such a list.

I'm interested in algorithms meeting this criteria that are pseudorandom in a cryptographically-secure way, and also those not cryptographically-secure that are quicker or simpler.

$\endgroup$
9
  • 9
    $\begingroup$ "It seems that they typically cycle when they reach their 2^bitlen number" - that's almost never true in practice. The Mersenne twister with the most common parameters has a 32-bit output and a period of $2^{19937}-1$. The Microsoft C library's rand(), which is about the worst PRNG in common use, has a 15-bit output and a period of $2^{32}$. $\endgroup$
    – benrg
    Jul 19, 2022 at 20:21
  • 3
    $\begingroup$ @benrg I think "bitlen" in that sentence (but not in the first sentence) refers to the size of the state, not of the output. $\endgroup$
    – Thomas
    Jul 20, 2022 at 7:34
  • 5
    $\begingroup$ @Thomas To me it seems OP is confused and assumes that state size = output size. Also, it's not clear to me what they are asking about... Which real-world PRNGs fail the last paragraph question? I believe OP has just asked "do we really have real-world PRNGs?" and the answer is a resounding "yes, since decades"... Or Maybe Op has to clarify what would be the unusual property they are looking for... $\endgroup$
    – GACy20
    Jul 20, 2022 at 9:38
  • 11
    $\begingroup$ The sequence you describe does not meet the criteria of a general (pseudo) random number sequence though, where you expect doublets etc. It is more a shuffling algorithm for a large deck. $\endgroup$ Jul 20, 2022 at 10:18
  • 7
    $\begingroup$ If I understand the question correctly, a maximum-length LFSR (linear feedback shift register) has the desired property, except that a state of all-zeroes cannot be reached. This can be useful for exercising memory cells (e.g. cache lines) randomly and exhaustively, for example. Note that such an LFSR by itself does not make for a very good general purpose PRNG, but it can be part of a PRNG (e.g. in George Marsaglia's KISS PRNG). $\endgroup$
    – njuffa
    Jul 20, 2022 at 11:16

4 Answers 4

39
$\begingroup$

Sure. Pick a block cipher (i.e., pseudorandom permutation), $E_K$, and a random key for it, $K$. Let $x_i=E_K(i)$. Then this has the properties you are looking for.

Short explanation:

As the block cipher $E_K$ maps each n-bit value uniquely to another n-bit value, all the resulting values must be different for different input values. Effectively that means $E_K$ creates a permutation of n-bit values that can be varied by changing $K$.

$\endgroup$
5
  • 8
    $\begingroup$ Feistel networks also make excellent hash functions if you need them to be invertible. en.wikipedia.org/wiki/Feistel_cipher $\endgroup$
    – Pseudonym
    Jul 20, 2022 at 3:41
  • $\begingroup$ @D.W. Can you explain how to create or store the permutation without needing a lot of memory? $\endgroup$
    – U. Windl
    Jul 21, 2022 at 15:45
  • 1
    $\begingroup$ @U.Windl: You pick a specific block cipher, like AES, and a random key, K. The permutation itself is not stored, but you are using an algorithm to generate the permutation. As state, this only needs the key K and the counter value i. For example, if you choose AES-128, you have a 128-bit key K and 128-bit counter i, for 256 bits total. For AES-256, the key K is 256 bits and the counter i is still 128-bit, so the state is 384 bits total. $\endgroup$ Jul 21, 2022 at 15:52
  • 2
    $\begingroup$ @DietrichEpp Thanks, but that still sounds too abstract to me: How is it guaranteed that no number repeats in the permutation? Maybe I got it: The n-bit block-cipher uniquely maps an n-bit input to an n-bit output? $\endgroup$
    – U. Windl
    Jul 21, 2022 at 16:30
  • 7
    $\begingroup$ @U.Windl Exactly. It has to, otherwise the encryption wouldn't be reversible. See also D.W.'s pseudorandom permutation link. $\endgroup$
    – marcelm
    Jul 21, 2022 at 17:16
20
$\begingroup$

A linear-feedback shift register (LFSR) is a terrible PRNG(*), but (with correct selection of feedback taps) it seems to meet all your qualifications.

A LFSR can run extremely fast -- faster than standard natural binary counters.

Is there one that, before it cycles, will generate each possible number in its universe, exactly once, without repetition, for larger bitspaces (e.g. 64, 128, 256), without large memory requirements (such as storing numbers generated so far, or a shuffled list of future numbers).

With a proper selection of feedback taps, a standard n-bit LFSR produces a "maximum length sequence", producing 2^n-1 output values (all possible output values, except for the all-zeros value, without repetition until it cycles back to the first value). There are a variety of techniques for tweaking the system to add that one final value all-zeros, so it produces all possible n-bit values. The only memory required is the n-bit current state of the LFSR. (A little more memory may be required if you want it to halt after it's cycled through all 2^n-1 values without repetition).

For example (based on http://users.ece.cmu.edu/~koopman/lfsr/ ):

#include <stdint.h>
#include <inttypes.h>
// David Cary
uint64_t next_LFSR64(){
  static uint64_t i = UINT64_C(1); // or any other non-zero value
  #define feed (UINT64_C(800000000000000D)
  // a few other special values of feed will also produce MLS, including:
  // #define feed (UINT64_C(800000000000000E)
  // #define feed (UINT64_C(800000000000007A)

  if (i & 1)  { i = (i >> 1) ^ feed; }
  else        { i = (i >> 1);       }
  return i;
};

will produce a maximum-length sequence of all possible 64-bit values (except the 0 value) without repetition until it cycles back to the initial value.

In principle (from a table from Roy Ward and Tim Molteno), a feedback term of

const uint256_t feed =
    (UINT256_C(1)<<255) + 
    (UINT256_C(1)<<253) + 
    (UINT256_C(1)<<250) + 
    (UINT256_C(1)<<245); // warning: untested.
static uint256_t i = UINT256_C(1); // or any other non-zero value

would in theory produce all possible 256-bit values except all-zeros, but of course our Sun won't last that long.

(*) From a cryptographic point of view, we want random-number generators and PRNGs to generate numbers that are very difficult for any attacker to guess ahead of time, even if that attacker has seen the previous thousand or so output values of that generator. The Berlekamp-Massey algorithm makes it easy to guess the next output of a LFSR given practically no information about the size of the LFSR and surprisingly few output values of the LFSR. Fortunately for cryptographers, cryptographically strong PRNGs exist which are immune to the Berlekamp-Massey algorithm. For example, all good stream ciphers use cryptographically strong PRNGs.

$\endgroup$
13
  • 1
    $\begingroup$ Isn’t it common wisdom to never use PRNG’s for security purposes? $\endgroup$ Jul 20, 2022 at 21:48
  • 4
    $\begingroup$ @DanielWalker PRNGS are used in security all the time. There are cryptographic grade PRNGs which are "very difficult" to break. You definitely would not use a LSFR for security, though! $\endgroup$
    – Cort Ammon
    Jul 21, 2022 at 4:49
  • 1
    $\begingroup$ Yes, they're terrible PRNGs, but the question is actually looking for a terrible PRNG. Deck-shuffling without having a deck. $\endgroup$ Jul 21, 2022 at 15:50
  • 1
    $\begingroup$ lol "Warning: untested" - Testing may take longer than the lifetime of our Sun $\endgroup$
    – sehe
    Jul 22, 2022 at 13:59
  • 2
    $\begingroup$ @LorenPechtel just use the block cipher with counter, and when your counter flows over, pick a new key. $\endgroup$ Jul 22, 2022 at 19:38
11
$\begingroup$

The period of a PRNG is how many random numbers you can generate before the sequence starts to repeat. If you don't mind using lower-quality PRNG algorithms, some classic ones (which fell out of favour for good reason) have short periods; for example an LCG can be constructed with any period you want, even for non-power-of-2.


Good quality PRNGs have a period much larger than the bit-space of their output. (Their internal state is wider than one output.) e.g. at least a couple words for a 1-word output, like for fast modern PRNGs such as the xorshift family.

The Mersenne Twister (the usual recommendation for C++: std::mt19937) has a famously large amount of state to initialize and manage, giving it a period of 219937 − 1. A large period is not the only figure of merit for a PRNG, but a short period is a serious flaw. (https://prng.di.unimi.it/ discusses various factors of PRNG quality, and has a comparison table of periods and which statistical tests are passed/failed by various PRNGs.)

For a PRNG with n bits of internal state, the maximum possible period is 2n, iterating through every internal state once before repeating. If the output is the entire state, achieving that maximum-period goal would mean generating each number exactly once, which is your requirement. (And some constructions do, although an LFSR can't generate 0).

But then they'd generate each number again in the same order. More interesting would be a PRNG that could sample every integer in its output range without replacement, and then do it again in a different order, and not just from a different starting point. That's non-trivial.


There are multiple crusty old PRNG algorithms which used to be used to implement functions like C rand() or random() which can return their whole state, and have maximal periods for that state.

The linear congruential generator is probably the most famous, where seed = (seed * a + c) % m; / return seed;

Generating 0 .. m-1 in a pseudo-random order without replacement

Interestingly, an LCG can be constructed with period m for any m. In some cases the sequence isn't very random, e.g. having some obvious patterns in the way they traverse the numbers from 0..m-1, at least with the way I chose to select c and a that would ensure a period m

I used this once, when low-quality randomness was acceptable (because nearby integers often had different-enough effects). I just wanted some permutation of the numbers in a 0..n range for rearranging trees via subtree pruning-regrafting aka SPR, to search for a maximum-likelihood tree in phylogenetics. This was a half-finished library that I shared on Github (GPLv2) in case pieces of it were useful.

I don't know if there are better algorithms for doing this for a non-power-of-2 period; this is just what I came up with many years ago, in about 2006. Another option would be to do something with a period somewhat too long, and discard out-of-range samples. (That could allow avoiding very low-randomness LCGs; see the comments in the code about some bad cases, like when m has no repeated prime factors.)

I constructed an LCG with m = the desired period (and output range), and chose c and a in a way that created a maximal-period LCG for that modulus. Knuth's The Art of Computer Programming was a useful resource for this.

// GPLv2, copyright Peter Cordes, written in 2006-2007 at Dalhousie University
// while running the computers for the phylogenetics group (math/stats/biology)

struct lcg {
    unsigned int state;
    unsigned int a, c, m;
    unsigned int startstate;
};

int is_prime(int p);     // these do what the name implies
int next_prime (int i);  // see lcg.c on github for the implementation I copied


/******************** Linear Congruential Generator setup ************/
/* to generate all possible SPRs in a pseudo-random order, we generate
 * all the numbers between 0 and the number of possible SPRs once each
 * without repetition using an LCG of the form: x_n+1 = x_n*a + c mod m.
 */
/*
 * Knuth: TAOCP 3.2.1: ex 2: if a and m are relatively prime,
 * the number X_0 will always appear in the period.  (will return to start?)
 *
 *  3.2.1.2: Theorem A: An LCG will have period m iff:
 *   -  c is relatively prime to m
 *   -  b = a-1 is a multiple of p, for every prime p dividing m
 *   -  b is a multiple of 4, if m is a multiple of 4
 *
 *  3.2.1.3: ex 4:  m = 2**e >= 8  ->  maximum potency when a mod 8 = 5.
 *   small multipliers are to be avoided.
 *
 * Numerical recipies suggests c = a prime close to (1/2 - sqrt(3)/6)*m
 */

/* make up some parameters for an LCG that will have the maximum period
 * equal to the range, so every value is generated once.
 * When maxval doesn't have any repeated prime factors, a = m+1,
 * which is the same as a=1.  It's not exactly random, but it does still
 * mix up which SPRs are done.
 */

void findlcg(struct lcg *lcg_params, int maxval)
{
    unsigned int a, b, c, m = maxval;
    int i;

    primesetup (maxval+maxval/2);

    if (m<=6){ // will be either 6 or 2.  Just loop in order
        b=0;
        c=1;
    }else{
        int divlimit = m;
        b=1; // b must be a multiple of all of m's prime factors
        if (!(m%2)){
            b=2;
            while (divlimit%2 == 0) divlimit /= 2;
        }
        for (i=3 ; i <= divlimit ; i+=2){
            if (is_prime(i) && m%i == 0){
                b *= i;
                while (divlimit%i == 0) divlimit /= i;
            }
        }

        if (!(m%4)){    // if m is a mult of 4, b must be.
            while (b%4) b *= 2;
        }

        /* make sure a isn't too small */
        while (b<sqrtf(m)) b*=7;

        if (b == m) b=0;  // just give up and avoid overflow

// Numerical Recipies says there is "lore" behind this... :)
// TAOCP says it's useless unless the multiplier sucks (section 3.3.3, eq. 40)
// That would be us.
        c = next_prime(max(5, (0.5 - sqrtf(3)/6.0)*m - 2));
        while (m%c == 0) c = next_prime(c+1);
        // Luckily we don't have to test for c>m, because it doesn't
        // happen with any m<100, and there are enough primes later...
/* I've observed that when a == m, (e.g. a=13, c=13, m=72) you often get
 * two consecutive numbers...  Do something to avoid that if it's a problem */
    }

    a = b+1;

    unsigned long long l = (unsigned long long)a * m;
    if (l > ULONG_MAX){
        fprintf(stderr, "spr: chosen Linear Congruential Generator is bogus\n"
        "   x_n+1 = x_n*%u+%u mod %u\n"
        "   a*m > ULONG_MAX, so it would overflow :(\n", a, c, m);
    }

    lcg_params->a = a;
    lcg_params->c = c;
    lcg_params->m = m;
    lcg_params->startstate = UINT_MAX;
    lcg_params->state = rand() % m;    // Linux/glibc rand() is not terrible
}

The actual PRNG function.
I didn't bother with any tricks to speed up the %m part; this was good enough for a first version.

// startstate = UINT_MAX means we've just started
// UINT_MAX as a return value means we've looped.
unsigned int lcg(struct lcg *lcgp) {
    // use long just to avoid overflow on multiply
    unsigned long a = lcgp->a, c = lcgp->c, m = lcgp->m;
    unsigned long old = lcgp->state;

    if (lcgp->startstate == UINT_MAX)
        lcgp->startstate = old;
    else if (old == lcgp->startstate)
        return UINT_MAX;
    // will continue to return this until startstate is reset

    lcgp->state = (a*lcgp->state + c) % m;
    return old;
}

With m being a power of 2type_width, the modulo is just binary truncation an happens for free. But that results in the low bits of the value having a very short period, e.g. alternating odd/even for the low bit.

Some LCG implementations use a wider state, like 48-bit, and return the high 32 bits of that. So the lowest bit returned doesn't have that short-period problem. (But then you wouldn't have the period = 2output_width property you're looking for.)

$\endgroup$
1
  • 1
    $\begingroup$ If you don't restrict output size = state size, you can get your different cycle by using the block cipher in counter mode, and then switch the key (or just increment it) when the counter flows over. (You'll want to pick a block cipher with smaller block size than the ones usually used in cryptography so you can get to the end of the cycle in your lifetime.) $\endgroup$ Jul 22, 2022 at 19:43
4
$\begingroup$

What is your intended application?

Apart from PRNGs, there are also quasirandom sequence generators. They are (almost certainly) not cryptographically secure, but have other desirable properties. From mathworld:

A sequence of n-tuples that fills n-space more uniformly than uncorrelated random points, sometimes also called a low-discrepancy sequence. [...] useful in computational problems where numbers are computed on a grid, but it is not known in advance how fine the grid must be to obtain accurate results. Using a quasirandom sequence allows stopping at any point where convergence is observed, [...]

They are useful in numerical integration, for example.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.