Mathematica Stack Exchange is a question and answer site for users of Mathematica. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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).






]   /;(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
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

Your Answer


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

Browse other questions tagged or ask your own question.