How to compute multiplicative inverses for elements in any simple (not extended) finite field? I mean an algorithm which can be implemented in software.
2026-04-25 16:39:28.1777135168
On
On
Multiplicative inverses for elements in field
2.3k Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
3
There are 3 best solutions below
0
On
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
0
On
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.
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}.$$