2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

How much will we have solutions?

Assuming:

  • $p, q, r, ..., z$ are distinct odd primes

  • $b$ is relatively prime to $n$

  • There exists at least one solution

Then, yes, there will be precisely $2^k$ solutions.

This is straight-forward to show; as we know there exists a solution $x_0$ such that $x_0^2 = b \pmod n$, then this implies that:

$$x_0^2 = b \pmod p$$

$$x_0^2 = b \pmod q$$

...

$$x_0^2 = b \pmod z$$

We know that the first equation has two solutions modulo $p$; $x_0$ and $-x_0$ (as $b$ is relatively prime to $p$, and hence $x_0 \ne 0 \pmod p$, and $p$ is odd, so $x_0 \ne -x_0 \pmod p$). We also know there cannot be a third (as that would imply a nontrivial factorization of $p$, contradicting the assumption that $p$ was prime).

Similarly, the rest of the equations have 2 solutions; hence using the Chinese Remainder Theorem, there are $2^k$ was to recombine these solutions into an $x$ value that satisfies all these equations (and hence the original one).

We can also show that any value of $x$ not in the set of $2^k$ will not satisfy one of the prime equivalences, and hence cannot satisfy the original, hence we have precisely $2^k$ solutions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.