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$
$\endgroup$
3
-
$\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$– user40023Commented Oct 6, 2015 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 YuanCommented Oct 6, 2015 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 ♦Commented Oct 7, 2015 at 10:07
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Oct 8, 2015 at 16:46
Jan-Christoph Schlage-PuchtaJan-Christoph Schlage-Puchta
9,1772 gold badges30 silver badges56 bronze badges