Is there a pratical application to PRNG that generates a sequence which is not a binary one? A ternary, quaternary sequence, for instance. If so, how can we test this? Is there any alternative test suite, like NIST test suite in order to test the randomness for non-binary sequences? For example, what if I generate a sequence in modulo 255 and then use it to encrypt an image in one-time pad manner via adding the values of pixels by the generated sequence in modulo 255 ?
14
-
$\begingroup$ Define "non-binary funtion"? $\endgroup$– fkraiemMay 4, 2016 at 9:07
-
5$\begingroup$ This does not matter because a n-ary sequence can be represented as a binary one with only polynomial overhead. $\endgroup$– fkraiemMay 4, 2016 at 10:00
-
2$\begingroup$ @fkraiem I think the point is per the test, not how the output can be represented. Since the algorithm may naturally output data in a base that is not 2, a statistical test should be relevant to that particular base, as well as to bitstreams. Ent for example only tests bits and bytes, not arbitrary n-ary sequences $\endgroup$– Richie FrameMay 4, 2016 at 12:22
-
1$\begingroup$ You just convert it to a binary string and run the test... $\endgroup$– fkraiemMay 4, 2016 at 13:53
-
2$\begingroup$ @fkraiem Well, I have some doubt about it. Consider a base, not a power of 2, say 3. The appropriate way representing $0,1,2$ is $00,10,11$ for the sake of respecting the frequency of zeros and ones. However, if we take all $2-$tuples in base 3 and covert them to binary we have $0000,0010,0011,1000,1010,1011,1100,1110,1111$. Isn't it a handicap that absence of some binary $4-$tuples ? $\endgroup$– faithMay 5, 2016 at 8:58
|
Show 9 more comments
1 Answer
$\begingroup$
$\endgroup$
Randomness testing uses asymptotic properties. Thus, as the length of your input increases the effect you are concerned about will disappear.
Specifically, there is no need to convert ternary $1$ or $2-$tuples to binary. If you let $n$ increase you cover the interval $\{0,1,\ldots,3^n-1\}$ and then you convert these integers to binary, paying at most a 1 trit (Shannon's term for entropy in base 3) penalty in entropy. Since a decent ternary source should yield not much less than $$\left(\frac{\log 3}{\log 2}\right)n$$ bits or $n$ trits of entropy, there is nothing to worry about.
