0
$\begingroup$

As far as I know PRGs get an input (seed) and generate a larger output value than the input. Therefore is it possible that some outputs will never be generated? based on the fact that input is smaller than the output.

$\endgroup$
4
  • $\begingroup$ You mean a larger output space? $\endgroup$
    – Paul Uszak
    Feb 22 at 17:16
  • $\begingroup$ @PaulUszak yes. $\endgroup$ Feb 22 at 17:25
  • 3
    $\begingroup$ There are numerous PRGs. The answer might differ depending on which ones. Many (most?) generators cycle through their state space, with the seed determining where on the cycle they start. This would effect how long you would need to wait to see a given output, but wouldn't effect which outputs you will see if you wait long enough. $\endgroup$ Feb 22 at 19:27
  • $\begingroup$ Is there research into the Twister? It's phenomenally complex and I can't pin down my feelings as to whether $2^{19937} − 1$ values can be output. $\endgroup$
    – Paul Uszak
    Feb 22 at 19:56
6
$\begingroup$

PRGs get an input (seed) and generates a larger output value than the input.

Indeed. The standard definition of a PRG makes it a deterministic polynomial-time algorithm with input a seed in $\{0,1\}^n$ and output in $\{0,1\}^{\ell(n)}$ with $\forall n, \ell(n)>n$; and an other characteristic (pseudorandomness).

is it possible that some outputs will never be generated?

It's not only possible, it's certain, for all $n$. To prove this, we only need to count the possible inputs: there are $2^n$; and the number of outputs: there are $2^{\ell(n)}$. The condition $\ell(n)>n\ge 0$ implies $2^{\ell(n)}>2^n$. And since the algorithm is deterministic, there can't be more possible outputs than possible inputs.


Is it guaranteed that all possible random numbers can be produced?

Also yes, but in another sense.

If we truncate the output into $\lfloor\ell(n)/k\rfloor$ bitstring of $k$ bits, then it becomes possible that each one of the $2^k$ potential output bitstrings of $k$ bits is reached for some input when $n$ grows high enough. In fact, pseudorandomness implies that holds¹. Every possible output of any fixed size $k$ bit is reached¹ for large‑enough $n$ and when we consider all the $2^n$ possible inputs.

Now we only need to choose $k$ such that all the random numbers thought are in $[0,2^k)$, and then all possible random numbers thought are¹ produced.


¹ except perhaps for vanishingly few $n$

$\endgroup$
2
  • 2
    $\begingroup$ A good answer, but it should be clarified that the “other characteristic” (pseudorandomness) implies that every $k$-bit string must appear$^1$ as a block of some output only for small $k=O(\log n)$, and not necessarily otherwise (e.g., $k=n/100$). For example, the $n$-bit all-zeros string might never appear in the PRG output (for $n$-bit input). $\endgroup$ Feb 23 at 12:49
  • 1
    $\begingroup$ @Chris Peikert: what you add is indeed useful. I'll leave it to your comment, for I have purposely avoided going to that level of detail while sticking to strictly true statement. Hence the carefully worded "Every possible output of any fixed size $k$ bit is reached¹ for large‑enough $n$", which is true, implied by pseudorandomness, less precise than your statement, but enough to answer the question. $\endgroup$
    – fgrieu
    Feb 23 at 13:23
0
$\begingroup$

Linear Congruential Generators

Let's start at the beginning: linear congruential generators1.

A linear congruential generator has the form: $X_{N+1} = aX_N + c \pmod m$

Let's also define $b = a - 1$.

A linear congruential generator that produces all outputs in its range is called (no big surprise) a full range generator.

A full range generator will produce all $m+1$ numbers from $0$ through $m$, just in some shuffled order. This is achieved if and only if the following requirements are met2:

  1. $c$ is relatively prime to $m$
  2. $b$ is a multiple of $p$ for every prime $p$ dividing $m$
  3. $b$ is a multiple of 4 if $m$ is a multiple of 4

Linear Feedback Shift Registers2

For an lfsr, we're normally dealing with taps. That is, we take certain bits from our shift register, combine them (usually via XOR, but sometimes XNOR) and that result takes the place of the bit vacated a shift. Those are normally treated as powers in a polynomial, so if we tapped (say) the 4th and 7th bits, we'd write that something like $X^7 + X^4$ + 1 (the 1 represents X0, the value previously in the zeroeth bit, where we're going to put the result). In this case, the minimum requirements that must be met to get a full-range lfsr are that:

  1. we must have an even number of taps, and
  2. the values of the taps must be setwise coprime.

Those are necessary but not sufficient conditions though, so if you want a full-range lfsr, there are numerous tables of polynomials that work for various sizes of shift register.

Block Cipher in Counter Mode

Finally, I'll cover one that actually is capable of being useful for a wide range of cryptographic applications, and has a pretty simple answer.

If a block cipher is secure, then running it in counter mode to get random numbers, is generally pretty secure as well.

At least in the typical case, we use some randomly chosen number as our key, then we generate consecutive numbers as input blocks, encrypt each, and the result is our random number.

To be functional as encryption, the result of encryption must be reversible, so each input block must result in a unique output block. If two or more inputs could produce the same output, we would no longer be able to decrypt a block of data to produce its input.

So, in this case every possible output will be produced if and only if the output block size equals the input block size.


  1. But keep in mind that LC generators are generally not suitable for most cryptographic uses, regardless of how large a period they may have. That's not to say every possible use of an LC generator an a cryptographic algorithm will make it insecure, but if the randomness directly affects security, an LC generator probably isn't a good choice.
  2. Pretty much the same as above: the output of an lfsr is generally predictable, so if your security relies on an unpredictable result, an lfsr is probably a poor choice.
  3. This is nearly a direct transcription of Knuth Volume II, Theorem A.
$\endgroup$
2
  • $\begingroup$ Well maybe for an LCG. But there are others, and you mention block doo-dahs. Their outputs collide at a 36% rate (it's a randomness thing). Surjective functions? So is your answer no? $\endgroup$
    – Paul Uszak
    Feb 22 at 22:58
  • $\begingroup$ @PaulUszak: If you mean: is there at least one PRNG that fails to produce at least one in-range output for at least one seed value, then the answer is clearly "yes". If you mean to ask something else, I think you'll need to clarify exactly what it is you want to know. $\endgroup$ Feb 23 at 1:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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