Re: [math-fun] random generators
From: Eugene Salamin <gene_salamin@yahoo.com> For cryptosecure, I don't see how you can do better than a physical noise or quantum source.? Why do computer science people so disdain physical RNG's; it is because they don't involve fun things like algorithm analysis?? This annoys me so much that I've made it into a litmus test.? When I pick up a book that discusses random number generation, I immediately look to see if physical RNG's are discussed, not necessarily praised, and if not, I ignore the entire book.
Now, there is a place for pseudo-RNG's, and that is if the same sequence of random numbers must be generated again since then the initial seed can represent the entire lengthy sequence.
--well, you've answered your own question. PRNGs are better than true-random in the sense you can re-run your program with exact same results, which is needed to be able to debug it. Also PRNGs are probably faster and also higher quality randomness (paradoxically) than true random RNGs in many cases, albeit by algorithms applied to true random bits they could be made excellent too. True random RNGs are essential for cryptographic purposes, i.e. generating something secret. A way I invented a long time ago to generate true random bits, is this. Let F(x) be a continuous function of x with |slope|=2, which maps some real interval to itself, for example if |x|<1 then F(x)=2+2x for -1<x<-1/2, -2x for |x|<1/2, 2-2x for 1/2<x<1. Build an analog circuit to compute F(x) on some voltage interval. (A circuit made of ideal op-amps and ideal diodes can do that.) Use it cyclically to compute x0=x, x1=F(x), x2=F(F(x)), x3=F(F(F(x))), etc forever. Each new analog value will contain 1 new bit of randomness. If we output the sequence sign(x_k) of bits, they will be random bits. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
Warren, your analog RNG ultimately depends on amplified noise, so yes indeed it is a TRNG. We do agree on TRNG for cryto. Here is my design. Use an LED and two photodetectors. For each photon detected by one detector, output a 0 into a shift register, and output a 1 for each detection by the second detector. This could be implemented in digital hardware and should be able to generate at least a few megabits per second. I'd use a UV LED for high energy (3 eV) photons. A 1 microwatt LED at 400 nm provides 10^12 photons per second, so plenty of available bandwidth. -- Gene From: Warren D Smith <warren.wds@gmail.com> To: math-fun@mailman.xmission.com Sent: Saturday, March 19, 2016 2:18 PM Subject: Re: [math-fun] random generators
From: Eugene Salamin <gene_salamin@yahoo.com> For cryptosecure, I don't see how you can do better than a physical noise or quantum source.? Why do computer science people so disdain physical RNG's; it is because they don't involve fun things like algorithm analysis?? This annoys me so much that I've made it into a litmus test.? When I pick up a book that discusses random number generation, I immediately look to see if physical RNG's are discussed, not necessarily praised, and if not, I ignore the entire book.
Now, there is a place for pseudo-RNG's, and that is if the same sequence of random numbers must be generated again since then the initial seed can represent the entire lengthy sequence.
--well, you've answered your own question. PRNGs are better than true-random in the sense you can re-run your program with exact same results, which is needed to be able to debug it. Also PRNGs are probably faster and also higher quality randomness (paradoxically) than true random RNGs in many cases, albeit by algorithms applied to true random bits they could be made excellent too. True random RNGs are essential for cryptographic purposes, i.e. generating something secret. A way I invented a long time ago to generate true random bits, is this. Let F(x) be a continuous function of x with |slope|=2, which maps some real interval to itself, for example if |x|<1 then F(x)=2+2x for -1<x<-1/2, -2x for |x|<1/2, 2-2x for 1/2<x<1. Build an analog circuit to compute F(x) on some voltage interval. (A circuit made of ideal op-amps and ideal diodes can do that.) Use it cyclically to compute x0=x, x1=F(x), x2=F(F(x)), x3=F(F(F(x))), etc forever. Each new analog value will contain 1 new bit of randomness. If we output the sequence sign(x_k) of bits, they will be random bits. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
Let F(x) be a continuous function of x with |slope|=2, which maps some real interval to itself, for example if |x|<1 then F(x)=2+2x for -1<x<-1/2, -2x for |x|<1/2, 2-2x for 1/2<x<1. Build an analog circuit to compute F(x) on some voltage interval. (A circuit made of ideal op-amps and ideal diodes can do that.)
--incidentally, let me pose this as a PUZZLE. Your task is to 1. invent a continuous function F(x) of this type, self-mapping the interval [-1,1]. Not necessarily the same as my example F(x). It must have |slope|>=2 everywhere. 2. Also, it should map an x that is uniform random on [-1,1] to another uniform. 3. design an analog circuit to compute F(x) using ideal op-amps, diodes, and resistors. 4. In such a way that your circuit is as simple & cheap and fast as possible. 5. Also, your F(x) should not have any "short orbits that pass thru corners." By "orbit" I mean starting from some x, if you iterate F, you after k iterations return to the starting point (that is the meaning of "length-k orbit") and by "orbit passing thru a corner" I mean, if the graph of F(x) has a corner at some value of x then the orbit of that particular x should be long (large number of iterations before pass thru either another or the same corner). This is necessary to avoid the problem that in the real world's graph of F(x) these corners will be rounded off a little, and then you could get an attracting orbit, which you do not want. You want all orbits to be repelling. This is a good optimal-design puzzle and it is not clear to me what the best possible answer is, although at one time I had a few candidates. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
participants (2)
-
Eugene Salamin -
Warren D Smith