# Why is a bit biased when generated from random $v \in Z_q$ for odd q?

I am not understanding the following from "Lattice Cryptography for the Internet" by C. Peikert (pages 10, 11):

When $q$ is odd, while it is possible to use the above methods to agree on a bit derived by rounding a uniform $v \in \mathbb{Z}_q$, the bit will be biased, and hence not wholly suitable as key material.

I don't understand the biased part and how it is related to $q$ being odd or even. Any help would be appreciated.

• I edited the title of your question to more closely reflect what the question is about. I hope this is fine. Oct 14, 2016 at 7:09
• @GuutBoy It is good. Thank you. Can you please edit the title of my other question as well (my english isn't good): crypto.stackexchange.com/questions/40668/… Oct 14, 2016 at 7:13

What Peikert is saying here is that you can generate a random bit $b$ by first picking a uniformly random number $v \in \mathbb{Z}_q$, and then setting $b = 0$ if $v \leq q/2$ and $b = 1$ if $v > q/2$.
However, when $q$ is odd there is one more number in $\mathbb{Z}_q$ that is smaller than $q/2$ than there numbers that are larger than $q/2$. I.e., the bit will be slightly biased towards zero.
Put in other words, the probability of $b=1$ will be $\frac{\lfloor q/2 \rfloor}{q}$ and the probability of $b=0$ will be $\frac{\lceil q/2 \rceil}{q} = \frac{\lfloor q/2 \rfloor + 1}{q}$.
Note: Actually, Peikert seems to be using a slightly different "rounding" method. But the same argument applies. You would have more numbers mapping $b$ to $0$ than $1$ (or the other way around).