Very commonly we have a system as the one below, and if we know a and b, then we can easily use CRT to solve for c.
\begin{align} x &\equiv a \pmod p \\ x &\equiv b \pmod q \\ x &\equiv c \pmod{pq} \\ % &gcd(p, q) = 1 \end{align}
However, suppose we instead know a and c, but not b.
What is the arithmetic way to solve this without directly doing reduction mod q?
Is this possible to compute using just +,\ -,\ *, mod pq and mod p?
Clarification: I am interested in finding b in addition to x.
Answer
If you know c then you have
x=c+kpq
for some k\in\mathbb{Z} hence we also have
x\equiv c\mod{p}
x\equiv c\mod{q}
by taking the modulus of p or q on both sides of the above equality.
No comments:
Post a Comment