Is there a parallel algorithm for doing modular multiplication of polynomials over Z/nZ? n is a very large number (for hundreds and thousands of bits).


Normally, the method used is binary exponentiation, but it's not a good idea for parallelization.



Parallel algorithm for modular multiplication of polynomials over Z/nZ
This problem is covered in great detail in Knuth's "The art of computer programming, volume II: Seminumerical algorithms". If the degree of the polynomials is $k$, then generalized Karatsuba schemes give the product of these polynomials in $O(k^{1+\varepsilon})$ multiplications modulo $n$, and these schemes parallelize very well, as each step splits the multiplication of two polynomials into several multiplications of polynomials of smaller degree.


