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