Timeline for Parallel algorithm for modular multiplication of polynomials over Z/nZ
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 11, 2015 at 7:53 | vote | accept | Yijun Yuan | ||
| Oct 8, 2015 at 16:46 | answer | added | Jan-Christoph Schlage-Puchta | timeline score: 3 | |
| Oct 7, 2015 at 10:07 | comment | added | Stefan Kohl♦ | 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. | |
| Oct 6, 2015 at 23:25 | comment | added | Yijun Yuan | @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. | |
| Oct 6, 2015 at 17:10 | comment | added | user40023 | 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. | |
| Oct 6, 2015 at 15:40 | history | asked | Yijun Yuan | CC BY-SA 3.0 |