math - 在有限域中计算乘法逆

Question

我写了一个扩展的欧几里得算法函数

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

也就是说，对于非零有限域元素a,b ∈ GF ( p ^m )，计算s和t使得sa + tb = 1。有没有一种方法可以xgcd用来计算域中的乘法逆元？也就是说，给定a ∈ GF( p ^m )，我想计算b使得ab = 1 ∈ GF( p ^m )。

---

我也实现了功能

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

其中(+)、(-)、(*)、(^)和ffQuotRem的行为与您预期的一样，并且degree是有限域的常用欧几里得函数（域元素的多项式表示的次数）。

（答案不一定需要在 Haskell 中。）

Answer 1

以下是答案的一些步骤。首先，考虑如果是素数的环Z/nZ，它是一个域。n我们可以给出一个简单的例程来计算元素的乘法逆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)

它的类型是因为当乘法逆不存在时，inverse :: Integral a => a -> a -> Maybe a它允许非素数。n

如果一个域不是素数域，那么它是某个素数 的素数域的域扩展K = Z/nZ，n并且同构K[x]/p于某个多项式p。特别是，我们要求有一个函数

degree :: Polynomial -> Integer

它告诉我们多项式的次数和偏函数

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

以明显的方式将 0 次多项式向下投影到其基础场。所以如果你知道n和p，那么

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

---

顺便说一句，如果我这样做，我可能会建立Integral在 Haskell 中的类定义的基础上，并定义一个新类

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

这将有一些简单的实例（主要字段，可以用类似的数据类型表示）

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

以及更复杂的非素数有限域实例，其元素是多项式，可能用Map-

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

Answer 2