Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs
2 of 4
specified which algorithm of knuth
yberman
  • 268
  • 1
  • 7

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 < x < p$. I used Knuth's algorithm for calculating the Extended GCD, but I was wondering if there was a trick for making it run in constant time, within a word?

The trick I found online 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.

yberman
  • 268
  • 1
  • 7