3
$\begingroup$

For example, let's say I want two cryptographically strong RNGs (R1 and R2). And I want them to have the following property: R1 (resp. R2) will never generate the same random number twice. R1 (resp. R2) will never generate a random number that R2 (resp. R1) can generate.

Is it possible for three RNGs, 4, N ?

Unlike other questions already on the site, I don't need the generated RNGs to be tracked back to their generator.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ I don't think it is possible. But it is effectively achieved by generating large numbers (e.g. 128-bit or larger), having a large state space (i.e. >= 128-bit again) and using a TRNG to seed the state. Chances of you seeing repeat values in practice in such a setup may as well be zero. $\endgroup$
    – Neil Slater
    Oct 2, 2015 at 10:11
  • 3
    $\begingroup$ There have been several near duplicates asked recently. A quick search found these two. Does either answer your question? $\endgroup$
    – otus
    Oct 2, 2015 at 10:11
  • $\begingroup$ I can't see a difference with the second question pointed by otus. $\endgroup$
    – fgrieu ♦
    Oct 2, 2015 at 10:51
  • $\begingroup$ @otus no: I don't need the generated numbers to be tracked back to their generator. I just want the RNGs to not repeat themselves and to not collide with the others RNGs. $\endgroup$
    – daruma
    Oct 2, 2015 at 11:50
  • $\begingroup$ @UnixJunkie, is it a problem if they are? I.e. what additional requirements do you have that require a different answer? $\endgroup$
    – otus
    Oct 2, 2015 at 12:01

1 Answer 1

Reset to default
11
$\begingroup$

Take a block cipher with a random key and for one generator encrypt the even numbers then with the other generator encrypt the odd numbers. Your output blocks will be pseudo-random and distinct. For more than two generators just partition the inputs accordingly.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ Correct, but useless. Sadly, the question is generally useless. $\endgroup$
    – Joshua
    Oct 2, 2015 at 16:16
  • 1
    $\begingroup$ +1. Also, if you need the outputs to lie in a range that doesn't conveniently match the block size of any standard block cipher, you can use the usual FPE tricks to construct a cipher with a suitable range. $\endgroup$
    – Ilmari Karonen
    Oct 3, 2015 at 20:57
  • $\begingroup$ Is it possible to preserve non-overlappiness for small ranges? E.g. 2 seeded random number generators that, each, picks a different subset of numbers from 1 to 20? $\endgroup$
    – caveman
    Aug 19, 2021 at 9:51
  • $\begingroup$ That was what the FPE comment above sought to address. $\endgroup$
    – Thomas M. DuBuisson
    Aug 19, 2021 at 18:32
  • $\begingroup$ Does FPE require synchronisation of the generators? E.g. if we have 2 generators each generating a sequence 512 bit blocks off a unique key, then one method in that document is sorting those 512 values in order to reach a global agreement across the generators. This sorting needs synchronisation between the generators. Can we do it without such synchronisation? E.g. can we just initialise the generators differently at start, then somehow have the generators generate non-overlapping random numbers without the generators needing to talk to each other to reach a ordering agreement? $\endgroup$
    – caveman
    Aug 19, 2021 at 20:24

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.