How to compute modular reduction in CRT domain?

Question

I'm working with big integers using chinese remainder theorem (CRT). This way I can map some big integer in a set of small ones.

I have addition and multiplication simply applying it coefficient-wise. However, modular reduction doesn't work so simply.

What I want to do: Let $a$, $q$, $p$ integers and $ a > q > p$. I know $a \mod p$ and I know $q$ and $p$. How to compute $\left(a \mod q\right) \mod p$?

What I have tried:

$$a \mod q = a - \lfloor \frac{a}{q}\rfloor \cdot q$$

So, $$a \mod q \mod p = \left[ a \mod p - \left(\lfloor \frac{a}{q}\rfloor \mod p\right)\cdot \left(q \mod p\right)\right] \mod p.$$

I know $a\mod p$ and $q \mod p$ but I can't compute $\lfloor \frac{a}{q}\rfloor$ since I don't know a.

Question: How to compute $a \mod q \mod p$ only knowing $a \mod p$, $q$ and $p$?

Answer 1

You are on a fool's errand. Let $p = 5$ and $q = 2$. Now

$$6 \equiv 1 \mod 5 \qquad\text{and}\qquad 6 \equiv 0 \mod 2$$ and $$11 \equiv 1 \mod 5 \qquad\text{and}\qquad11 \equiv 1 \mod 2$$

Thus you see that knowing $a \mod p$ is not enough to determine $a \mod q$ or $ (a\mod q) \mod p$.

---

I apparently missed the $a > q > p$ condition. However, this is still not solvable. Letting $q = 5$ and $p = 2$, suppose we know that $a \equiv 1 \mod 2$. Some possibilities are

• $a = 1, \ a \equiv 1 \mod 5, \ (a \mod 5) \equiv 1 \mod 2$
• $a = 7, \ a \equiv 2 \mod 5, \ (a \mod 5) \equiv 0 \mod 2$

Thus neither $a \mod q$ nor $(a \mod q) \mod p$ are well-defined.