Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

3 Answers 3

up vote 6 down vote accepted

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}.$$

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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