2
$\begingroup$

Consider a prime finite field $\mathbb{F}_p$ of quite large characteristics $p$, for example $\log_2(p) \approx 256$ bits. I would like to know an approximate quantity of multiplications in $\mathbb{F}_p$ amounting the same bit complexity as one inversion in $\mathbb{F}_p$. Of course, this depends on many factors, hence I propose to listen your ideas rather than exact results. May be, is there an article or book, which discusses this topic?

$\endgroup$
2
$\begingroup$

The standard algorithm for inverting an element is using the extended Euclidean algorithm. You can read all about this connection on Wikipedia.

$\endgroup$
2
$\begingroup$

One algorithm to compute inverses in a finite field is to raise to a large power. In particular, $x^{-1} = x^{p-2}$ if you are working in $\mathbb{F}_p$ (by Fermat's little theorem). You can use standard algorithms for fast modular exponentiation to compute this with about $2 \lg p$ multiplications, or fewer (depending on the specific value of $p$ and the length of the shortest addition chain for $p-2$).

Another algorithm is to use the extended Euclidean algorithm, as Yuval Filmus explains. I'd expect this to be faster in most cases.

$\endgroup$
  • $\begingroup$ I know these methods, I would like to understand their algebraic complexity, i.e., amount of necessary multiplications in $\mathbb{F}_p$ for one inversion in $\mathbb{F}_p$. However, in books I saw only bit complexity. $\endgroup$ – Dima Koshelev Feb 23 '19 at 10:37
  • $\begingroup$ @DimaKoshelev, in general we ask you to tell us in the question what research you've done, what progress you've made, what solutions you've already considered and why you've rejected them -- precisely so we don't waste our time and your time by telling you things you already know of. If what you want to know is "what is the algebraic complexity of the extended Euclidean algorithm?", I suggest that you ask that separately, as a separate question -- but try to work it out first on your own, as the analysis of bit complexity should have all the ideas needed to analyze algebraic complexity. $\endgroup$ – D.W. Feb 23 '19 at 19:48

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.