计算有限域中的乘法逆

Question

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

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

的是,对于非零有限域的元素A,B ∈ GF(p ^米),计算小号和吨,使得SA + TB = 1 是否有一种方法可以使用xgcd在该领域来计算乘法逆？即,给定一个 ∈GF(p ^米),我要计算b,使得AB = 1∈GF(p ^米).

---

我也实现了这些功能

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

其中(+),(-),(*),(^),并ffQuotRem表现为你所期望的并且degree是通常的欧几里得功能的有限域(field元素的多项式表示的程度).

(答案不一定需要在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
}