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.)

What does your `xgcd` function compute? How do you define the greatest common divisor in a field, where every non-zero element divides every non-zero element? — Joni, Dec 09 '13 at 09:39
@Joni: I see what you mean now. That wasn't the normal definition of gcd. I updated the question to reflect that. — Snowball, Dec 09 '13 at 10:04
What does `xgcd` compute really? Given non-zero `a`, for every `t` in the field you can find `s = (1-tb)/a` that satisfies the equation, so `xgcd` is not well defined by that equation alone... — Joni, Dec 09 '13 at 10:47
@Joni: I really screwed up this question... Let F = Z/pZ, f(x) irreducible in F[x], and GF(p^m) = F[x]/(f(x)). My mistake was that `xgcd a b` actually runs in F[x], not F[x]/(f(x)). That is, it calculates s and t **in F[x]** such that sa' + tb' = gcd(a',b'), where a',b' are the least degree elements in the congruence classes *a,b*, respectively. I'll think it through more carefully and try to salvage the question in the next couple days. — Snowball, Dec 09 '13 at 11:25

Chris Taylor · Accepted Answer · 2013-12-09T10:14:06.680

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
}

Joni · Answer 2 · 2013-12-10T12:42:25.030

3

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).

edited Dec 10 '13 at 12:42

answered Dec 09 '13 at 11:42

Joni

108,737
14
143
193

I'm not convinced that this is correct. Even if the inputs `u` and `f` are coprime, the extended Euclidean algorithm is only guaranteed to generate `v`, `w` such that `vu+wf=r` where `r` is a polynomial of degree `0` -- not necessarily the multiplicative unit. You must multiply `v` by `1/r` (considered as an element of `F`) in order to get the multiplicative inverse of `u`. See http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm – Chris Taylor Dec 09 '13 at 13:55
You are right Chris: GCD is unique up to multiplication by a unit, so `gcd(u,f)` can be any element in `F\{0}`. This has to be taken to account. – Joni Dec 10 '13 at 12:22

Calculating multiplicative inverse in a finite field

2 Answers2