4
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ Define "non-binary funtion"? $\endgroup$ – fkraiem May 4 '16 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$ – fkraiem May 4 '16 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 Frame May 4 '16 at 12:22
  • 1
    $\begingroup$ You just convert it to a binary string and run the test... $\endgroup$ – fkraiem May 4 '16 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$ – faith May 5 '16 at 8:58
1
$\begingroup$

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.

$\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.