Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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]}]; 
  Return[Output])

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

Update

(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}
share|improve this question
    
Why would you need to do this? Why is the built-in version unsuitable? –  J. M. Nov 22 '12 at 16:38
    
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. –  Mohsen Afshin Nov 22 '12 at 16:42
2  
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? –  Rojo Nov 22 '12 at 18:58
1  
Just use ParallelMap or ParallelTable to run PowerMod on your 100k numbers over all your cores. –  s0rce Nov 22 '12 at 19:10
1  
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... –  KennyColnago Nov 23 '12 at 0:23
show 7 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.