Поля Галуа/ GF (2^8)?на мой взгляд ответ =0

Не могу решить задачу, на мой взгляд ответ 0.

Выполните операцию умножения 0x5A и 0xA5 в поле Галуа GF (2^8) с неприводимым многочленом 0x11B


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

Автор решения: Pak Uula

Коротко 0x7e

Длинно

По определению поля, множество ненулевых элементов образует абелеву группу по умножению. Поэтому в вашем примере произведение двух элементов никак не может быть равным нулю.

Вот вам программа на языке Пайтон, которая перемножает полиномы в поле GF(2^8)

def gf_mul(a, b, modulo, details=False):
    """
    Умножение двух многочленов в поле GF(2^8).
    
    Многочлены представлены в виде целых чисел, где каждый бит соответствует коэффициенту при соответствующей степени x.
    Например, многочлен x^7 + x^5 + 1 будет представлен как 0b10010001 или в 0x91.
    """
    result = 0
    if details:
        print(f"Умножаем {poly(a)} на {poly(b)} по модулю {poly(modulo)}")
    a0 = a # Сохраняем начальное значение a для вывода
    for i in range(8):
        if b == 0:
            break
        if b & 1:
            if details:
                print(f"  слагаемое: {poly(1<<i)}*({poly(a0)}) mod ({poly(modulo)}) = {poly(a)}")
                print(f"({poly(result)}) + ({poly(a)}) = {poly(result ^ a)}")
            result ^= a  # Добавляем a к результату
        hi_bit_set = a & 0x80  # Проверяем, есть ли в многочлене a член x^7
        a <<= 1  # Умножаем a на x
        if hi_bit_set: 
            # Если был член x^7, то после умножения на x старший член стал x^8, и многочлен нужно редуцировать
            a ^= modulo  # Редуцируем по модулю неприводимого многочлена
        a &= 0xFF  # Отбрасываем старшие биты, которые появились в результате редукции
        b >>= 1  # Делим многочлен b на x
    return result

def poly(n: int) -> str:
    """
    Преобразует число в строку многочлена.
    Например, 0b10010001 будет преобразовано в "x^7 + x^5 + 1".
    """
    if n == 0:
        return "0"
    
    terms = []
    for i in reversed(range(n.bit_length())):
        if n & (1 << i):
            if i == 0:
                terms.append("1")
            elif i == 1:
                terms.append("x")
            else:
                terms.append(f"x^{i}")
    return " + ".join(terms)

Пример вычисления для ваших данных:

modulo = 0x11B  # Неприводимый многочлен для GF(2^8)
print("неприводимый многочлен:",poly(modulo))  # Пример неприводимого многочлена

a = 0x5A
print("a = ", poly(a))  

b = 0xA5
print("b = ", poly(b))

c = gf_mul(a, b, modulo=modulo)
print("a * b = ", poly(c))
print(f"{hex(a)} * {hex(b)} = {hex(c)}")
print(f"{a} * {b} = {c}")

Результат работы программы:

неприводимый многочлен: x^8 + x^4 + x^3 + x + 1
a =  x^6 + x^4 + x^3 + x
b =  x^7 + x^5 + x^2 + 1
a * b =  x^6 + x^5 + x^4 + x^3 + x^2 + x
0x5a * 0xa5 = 0x7e
90 * 165 = 126

Если хотите посмотреть перемножение по шагам, то добавьте аргумент details=true, тогда вывод будет такой

неприводимый многочлен: x^8 + x^4 + x^3 + x + 1
a =  x^6 + x^4 + x^3 + x
b =  x^7 + x^5 + x^2 + 1
Умножаем x^6 + x^4 + x^3 + x на x^7 + x^5 + x^2 + 1 по модулю x^8 + x^4 + x^3 + x + 1
  слагаемое: 1*(x^6 + x^4 + x^3 + x) mod (x^8 + x^4 + x^3 + x + 1) = x^6 + x^4 + x^3 + x
(0) + (x^6 + x^4 + x^3 + x) = x^6 + x^4 + x^3 + x
  слагаемое: x^2*(x^6 + x^4 + x^3 + x) mod (x^8 + x^4 + x^3 + x + 1) = x^6 + x^5 + x^4 + x + 1
(x^6 + x^4 + x^3 + x) + (x^6 + x^5 + x^4 + x + 1) = x^5 + x^3 + 1
  слагаемое: x^5*(x^6 + x^4 + x^3 + x) mod (x^8 + x^4 + x^3 + x + 1) = x^7 + x^5 + x^4 + x^2 + 1
(x^5 + x^3 + 1) + (x^7 + x^5 + x^4 + x^2 + 1) = x^7 + x^4 + x^3 + x^2
  слагаемое: x^7*(x^6 + x^4 + x^3 + x) mod (x^8 + x^4 + x^3 + x + 1) = x^7 + x^6 + x^5 + x
(x^7 + x^4 + x^3 + x^2) + (x^7 + x^6 + x^5 + x) = x^6 + x^5 + x^4 + x^3 + x^2 + x
a * b =  x^6 + x^5 + x^4 + x^3 + x^2 + x
0x5a * 0xa5 = 0x7e
90 * 165 = 126
→ Ссылка