Вычисление мультипликативного обратного в конечном поле

Я написал расширенную функцию евклидова алгоритма

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 обычная евклидова функция для конечных полей (степень полиномиального представления элемента поля).

(Ответы не обязательно должны быть в Хаскеле.)

Источник

2 ответа

Решение

Вот несколько шагов к ответу. Сначала рассмотрим кольцо 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
}
Источник

Более теоретический подход к дополнению потрясающего ответа Криса:

Учитывая F = Z/(p), f и u в F[x], вы можете использовать расширенный евклидов алгоритм для нахождения v и w в F[x], таких что

uv + fw = gcd(u, f)

Сейчас если f является неприводимым и u не делится на f их самый большой общий делитель r = gcd(u,f) это единица. То есть, vu + wf = rс г в F\{0}, Из этого уравнения вы получите конгруэнтность:

uv = r (mod f)       <=>        uvr⁻¹ = 1 (mod f)

где r-1 - мультипликативное обратное к r в F.

Поэтому мультипликативный обратный класс конгруэнции u является vr⁻¹ в F[x]/(f).

Источник
Другие вопросы по тегам