2
$\begingroup$

How to compute multiplicative inverses for elements in any simple (not extended) finite field? I mean an algorithm which can be implemented in software.

3 Answers 3

6

The unit group of the finite field of order $q$ is a cyclic group of order $q-1.$ Thus, for any $a \in \mathbb{F}_q^{\times},$ $a^{-1} = a^{q-2}.$

4

In both cases one may employ the extended Euclidean algorithm to compute inverses. See here for an example. Alternatively, employ repeated squaring to compute $\rm\:a^{-1} = a^{q-2}\:$ for $\rm\:a \in \mathbb F_q^*\:,\:$ which is conveniently recalled by writing the exponent in binary Horner form. A useful reference is Knuth: TAoCP, vol 2: Seminumerical Algorithms.

2

If 'simple' means a prime field $\mathbf{Z}/p\mathbf{Z}$ to you, then, given an integer $x$ coprime to $p$, you simply need to find an integer $y$ such that $xy\equiv1\pmod{p}.$ Look up the paragraph of multiplicative inverses in the wikipedia page on Euclidean algorithm