Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
1  
"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
1  
What is a random string? –  Qiaochu Yuan Feb 28 '11 at 2:38
2  
@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
show 9 more comments

2 Answers

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.