Calculating multiplicative inverse in a finite field

Question

I've written an extended Euclidean algorithm function

xgcd :: FFElem -> FFElem -> (FFElem, FFElem)

that, for nonzero finite field elements a,b ∈ GF(p^m), calculates s and t such that sa + tb = 1. Is there a way I can use xgcd to calculate multiplicative inverses in the field? That is, given a ∈ GF(p^m), I want to calculate b such that ab = 1 ∈ GF(p^m).

---

I've also implemented the functions

(+)       :: FFElem -> FFElem -> FFElem
(-)       :: FFElem -> FFElem -> FFElem
(*)       :: FFElem -> FFElem -> FFElem
(^)       :: FFElem -> Integer -> FFElem
ffQuotRem :: FFElem -> FFElem -> (FFElem, FFElem)
degree    :: FFElem -> Integer

Where (+), (-), (*), (^), and ffQuotRem behave as you would expect and degree is the usual Euclidean function for finite fields (the degree of the polynomial representation of the field element).

(Answers don't necessarily need to be in Haskell.)

Answer 1

Here are some steps toward an answer. First, consider the ring Z/nZ which is a field if n is prime. We can give a simple routine to compute the multiplicative inverse of an element a

-- | Compute the inverse of a in the field Z/nZ.
inverse' a n = let (s, t) = xgcd n a
                   r      = s * n + t * a
                in if r > 1
                    then Nothing
                    else Just (if t < 0 then t + n else t)

Its type is inverse :: Integral a => a -> a -> Maybe a because it allows for non-prime n, when the multiplicative inverse does not exist.

If a field is not a prime field, then it is a field extension of a prime field K = Z/nZ for some prime n, and is isomorphic to K[x]/p for some polynomial p. In particular, we require that there is a function

degree :: Polynomial -> Integer

that tells us the degree of a polynomial, and a partial function

project :: Integral a => Polynomial -> Maybe a

that projects a polynomial of degree 0 down to its underlying field in the obvious way. So if you know n and p, then

-- |Compute the inverse of a in the finite field K[x]/p with K=Z/nZ
inverse a (n, p) = let (s, t) = xgcd p a
                       r      = s * p + t * a
                    in if degree r > 0
                         then Nothing
                         else let Just r' = inverse' (project r) n
                               in Just $ r' * t

---

As an aside, if I were doing this, I would probably build on the definition of the Integral class in Haskell, and define a new class

class Integral a => FiniteField a where
    degree  :: a -> Integer
    xgcd    :: a -> a -> (a, a)
    inverse :: a -> a

which would have some simple instances (prime fields, which can be represented with a data type like)

data PrimeField = PF { size :: Integer, element :: Integer }

and more complicated instances for non-prime finite fields, whose elements are polynomials, probably represented with a Map -

data NonPrimeField = NPF {
    prime     :: Integer
  , maxDegree :: Integer
  , element   :: Map Integer Integer
}

Answer 2

A more theoretical approach to augment Chris's awesome answer:

Given F = Z/(p), f and u in F[x], you can use the extended Euclidean algorithm to find v and w in F[x] such that

uv + fw = gcd(u, f)

Now, if f is irreducible and u is not divisible by f their greatest common divisor r = gcd(u,f) is a unit. That is, vu + wf = r, with r in F\{0}. From this equation you get the congruence:

uv = r (mod f)       <=>        uvr⁻¹ = 1 (mod f)

where r^-1 is the multiplicative inverse of r in F.

Therefore the multiplicative inverse of the congruence class of u is vr⁻¹ in F[x]/(f).