Операции в поле Галуа GF (2^8)

Question

Всем привет!

1. Я пытаюсь найти обратный элемент в поле Галуа (2^8) по заданному модулю, но видимо у меня не хватает знаний чтобы понять. В учебном задании сказано, что при реализации мы не можем хранить какие-то состояния, следовательно предполагается что нужно реализовать без таблиц степеней и логарифмов. Или можно было бы каждый раз генерировать при запуске программы заново таблицу, но наверное это странно если мы можем менять модуль с каждым запуском. В википедии сказано что мы можем использовать расширенный алгоритм евклида.

Вот псевдкод:

 function inverse(a, p)
    t := 0;     newt := 1
    r := p;     newr := a

    while newr ≠ 0 do
        quotient := r div newr
        (r, newr) := (newr, r − quotient × newr)
        (t, newt) := (newt, t − quotient × newt)

    if degree(r) > 0 then 
        return "Either p is not irreducible or a is a multiple of p"

    return (1/r) × t

Меня в нём смущает строчка quotient := r div newr. Я не понимаю как это работает, если у нас и r и newr - некие полиномы, а операция деления над полем не задана. И то же самое с 1/r. Ведь для деления нужно сначала найти обратный мультипликативный элемент.

Поясните эти вещи, пожалуйста и можно ли как-то проще находить обратный элемент в заданном поле?

2. Проверьте двоичный полином степени 8 на неприводимость над ??(2^8); В голову пришло только перемножать последовательно элементы и проверять, получается ли в процессе этот полином или нет. Но есть ли какой-то более адекватный вариант (не алгоритм Берлекэмпа,он для меня тоже не очень понятен), напишите, пожалуйста. Буду благодарна за любые ответы, которые помогут лучше разобраться в теме.

Answer 1

Концептуально самый простой способ вычислить обратный элемент - возвести элемент в 254 степень.

Обоснование. В поле GF(2^8) 256 элементов. В мультипликативной группе поля 255 элементов. Группа циклическая, порядок любого элемента является делителем порядка группы. То есть любой элемент в степени 255 должен давать единицу. Другими словами, для любого элемента x справедливо 1 == x * x^254, следовательно x^254 - обратное к x. Вычисление требует 15 умножений. Каждое умножение требует от 2 до 16 сдвигов.

Но с вычислительной точки зрения самый быстрый способ - расширенный алгоритм Евклида. Да, нужно деление с остатком, но для полиномов над GF(2^8) его реализовать несложно. Не более 8 сдвигов вправо на операцию.

БЛОГ НА HUSL

Операции в поле Галуа GF (2^8)

Ответы (1 шт):