Calculating multiplicative inverse in a finite field

abstract-algebra, cryptography, haskell, math

Solution

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
}

Problem

I've written an extended Euclidean algorithm function ``` xgcd :: FFElem -> FFElem -> (FFElem, FFElem) ``` that, for nonzero finite field elements a,b ∈ GF(pm), 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(pm), I want to calculate b such that ab = 1 ∈ GF(pm). 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.)

Original source