Поля Галуа/ 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