10
$\begingroup$

How would you generate a list of distinct random strings, where all strings are alphanumeric and have a fixed length?

$\endgroup$
2
  • 1
    $\begingroup$ Welcome to Cryptography Stack Exchange. Sorry, your question is not clear. Do you want to know how to use the output of a random number generator to generate such a list? (Then this would be off-topic here, and might be better on Stack Overflow.) Or do you want to create a random number generator? (Then it still lacks information ... or it simply gets a list of known RNG algorithms, and list-questions are off-topic here.) $\endgroup$ Nov 30, 2011 at 19:55
  • $\begingroup$ Random string generation might provide some inspiration. $\endgroup$ Dec 4, 2011 at 16:23

3 Answers 3

13
$\begingroup$

There are three general solutions to the non-duplicate random number problem:

  • If you want a few numbers from a large range then pick one and reject it if it is a duplicate. If the range is large, then this won't cause too many repeated attempts.

  • If you want a lot of numbers from a small range, then set out all the numbers in an array and shuffle the array. The Fisher-Yates algorithm is standard for array shuffling. Take the random numbers in sequence from the shuffled array.

  • If you want a lot of numbers from a large range then use an appropriately sized encryption algorithm. E.g. for 64 bit numbers use DES and encrypt 0, 1, 2, 3, ... in sequence. The output is guaranteed unique because encryption is reversible. The Hasty Pudding Cipher can be set for any convenient range of numbers.

$\endgroup$
2
  • 2
    $\begingroup$ Note that the first two options can be truly random (if they're based on a truly random source); the last is only pseudo-random (at least once it gets past the key size of the cipher). $\endgroup$ Dec 2, 2011 at 17:08
  • 3
    $\begingroup$ Agreed, but for most uses pseudo-random is going to be sufficient. With a requirement for non-repetition, each successive use is 'less random' since it is being picked from a smaller pool. The last number picked has no randomness at all - it is fully determined by the preceding numbers. $\endgroup$
    – rossum
    Dec 5, 2011 at 12:22
7
$\begingroup$

We want a list of $n$ distinct random-like non-negative integers less than $m$, obviously with with $n \le m$.

One option is to build a cipher $C$ over the set of non-negative integers less than $m$; select a fixed random key $K$ for that cipher; and construct the desired list as $C_K(i)$ for $0 \le i \lt n$. The rationale is that a good cipher over a set, with a random key, is indistinguishable from a random permutation of this set.

If $m = 2^{128}$, a safe choice for the cipher is AES (with a key size of 128, 192 or 256 bit depending on the paranoia required security level). If $m = 2^{64}$, 3DES is fine (perhaps with the restriction $n \lt m-1$, if we could find an efficient way to predict the butlast two values from the previous $2^{64}-2$ and the fact that 3DES is an even permutation, which BTW is an interesting problem).

For other $m$, we can build a custom cipher. See John Black and Phillip Rogaway: Ciphers with Arbitrary Finite Domains; or, especially for moderate $m$ and $n$ approaching $m$, Louis Granboulan and Thomas Pornin: Perfect Block Ciphers With Small Blocks.

$\endgroup$
1
  • 3
    $\begingroup$ Additionally the newer paper about Thorpe shuffles by Morris, Rogaway and Stegers might be useful. $\endgroup$
    – j.p.
    Dec 2, 2011 at 9:30
6
$\begingroup$

To expand on rossum's answer:

The Fisher–Yates shuffle is actually quite a versatile algorithm. In particular, you can use it in "on-demand mode", where, whenever you need a new random number, you run one step of the algorithm (Durstenfeld version or equivalent) and output $a[i]$ (where $a$ is the array being shuffled and $i$ is the loop counter).

Also, with a sparse array, you can generate $n$ unique random numbers from any range using $\Theta(n)$ time and space (assuming that storing and retrieving an element takes $\mathrm O(1)$ time and space). Basically, you use the standard Fisher–Yates shuffle, but only physically store those elements of the array $a$ for which $a[i] \ne i$. (In on-demand mode, you also don't need to store the elements that have already been output, since the algorithm won't ever reuse them.)

The rejection technique also needs at least $\Theta(n)$ time and space (since the output values must be stored somehow to let them be rejected), so in that sense it's no better than the Fisher–Yates shuffle even for large domains; however, in some cases it might be simpler to implement. Note, though, that simple implementations using a flat array to store duplicates will usually end up needing $\Omega(n^2)$ time to generate $n$ values. In general, I wouldn't expect an efficient implementation of the rejection method to be significantly less complicated than a comparable implementation of the Fisher–Yates method.

The block cipher method needs only $O(1)$ storage, excluding the output, and may therefore be preferable in some cases. As Gordon Davisson notes in the comments, it cannot be used to generate truly random output — but then, the other methods are also most often used with only pseudorandom input, in which case they have no special advantage there.

Finally, of course, if your domain is large enough (as in larger than $kn^2/2$ possible values, where $n$ is the number of values you want to generate and $k$ is an arbitrary security parameter), you can just pick uniform random values from the domain without worrying about duplicates, knowing that the probability of a collision is less than $1/k$.

$\endgroup$

Your Answer

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

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