math - 计算有限域中的乘法逆元

Question

我写了一个extended Euclidean algorithm功能

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

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

<小时/>

我也实现了这些功能

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

其中 (+)、(-)、(*)、(^) 和 ffQuotRem 的行为符合您的预期，level 是通常的 Euclidean function对于有限域(域元素的多项式表示的次数)。

(答案不一定需要用 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，而乘法逆元则不允许存在。

如果一个域不是素域，那么它是某个素数n的素数域K = Z/nZ的域扩展，并且同构于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

<小时/>

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

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
}