Prove that Decision$-$LWE is as hard as Search$-$LWE. Specifically, show a $$divide$-$and$-$conquer$$ attack, where given an adversary who solves Decision$-$LWE, it is possible to guess the entries of s one by one. Recall that the modulus p is polynomial in the security parameter.

Hint: Consider guessing the value of the first entry of s$,$ denoted s$1$ in Zq and choosing a column vector a$$ in Z$\_$p$^$m uniformly at random. Given an LWE instance $($A$,$ u$),$ update the instance to $($A$,$ u $+$ s$1$ a$$ mod p$),$ where A$$ is the matrix A with column vector a$$ added to its first column.

What is the distribution of $($A$,$ u $+$ s$1$ a$$ mod p$)$ in case the guess for s$1$ is correct or incorrect?