Parallelizing GMP

Torbjorn Granlund tg at
Sat Oct 29 11:01:28 CEST 2011

Let me add some points to Marc's reply.

You're computing in a simple ring, making multiplies therein about the
same cost as multiplies in Z.  Can you factor the order of the ring?
Because if you can, it would be faster to compute in subrings and then
use CRT at the end to lift the result to the original ring.

This would not only be faster, it might also allow for straightforward
high-level parallelisation.  (To determine which subring operations to
combine on a processor is a binpacking problem, which is not
straightforward to solve optimally, of course.)

More information about the gmp-discuss mailing list