So I'm taking my first abstract algebra class, and I have some homework like "Solve the equation $x^2 + [3]\times x+[2]=[0]$ in $\mathbb{Z}_6$. This doesn't seem to difficult to do since I can easily plug in all the congruent classes in $\mathbb{Z}_6$.
But then I have this one: Solve $x^3 + x^2 = [2]$ in $\mathbb{Z}_{10}$, and apparently it's a little bit tedious to go through all classes, but still doable.
But what if I need to solve it in $\mathbb{Z}_{7832}$ or $\mathbb{Z}_{2367283952}$?
There is an amazing trick called the Chinese Remainder Theorem. It lets you rewrite $\mathbb{Z}_{mn}$ as $\mathbb{Z}_m \times \mathbb{Z}_n$ as long as $m, n$ are coprime.
If $m, n$ are coprime, you can find integers $a,b$ such that $am+bn = 1$.
The mappings are $[k] \mapsto ([k],[k])$ and $([k],[l]) \mapsto [bk + al]$
Now you can solve a problem in $\mathbb{F}_{10}$ by solving it in $\mathbb{F}_5$ and $\mathbb{F}_2$, and then combining the solutions back to something in $\mathbb{F}_{10}$.
Assuming conversion is trivial, the speedup is obvious. You only have to evaluate your polynomial $m+n$ times, instead of $mn$ times.
Unfortunately, this doesn't help with large primes/large prime powers