Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $a ,$ $b ,$ $\alpha ,$ and $\beta$ be non-zero binary strings of length exactly $n$ where $$ \beta = a \alpha + b. $$

Now, consider the following scenario. Fix $a$ and $b.$ I give you $\alpha$ and $\beta,$ but keep $a$ and $b$ as secrets from you. What is the probability that you can modify both strings (same length, just alter some bits), such that the altered strings $\alpha'$ and $\beta'$ still satisfy $$ \beta' = a \alpha' + b. $$ A cryptography paper which I am reading mentions it is $2^{-n}$ but I couldn't convince myself why.

share|cite|improve this question
How many strings of length $n$ are there? How many pairs of strings of length $n$ are there? And from these, how many could satisfy a linear relationship? – Raskolnikov Mar 3 '11 at 20:23
'the probability that you can modify both strings'... Your question is not well formulated, pls revise it. – leonbloy Mar 3 '11 at 20:24
@leonbloy Sorry I'm an ESL speaker. I will revise it. – user2468 Mar 3 '11 at 21:18
@Raskolnikov There are $2^n$ different $\alpha$s and same number of $\beta$s. So, there are $2^{2n}$ different pairs $(\alpha',\beta')$. Now, I need to count how many of those $2^{2n}$ pairs satisfy the linear relation $\beta' = a \alpha' + b$. And the probability of choosing an element randomly from the $2^{2n}$ such that it satisfies the linear relation. Right? – user2468 Mar 3 '11 at 21:25
@M.S.: You got it! – Raskolnikov Mar 3 '11 at 21:26
up vote 0 down vote accepted

Answer was figured out in the comments by discussion with @Raskolnikov.

(Edit: It's better if a moderator can close the question.)

share|cite|improve this answer

Your Answer


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