math - 有限体での乗法逆数の計算

Question

拡張ユークリッド アルゴリズム関数を作成しました

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

非ゼロの有限体要素a,b ∈ GF ( p ^m ) の場合、sa + tb = 1となるようにsとtを計算します。体の乗法逆数を計算するために使用できる方法はありますか? つまり、a ∈ GF( p ^m ) が与えられたとき、 ab = 1 ∈ GF( p ^m ) となるようにbを計算したいと考えています。xgcd

---

機能も実装しました

(+)       :: 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]/pp

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

---

余談ですが、私がこれを行う場合、おそらくIntegralHaskell のクラスの定義に基づいて構築し、新しいクラスを定義します。

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