# Fastest way to find modular multiplicative inverse

I am looking for a fast way to find the modular multiplicate inverse of an integer $a$ in mod $p$. I am mainly interested in $p=115792089210356248762697446949407573530086143415290314195533631308867097853951$, which is the prime used for the finite field over which the elliptic curve P-256 is defined by the NIST (https://www.nsa.gov/ia/_files/nist-routines.pdf).

Take for example $a=23212057121572626849771762094316348576132063248523924165380765792316089469237$. What is the fastest way to calculate $a^{-1}$ mod $p$? I am currently using the extended Euclidean algorithm, but it is quite slow. I need the speed, since it's an operation that I will need to use a lot for encryption.

A file of 1664 bytes for example, requires about 20000 uses of the extended Euclidean, which takes about 10 seconds on my computer, which is quite long to encrypt 1664 bytes.

The algorithm I'm using is the following (taken from "Guide to Elliptic Curve Cryptography":

• I don't know about relative speed, but finding the value of $a^{p-2}\pmod p$ provides this information. "Modular exponentiation" is the term for this approach. Jan 3, 2015 at 23:51
• @abiessu Calculating $a^{p-2}$ is slower than the extended Euclidean algorithm, since $p$ is so large. Jan 4, 2015 at 0:05
• The extended Euclidean algorithm should be blindingly fast (try Wolfram Alpha for example). Perhaps your implementation is faulty? Jan 4, 2015 at 0:37
• I am quite certain that my implementation works, since I copied it pretty much straight from a book on elliptic curve cryptography ("Guide to Elliptic Curve Cryptography") Jan 4, 2015 at 0:40
• I'm guessing you know you can keep remainders less than p/2 ?
– user645636
Feb 26, 2019 at 19:31

Euclidean division is usually fast enough for applications in cryptography. It is at most a $$\log$$ factor slower than multiplication, and there is probably no better way of calculating modular inverse.
However, if you do want to save the $$\log$$ factor, then in your specific case I would suggest using an "inversion-free" version of your algorithm.