# 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$.

1. How do I check if a solution exists?
2. 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$.

• Thank you. Especially for example - they are really difficult to find. Remark 1 - I suspected you are supposed to calculate Legendre symbol for both p and q but couldn't get a straight answer form google – t4u May 13 '16 at 7:55
• for: p=852149 and q=376949 ; p= 1( mod 4); q= 1 (mod 4); ; and not 3; – t4u May 17 '16 at 20:45

There is also a nice formula giving solutions for quadratic residues modulo $n$: $$x=a^{\frac{(p-1)(q-1)+4}{8}}\mod n.$$ As usual, it is sufficient to verify it modulo $p$ and modulo $q$ separately.