# Approximate to the speed of Build-In functions

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.

-
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 '14 at 10:20
Extended GCD methods might be faster (and that might be what PowerMod us using anyway). – Daniel Lichtblau Dec 3 '14 at 0:43