Decrypting message as MSB in regev scheme I was watching this FHE video and it define Regev encryption scheme as fallow :
kyegen:

sk : choose $t = (1,s)^t \in \mathbb{Z}_q^{n+1}$
pk = $A \in \mathbb{Z}_q^{m*(n+1)}$ random except $[A * t]_q$  small

Enc: for random $r \in \{0,1\}^m $ output and $\mu \in\{0,1\}$

$c \leftarrow (\mu,0,...,0).\frac{q}{2} + r.A$

Dec : compute
$$\langle c,t\rangle =  \mu.\frac{q}{2} + r.A.t = \mu.\frac{q}{2} + \; small \; (mod \; q)$$

Decrypt $\mu$ as MSB$([\langle c,t \rangle]_q)$

But i can not understand how decryption works? what i think is  for example for $q = 8$ if $[\langle c,t \rangle]_q \in [2,6)$ message is 1 and if $[\langle c,t \rangle]_q \in [6,8) \cup [0,2)$ message is 0 (if absolute value of small in $\langle c,t\rangle$ be less thatn $q/4$). I cant understand how the message would be MSB$([\langle c,t \rangle]_q)$ ? for example if we use 3 bits for each number MSb of both 0 and 3 would be 0.
Edit
responding to @kelalaka answer. beside $q$ being odd which is important but not very much what made me confused at first place was this section of Regev's paper. I think what you said is true when &quot;small&quot; bounded like $0&lt;= small &lt; q/2$. for example for $q = 7$ we have something like
$$000\\001\\010\\\\011\\---------\\100\\101\\110$$
and what i said when $-q/4&lt;= small &lt; q/4$ and depends on error distribution you choose at first place. but still not sure.
Edit 2 : actually it was kinda a silly question. for future reference if somebody(with low probability) came across this question. Homomorphic Encryption is a good paper from SHai Halevi, the guy in the video. and at secction 2.1    Notations and Basic Definitions you can find definition of $[\;\;]_q$ and much more.
You have some errors on the definition of the Regev's Scheme

Keygen($1^n$):

sk : choose $t = (1,s)^t \in \mathbb{Z}_q^{n}$ where $q$ is an prime between $n^2$ and $2n^2$
pk = $B \in \mathbb{Z}_q^{m\times n}$ random except $[B \times t]_q$  &quot;small&quot;


$Encryption(B,\mu \in \{0,1\}$:  For random $r \in \{0,1\}^m $ output and $\mu \in\{0,1\}$
$$c \leftarrow (\mu,0,...,0) \cdot \frac{q}{2} + r \times B$$

$Decrypt(c,t)$ : Compute


$$\langle c,t\rangle =  \mu \cdot \frac{q}{2} + r \times B \times t = \mu \cdot \frac{q}{2} + \text{ "small"} \pmod q$$

Recover $\mu$ as MSB$([\langle c,t \rangle]_q)$

Details

the secret key is a $n$ dimensional vector in $\mathbb{Z}_q^{n}$ where the first component is $1$

The public key is a matrix except that when you multiply with the secret key $t$ you will have a vector in $q$ that hash small values $[B \times t]_q$

The random $r$ is a bit vector of size $m$, $r \in \{0, 1\}^m$.

The message It is a bit, yes you encrypt either $\mu \in \{0, 1\}$, and  for a vector of size $n$, $(\mu,0,...,0)$

Encryption :


$$c \leftarrow (\mu,0,...,0) \cdot \frac{q}{2} + r \times B$$

Decryption :

\begin{align}
\langle c,t\rangle &amp;= \langle (\mu,0,...,0) \cdot \frac{q}{2} + r \times B ,t\rangle\\
 &amp; = (\mu,0,...,0) \cdot \frac{q}{2} \times t + r \times B \times t \\
 &amp; = (\mu \cdot \frac{q}{2},0,...,0) \times t + r \times B \times t \\
 &amp; = \mu \cdot \frac{q}{2}+ r \times (B \times t)
\end{align}
remember $[B \times t]_q$  was chosen as &quot;small&quot; and  $r$  was a bit vector. If you consider the final integer in $\mod q$.
$$\mu \cdot \frac{q}{2} + \text{"small"}$$
The &quot;small&quot; in the beginning is adjusted so that $r \times B \times t$ never exceeds $q/2$.
Now, calling the MSB on the result will provide the $\mu$ since $\mu \cdot q/2$ makes the MSB 0 or 1 depending on the $\mu$.
Correctness
The small term is also called the error $e$ term. The correctness requires that $|e| &lt; \lfloor q/2 \rfloor /2 $

Note: I did not go to verify the example, since $q$ is so small to work. The bounds must be carefully controlled.
The below sageMath code is working, however, one needs to tune the &quot;small&quot;, that is left!

q = 129 # n^2 &lt; 129 &lt; 2n^2
R = IntegerModRing(q)
n = 10 # vector size
m = 10 # random vector size

def randSecretKey(R, size):
    v = vector(R,sample(range(q), size))
    v[0] =1
    return v

def randPublicKey(R,m,n):
    m2 = random_matrix(R,m,n)
    return m2

def randomBitVEctor(R,size):
    v = vector(R,[randint(0, 1) for i in range(size)])
    return v
    
def smallPKSK(R,m,n,sk,q):
    trials = 0
    small = false
    while not small:
        trials += 1
        inrange = true
        pk = randPublicKey(R,m,n)
        c = pk*sk
        for i in c:
            if i &gt; 50:
               inrange = false
        if inrange == true:
            print( &quot;number of =&quot;, trials)
            return pk

def encodeMessage(R,bit,m):
    mu = zero_vector(R,m)
    mu[0] = bit
    return mu

def encrypt(R, q, mu, r, B):

    return mu * R(64) + r * B

def decrypt(R, c, t):
    return c*t

sk = randSecretKey(R,n)
print(&quot;\nsecret key = &quot;, sk)

pk = smallPKSK(R,m,n,sk,q)
print(&quot;\nPublic key\n&quot;)
print(pk)

pk*sk

r = randomBitVEctor(R,n)
print( &quot;r = &quot; , r)

mu = encodeMessage(R,1,m)
print(&quot;mu = &quot;,mu)

c = encrypt(R, q, mu, r, pk)

print(&quot;ciphertext = &quot;,c)

p = decrypt(R, c, sk)

print(&quot;plaintext = &quot;,p)
Integer(p).digits(2)