Get $a$ such that quadratic residue has a solution (Rabin) My task is to implement Rabin signature. I have trouble with choosing padding a such that
$$x^2 \equiv a \pmod n$$
has a solution.

In that context, $n=p\cdot q$ is composite, where $p$ and $q$ are prime numbers with $p\equiv3\pmod 4$ and $q\equiv3\pmod 4$.


How do I check if a solution exists?
Is there any formal way to find $a$?
The equation $a = x^2 \bmod N$ has at most $4$ solutions $x$.  

There are solutions if $a$ is a square modulo both $p$ and $q$.  This can be checked by computing the Legendre of symbol of $x$ modulo $p$ and modulo $q$. 

Assuming that the two Legendre symbols are +1, when $p \equiv 3 \pmod 4$, a square-root of $a$ modulo $p$ is given by $x_p = a^{(p+1)/4} \bmod p$; the other square-root modulo $p$ is given by $-x_p$; and simililarly modulo $q$.  The square-roots modulo $N$ are then obtained through Chinese remaindering (CRT): $x_1 = \mathrm{CRT}(x_p,x_q)$, $x_2 = \mathrm{CRT}(-x_p,x_q)$, $x_3 = \mathrm{CRT}(x_p,-x_q)$, $x_4 = \mathrm{CRT}(-x_p,-x_q)$. 

For example, suppose $p = 852151$ and $q = 376963$ (note that $p,q \equiv 3 \pmod 4$).  And so $N = pq = 321229397413$.  Let also $a = 187078154864$.  It is verified that the Legendre symbol of $a$ modulo $p$ is $+1$, and similarly modulo $q$.

From the previous formula, we obtain $x_p = 295070$ and $x_q = 21456$.  The four square roots of $a$ are then obtained through Chinese remaindering: $184209776740$, $156318284370$, $164911113043$, and $137019620673$.

Remark 1:  The Legendre symbol of $a$ modulo $p$ is given by $a^{(p-1)/2} \bmod p$.

Remark 2:  Given $x_p$ and $x_q$, $\mathrm{CRT}(x_p,x_q) = x_p + p[i_p(x_q - x_p)\bmod q]$ with $i_p = p^{q-2} \bmod q$.