1
$\begingroup$

Can True Randomness be achieved by composing prngs in different states and with different algorithmsv(e.g. have $n$ different composition algorithms, use a prng to select any permutation of them. A lot $(\sum_{i=1}^{n}{^nP_i})$ of permutations exist. Compose the algorithms selected using the permutation. Whenever a new number is generated in a sequence of random numbers the entire algorithm selection process is repeated, and new seeds assigned to all algorithms.

The final result with/from the different prngs will be supplied as output.

For every new number, a fresh seed is taken to the random selection algorithm(to choose the composition of the PRNGs), this should be the most complex PRNG and have as much entropy as possible.

The sequence works something like this. Each PRNG takes two parameters; a seed, and some previous value.

For the first PRNG selected for composition, a seed $s$ is provided, and another randomly generated seed is used to generate another number $c$(This will be done by a randomly selected PRNG not in the sequence. So in actuality, we'll have $n+2$ PRNG algorithms). Each PRNG generates its own random number $k$. By choosing a permutation of some predefined composition algorithms (Whether the random number is to be floating or not, will define available composition algorithms, e.g final value $v \mod max$ will be used to arrive at the random integer) $c$ is used to modify $k$, to generate some $c_i$ to pass to the next algorithm in the sequence. The final $c_n$ will be adjusted to be within range as the random number.

I cannot conceive how such a system may be feasibly 'deterministic'.

Because of this, the algorithm shouldn't be philosophically deterministic. The next number is NOT based on previous numbers.

Arbitrarily designing a PRNG 'algorithm' isn't difficult (slightly modifying an existing algorithm, using different seeds to choose from, generating more than one result and choosing from it, etc). I read a post online about the security flaws of using prngs. How they are ultimately deterministic.

Will such a prng be deterministic?
Will it be able to achieve 'true' randomness?
Assuming all the prng algorithms have the same 'degree' of randomness What is the minimum $n$ I should choose to make it non-feasibly deterministic? $\tag{*}$

My only worry now, is the computational expensiveness of such a model. It should have a worst case running time of $nf(n)$ where $f(n)$ is the worst case running time of the worst random algorithm. (Assuming PRNGS don't have their running time vary with their outputs) {Though the higher security, might be worth it}.

(*) Feasible deterministic, means that if all computers in the world were connected to make a super computer (assume this is possible and performance scales accordingly) this super computer will be able to 'crack' (be able to determine the next $k$ number(s) in line given an arbitrary list of generated numbers (from the same instance of this algorithm $n$ and arbitrary time $m$ s.
$n,m\colon n \ge m \gt 10^{10^{100}}$
$k$'s value is irrelevant. If it can crack the next 10, then given enough time, it'll crack the next 100.

True randomness, is defined as being non feasibly deterministic.

$\endgroup$
  • 2
    $\begingroup$ What is "true randomness"? Incidentally, remember Knuth's dictum: A PRNG chosen at random is not random. $\endgroup$ – Pseudonym Dec 22 '16 at 5:23
  • $\begingroup$ @Pseudonym Where may I see this dictum. True randomness is defined as being non-feasibly deterministic. May I see this dictum of Knuth's haven't come across it yet. $\endgroup$ – Tobi Alafin Dec 22 '16 at 5:35
  • $\begingroup$ It's in "The Art of Computer Programming", in the section on random-number generators. Don't have it at hand so I can't give you a page number. $\endgroup$ – Pseudonym Dec 22 '16 at 5:39
  • $\begingroup$ I have the pdf somewhere on my laptop. Volume 1 I assume? $\endgroup$ – Tobi Alafin Dec 22 '16 at 5:40
  • 2
    $\begingroup$ TAoCP Vol 2: Ch. 3 Random Numbers. "Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin." (attributed to J.v.Neumann) TAoCP contains an anecdote of such a combined generator hitting a fixed point (a short cycle with a different starting number) almost immediately ("Algorithm" K), to go on with the insight quoted by Pseudonym. $\endgroup$ – greybeard Dec 22 '16 at 9:19
6
$\begingroup$

There are two types of answers:

  • Practical: You are looking for good stream ciphers. Several exist, though we don't know for sure that they are secure.

  • Theoretical: You are looking for cyptographically secure PRNGs. There are several suspected constructions, but such objects are not known to exist; if P=NP, then they don't exist.

In both cases, there is quite a wide literature on the subject.

$\endgroup$
4
$\begingroup$

No deterministic algorithm can produce non-deterministic output (by definition). PRNGs are deterministic algorithms, so mixing them any complicated way still produces a deterministic result.

If you want the output to be "truly random" (have entropy), you will have to get the entropy from somewhere (and a deterministic algorithm cannot create entropy) and thus have a non-deterministic algorithm/system.

$\endgroup$

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.