Let p1,...pk be the k first prime numbers. Denote p1*...*pk by n. We want to find x mod n, for that asume we found x mod pi for i in {1,...,k} , then use CRT to observe x mod n. What is the lowest (known) computational time for that? Quite clear that you can do it in O((log(n))^2). But I was told that it can be done in less time (however, they could not refer me to a source with an explanation ..) Is it really possible to reduce the computational time and how? (Would love to have a source or explanation)
What is the complexity if we work in Z [x] (now the pi are polynomials and not prime numbers)? assume pi are polynomials of degree 1.