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.

  • $\begingroup$ Do you know a factorization of $n$? Let's say $n = n_1 n_2 \cdots n_k$ with $n_1, \ldots, n_k$ pairwise coprime. If so you can multiply in parallel using the Chinese Remainder Theorem. $\endgroup$ – user40023 Oct 6 '15 at 17:10
  • $\begingroup$ @Fry Unfortunately, it's hard to find a factor of n. Moreover, even determining whether n is a prime or not is still a great task in my case. $\endgroup$ – Yijun Yuan Oct 6 '15 at 23:25
  • $\begingroup$ When you multiply two polynomials, you need to multiply every coefficient of the first factor with every coefficient of the second factor; as it does not matter in which order these products are computed, you can share these multiplication tasks among the processors your machine has. The addition step is maybe not so easy to parallelize, but it takes only a relatively small fraction of the total time. $\endgroup$ – Stefan Kohl Oct 7 '15 at 10:07

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.