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":

  • $\begingroup$ 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. $\endgroup$ – abiessu Jan 3 '15 at 23:51
  • $\begingroup$ @Amzoti What is HAC? $\endgroup$ – Dasherman Jan 4 '15 at 0:00
  • 1
    $\begingroup$ @abiessu Calculating $a^{p-2}$ is slower than the extended Euclidean algorithm, since $p$ is so large. $\endgroup$ – Dasherman Jan 4 '15 at 0:05
  • 4
    $\begingroup$ The extended Euclidean algorithm should be blindingly fast (try Wolfram Alpha for example). Perhaps your implementation is faulty? $\endgroup$ – Greg Martin Jan 4 '15 at 0:37
  • $\begingroup$ 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") $\endgroup$ – Dasherman Jan 4 '15 at 0:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.