Constant time multiplicative inverse within a word I was playing with an algorithm which at one step, calculated $f(x) = x^{-1} \mod p$ for $0 &lt; x &lt; p = 2^{64}-59$ (note $p$ is a prime). I used Knuth's Vol 2 Algorithm X algorithm for calculating inverse modulo a prime, using the Extended GCD, but I was wondering if there was a way for making it run in constant time, within a word?

The trick I found online for producing constant time inverses used Montgomery Multiplication, and therefore wouldn't fit within a 64-bit word.

My objective is to write a 64-bit cipher which (is probably insecure, definitely slow, and) uses inversion for confusion and diffusion.

Edit: Specified $p = 2^{64}-59$, a prime.

Edit2: Specified the algorithm attributed to Knuth with link to page which has attribution.
You can compute $f(x) = x^{\phi(p)-1} \bmod p$ in constant time, using $O(\log p)$ constant time modular multiplies.  If $p$ is prime, this reduces to $f(x) = x^{p-2} \bmod p$

BTW: calling it 'Knuth's' algorithm is, in general, not very helpful; Knuth gives hundreds of different algorithms in 'The Art of Computer Programming'.  I assume you mean the Extended Euclidean algorithm?