Is there anyway to parallelize the PowerMod function?

Here is my Left-To-Right modular exponentation:

AfshinPowerMod[a_, b_, m_] := (Output = 1; 
  Do[If[n == 1, Output = Mod[Output*Output*a, m], 
    Output = PowerMod[Output, 2, m]], {n, IntegerDigits[b, 2]}]; 

It computes roughly in the same time as original PowerMod for 10K digits numbers.


(Since for prime testing, 2 is the lowest base, I've used it for faster computation)

Timing Result (Mathematica 8):

In[1]:= Total[DigitCount[2^100000 + 1]]

Out[1]= 30103

In[2]:= AbsoluteTiming[AfshinPowerMod[2, 2^100000 + 1, 2^100000 + 1]]

Out[2]= {91.839778,}

In[3]:= AbsoluteTiming[PowerMod[2, 2^100000 + 1, 2^100000 + 1]]

Out[3]= {92.9851312,}

As per J.M. request for RandomPrime (Based on the generated random prime timing differs, but yet it is roughly as fast as PowerMod)

In[41]:= prime = RandomPrime[10^2000]

In[43]:= AbsoluteTiming[PowerMod[2, prime, prime]]

Out[43]= {0.1406312, 2}

In[42]:= AbsoluteTiming[AfshinPowerMod[2, prime, prime]]

Out[42]= {0.1562399, 2}
  • $\begingroup$ Why would you need to do this? Why is the built-in version unsuitable? $\endgroup$ – J. M.'s torpor Nov 22 '12 at 16:38
  • $\begingroup$ Time. It take hours to compute PowerMod for 100K numbers while my cores are idle. I know I can distribute multiple numbers to multiple cores but I want to split PowerMod for a single number to decrease computing time. $\endgroup$ – Mohsen Afshin Nov 22 '12 at 16:42
  • 2
    $\begingroup$ If it's a matter of speed when you have 100K numbers, why do you need to split each number into cores? Wouldn't be equally efficient to just distribute the 100K numbers among the kernels? $\endgroup$ – Rojo Nov 22 '12 at 18:58
  • 1
    $\begingroup$ Just use ParallelMap or ParallelTable to run PowerMod on your 100k numbers over all your cores. $\endgroup$ – s0rce Nov 22 '12 at 19:10
  • 1
    $\begingroup$ I cannot reproduce @Mohsen's statement that AfshinPowerMod "computes roughly in the same time as original PowerMod for 10K digits numbers." My timings have the built-in PowerMod orders of magnitude faster for input integers $a$ and $b$ tested with up to 25 thousand digits... $\endgroup$ – KennyColnago Nov 23 '12 at 0:23

Your Answer

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

Browse other questions tagged or ask your own question.