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.

In Mathematica, there is a function PowerMod[a,b,m], which computes a^b mod m. I will concern only this case: b = -1, m is a power of a prime, say m = p^N. When b=-1, the result of PowerMod[a,-1,m] is the number a' such that a*a' = 1 mod m, i.e the inverse of a in mod m.

There is a standard way to compute this inverse (when m is a prime power), but I will just give the code. The idea is to use Newton's method (in p-adic sense).

pAdicInverse[n_Integer,p_Integer,N_Integer]:=Module[

{stepMax,a,a0,x},

stepMax=Floor[Log2[N]]+1;
a=Mod[n,p^N];
a0=Mod[a,p];
x=PowerMod[a,-1,p];

Do[x=Mod[x*(2-a*x),p^2^i],{i,1,stepMax}];

x=Mod[x,p^N]

]   /;(PrimeQ[p] && N>=1)

This gives the correct answer, but the build-in PowerMod[a,-1,p^N] is 15x faster than the above code.

I would like to know how to speed up it. I thought to use something like Nest or Fold, but I didn't figure it out. The reason is that: In each step of Do, it works with different modulo p^2^i. Of course I can do it use the same modulo p^N all the time, but it will be much slower, even if I use Nest.

This is not really important, but I wonder how to speed it.

share|improve this question
1  
You will most likely not be able to match a specialized built-in (which may e.g. be implemented in C). You can try to Compile your code to speed it up, if you want to spend time on that. –  Yves Klett Mar 12 at 10:20

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.