Integers between 0 and a square-free number $r$ minus one can be represented by their value modulo each of $r$'s prime factors, according the Chinese remainder theorem.

Given a number represented like that, is there an efficient way to calculate its representation for $r^2$, that is, its remainder modulo each of $r$'s prime factors squared?

I can do this in $O(n^2)$, with $n$ being the number of primes factors (given that the primes are relatively small), by running Garner's algorithm, and calculating the resulting number directly modulo each of the factors squared. Is there a way to do that more efficiently?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.