0
$\begingroup$

Let us define a one-to-one function $f$ that maps binary strings of length $n$ to ternary strings of length $n$ such that if $x$ is random then $f(x)$ must be random. My question

Is there an algorithm that computes such function?

  • 0
    What about $f(x) = x$? I guess I must be missing something...2011-02-28
  • 0
    I guess identity function is excluded. $x \in \{0,1\}^*$ while $f(x) \in \{0,1,2\}^*$2011-02-28
  • 0
    @turk: Don't you mean $x \in \{0,1\}^n$?2011-02-28
  • 1
    "one-to-one" means injective, right? because there are no surjections from binary strings of length $n$ to ternary strings of length $n$.2011-02-28
  • 1
    What is a random string?2011-02-28
  • 0
    @Moron: if f(x)=x, there will be no 2's in f(x), so it won't look random.2011-02-28
  • 0
    @Ross: Well, if $x$ can be considered random... Of course, as Qiaochu asked, what does random really mean here?2011-02-28
  • 0
    @Moron: I was thinking in terms of compressible-is there a (much) shorter description. And if you know there are no 2's, you can save a factor of $\log_2(3)$2011-02-28
  • 2
    @Ross: I was thinking about 'unpredictable'. But that is not too rigorous. Of course, OP should ideally tell us...2011-02-28
  • 0
    @Moron: agreed on OP should answer. "Random" is not well-defined.2011-02-28
  • 0
    @Ross, I guess you can assume that random means incompressible strings (using Kolmogorov Complexity).2011-02-28
  • 0
    @turkistany: that is the sense of my answer. If somebody knows the algorithm, they will know the range of $f(x)$ otherwise they will have to look at the output and it may look random.2011-02-28
  • 0
    @Ross, Do you have a concrete algorithm that would compute $f$?2011-02-28
  • 0
    No, but there are many. You could feed your $x$ as a seed (maybe broken into pieces) to your favorite random number generator or encryption algorithm.2011-02-28

2 Answers 2

2

If the person reading the ternary string knows your algorithm, then s/he will know that $f(x)$ is not random. There are $2^n$ binary strings of length $n$, so it takes $n$ bits to select one. But there are $3^n$ ternary strings of length $n$, so it takes $n\log_2 (3)$ bits to select one. Your $f(x)$ can only have a range of $2^n$ strings, not $3^n$. However, to somebody who doesn't know your algorithm, the output can look random.

0

Continuing Ross's answer, the correct way is to take $n$ bit binary numbers to $\lfloor (\log_3 2) n \rfloor$ ternary numbers. If you choose such an $n$ so that $(\log_3) 2 n$ is close to an integer, this will be "relatively random" How close to an integer can $(\log_3 2) n$ be? Dirichlet's theorem tells us that the error can be roughly $1/n$ (this is optimal by Roth's theorem), and so letting $m = \lfloor (\log_3 2) n \rfloor$, the range of your function will be $$3^{m-\Theta(1/m)} = 3^{-\Theta(1/m)} 3^m.$$ As $m$ gets bigger, the range of the function becomes more and more closer to $3^m$, which makes it more and more difficult to break the function. You will need to look for that many numbers: $$ \frac{1}{1 - 3^{-\Theta(1/m)}} = \Theta(m). $$ In cryptography, when trying to break an $m$-digits generator, you can use polynomially many queries (in $m$). So in this sense, the function is not secure after all.