Can anyone help me?
Not a homework problem. Just trying to finish all the book problem in my spring break. This is from my abstract algebra/Number theory book.
Show that we can compute (a $mod n_1$,...,a $mod n_k)$in time $$O(len(n)^2)$$
where $$n = n_1 *,.......,*n_k$$
given:
$O$ of computing $q := ⌊a/n⌋ $ and $r = a\mod n $ is $O(len(q).len(n))$
$r$ can be written as $a-nq=r$
Book also vaguely says "time to compute q and r is rougly same as time to compute $n\times q$"
Thanks