# Mapping between random strings?

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?

-
What about $f(x) = x$? I guess I must be missing something... – Aryabhata Feb 28 '11 at 0:16
I guess identity function is excluded. $x \in \{0,1\}^*$ while $f(x) \in \{0,1,2\}^*$ – Mohammad Al-Turkistany Feb 28 '11 at 0:23
"one-to-one" means injective, right? because there are no surjections from binary strings of length $n$ to ternary strings of length $n$. – lhf Feb 28 '11 at 1:30
What is a random string? – Qiaochu Yuan Feb 28 '11 at 2:38
@Ross: I was thinking about 'unpredictable'. But that is not too rigorous. Of course, OP should ideally tell us... – Aryabhata Feb 28 '11 at 3:53

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