Rabin cryptosystem - How many solutions?

55 Views Asked by At

If in Rabin cryptosystem we have $n = p \cdot q$ where $p$ and $q$ is prime we have four solutions (roots) - exist four solution of $x^2 \equiv b \pmod{n}$.

However, when we have:

$n = p \cdot q \cdot r$

where $p$ and $q$ and $r$ is prime or:

$n = p \cdot q \cdot r \cdot z$

where $p$ and $q$ and $r$ and $z$ is prime

How much will we have solutions?

will they be $2^k$? where $k$ is the number of prime numbers?