Calculating multiplicative inverse in a finite field

Viewed 4417

I've written an extended Euclidean algorithm function

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

that, for nonzero finite field elements a,bGF(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.)

2 Answers
Related