New Random Number Generator for encryption
in [Cryptography]
|
Prev: Scalable Key Cryptography - The Universal Model.
Next: New Generation Lossless Data Representations
From: jbriggs444 on 13 Aug 2010 08:46 On Aug 13, 8:29 am, jbriggs444 <jbriggs...(a)gmail.com> wrote: > On Aug 13, 4:27 am, orz <cdh...(a)gmail.com> wrote: > > > on topic again: > > > Is there any reason to have walls in the system instead of wrap around > > coordinates? > > If you have walls and corners, does that bias your results? > > Let's see... > > We are looking for 4-tuples with each element selected from > the set {-1, 0, 1} subject to the constraints that: > > 1. Not all elements can be zero > 2. The x element cannot be -1. > > There should be ( 81 - 27 ) / 2 such elements. We want to > ensure that the parity of these elements is evenly split between > even and odd. > > Ahah! An easy argument follows. We already know that the > three dimensional (3x3x3) hyper-plane right at the wall is not > evenly split with respect to parity. And we already know that > the full four dimensional (3x3x3x3) hyper-cube is evenly split. > And we can easily see that the two four-dimensional half-cubes > with the center plane excluded are mirror images of one > another and must neccessarily have an identical parity excess. > > It follows that eliminating one four-dimensional half-cube > at the walls will have the effect of inducing a parity bias > there. > > So yes, non-toroidal walls are a problem. Making this more concrete... You start with a 3x3x3x3 hyper-cube with the center cell eliminated. 40 of these cells have even parity and 40 have odd parity. The hyper-plane right at the wall is a 3x3x3 cube with the center cell eliminated. It has a 14 to 12 parity bias. Of the original 80 cells, 26 are in the "at-the-wall" cube. 27 more are on the far side of the wall and 27 more are on the near side of the wall. Both of these cubes have a 13 to 14 parity bias in the opposite direction of the central hyper-plane. 14 to 12 plus 13 to 14 = 27 to 26. So the walls of the four dimensional matrix naively induce a 27 to 26 bias in the random bits generated there. However, that analysis may indeed be quite naive. Unless I am mistaken, the likelihood of finding a particle adjacent to a wall is lower than the likelihood of finding it somewhere in the interior of the matrix. You can easily see this if you reduce things to one dimension and use a matrix that is three cells wide. You get an asymptotic density of (0.25, 0.50, 0.25). I'm just an untutored dweeb, but it seems you'd want some Markov analysis to come up with an asymptotic density for a walled four-dimensional space. Or just run a simulation and let a starting distribution relax through a couple of million iterations.
From: Lev Dymchenko on 13 Aug 2010 11:49 On Aug 13, 4:46 pm, jbriggs444 <jbriggs...(a)gmail.com> wrote: > On Aug 13, 8:29 am, jbriggs444 <jbriggs...(a)gmail.com> wrote: > > > > > > > On Aug 13, 4:27 am, orz <cdh...(a)gmail.com> wrote: > > > > on topic again: > > > > Is there any reason to have walls in the system instead of wrap around > > > coordinates? > > > If you have walls and corners, does that bias your results? > > > Let's see... > > > We are looking for 4-tuples with each element selected from > > the set {-1, 0, 1} subject to the constraints that: > > > 1. Not all elements can be zero > > 2. The x element cannot be -1. > > > There should be ( 81 - 27 ) / 2 such elements. We want to > > ensure that the parity of these elements is evenly split between > > even and odd. > > > Ahah! An easy argument follows. We already know that the > > three dimensional (3x3x3) hyper-plane right at the wall is not > > evenly split with respect to parity. And we already know that > > the full four dimensional (3x3x3x3) hyper-cube is evenly split. > > And we can easily see that the two four-dimensional half-cubes > > with the center plane excluded are mirror images of one > > another and must neccessarily have an identical parity excess. > > > It follows that eliminating one four-dimensional half-cube > > at the walls will have the effect of inducing a parity bias > > there. > > > So yes, non-toroidal walls are a problem. > > Making this more concrete... > > You start with a 3x3x3x3 hyper-cube with the center > cell eliminated. 40 of these cells have even parity and > 40 have odd parity. > > The hyper-plane right at the wall is a 3x3x3 cube with > the center cell eliminated. It has a 14 to 12 parity > bias. > > Of the original 80 cells, 26 are in the "at-the-wall" > cube. 27 more are on the far side of the wall and > 27 more are on the near side of the wall. > > Both of these cubes have a 13 to 14 parity bias > in the opposite direction of the central hyper-plane. > > 14 to 12 plus 13 to 14 = 27 to 26. > > So the walls of the four dimensional matrix > naively induce a 27 to 26 bias in the random bits > generated there. > > However, that analysis may indeed be quite naive. > Unless I am mistaken, the likelihood of finding > a particle adjacent to a wall is lower than the > likelihood of finding it somewhere in the interior of > the matrix. You can easily see this if you reduce > things to one dimension and use a matrix that is > three cells wide. You get an asymptotic density > of (0.25, 0.50, 0.25). > > I'm just an untutored dweeb, but it seems you'd want > some Markov analysis to come up with an asymptotic > density for a walled four-dimensional space. > > Or just run a simulation and let a starting distribution > relax through a couple of million iterations.- Hide quoted text - > > - Show quoted text - If we have cube size 4, most particles are near walls btw.
From: Cristiano on 13 Aug 2010 11:20 orz wrote: > I have not been very impressed with Diehard or the NIST stuff or RaBiGeTe > or ENT. As I told you, I got little feedback for RaBiGeTe. What should I do to get RaBiGeTe more "impressive"? Cristiano
From: Lev Dymchenko on 13 Aug 2010 13:32 On Aug 13, 7:20 pm, "Cristiano" <cristiaN...(a)gmail.com> wrote: > orz wrote: > > I have not been very impressed with Diehard or the NIST stuff or RaBiGeTe > > or ENT. > > As I told you, I got little feedback for RaBiGeTe. What should I do to get > RaBiGeTe more "impressive"? > > Cristiano I tested mdwp with RaBiGeTi, I have some small suggestions for the test.
From: orz on 13 Aug 2010 14:30
Cristiano, and anyone else interested in statistical tests for RNGs: I'd like to talk more about that, but don't really want to sidetrack this thread. I could email people individually, but I'd like a more public exchange where more people might join the conversation. So, I'm creating a new thread in sci.math with the title of "statistical tests for random number generators" and reply to that stuff there. I'll try to cross-post it to sci.crypt.random-numbers since that seems to be the only usenet group specific to RNGs, even if it is slightly offtopic for crypto stuff. |