GF2p8 Нахождение корней образующего полинома

Понадобилось больше теории, чтобы перейти к композитным полям. Но все попадаются сатьи индусов с ведической алгеброй или индусов из исследовательского центра IBM в Индии. В единственном нормальном учебнике, который мне попался по теории Галуа и кодам Рида-Соломона, слово "корень" употребляется всего один раз, вообще один раз на все сто-пятьсот страниц, и без определения.

Допустим A -- один из корней образующего полинома p(x) = x⁸+x⁴+x³+x+1. При сложении коэффициентов при степенях используется арифметика по модулю 2. Степени A образуют полиномиальный базис [1,A,A²,A³,A⁴,A⁵,A⁶,A⁷], который далее может использоваться для вычисления матриц изоморфных преобразований и представления элементов поля.

Что значит корень? Это значит, что подстановка "корня" в образующий поле полином (8-ого порядка) дает ноль:
P(A) = с₈A⁸ + с₇A⁷ + ... + c₂A² + c₁A¹ + c₀=0.
Здесь коэффициенты при степенях (c_k) те же, что и в образующем полиноме.
Как найти корень? Чтобы найти в одно действие какой-то корень надо отбросить от образующего полинома степень 8, получим полином 7й степени – это один из корней (x⁴+x³+x+1). Отбрасывание старшего порядка равносильно операции A = x⁸ mod P(x). Остальные корни находим методом возведения полученного корня в квадрат, рекурсивно. Всего будет 8 корней для полинома 8 порядка.

// Проверка на корень
int gf2p8_is_root(uint8_t a, uint32_t Poly)
{
	uint8_t v=1, r=0;
	uint32_t p = Poly;
	while (p) {
		if(p&1) r ^= v;
		v = gf2p8_mul(v, a, Poly);
		p>>=1;
	}
	return (r==0);
}

Полином поля можно представить иначе, с учетом знания о корнях, как произведение:
P(x)= (x-A)(x-A²)(x-A⁴)(x-A⁸)(x-A¹⁶)(x-A³²)(x-A⁶⁴)(x-A¹²⁸).

Все корни образующего полинома поля GF(2^m)образуют циклическую группу по операции возведения в квадрат.

Для полинома восьмого порядка сразу можно выделить четыре корня: A =x¹, x², x⁴, x⁸ mod P(x). Остальные четыре корня надо считать.

Свойства поля Галуа GF(p^m):

1. Существует порождающий примитивный элемент поля (геренатор поля), такой что любой не нулевой элемент поля может быть выражен, как степень порождающего элемента поля. Мультипликативная группа циклична.
2. Для любого элемента (g) поля GF(p^m) справедливо: g^pm-1 = 1, g^-1 = g^pm-2.
3. Любой элемент поля может быть выражен суммой из m элементов поля. Для выражения элементов поля используются m элементов, составляющих полиномиальный базис. Элемент поля можно представить через полиномиальный базис: a₀ +a₁A +a₂A² +...+a_m−1A^m−1.
4. В поле GF(p^m) выполняется равенство: (a + b)^p = a^p + b^p (mod p)
5. Если элемент A поля GF(p^m) - корень нередуцируемого полинома P(x) степени m, то остальными корнями P(x) будут элементы: A^p, A^p2, . . . , A^pm-1.
6. Для любого простого числа p и любого нередуцируемого полинома P(x) степени m существует только одно поле Галуа GF(p^m). Поля Галуа GF(p^m), образованные различными нередуцируемыми полиномами степени m изоморфны.

Ниже привожу все корни от 30 нередуцируемых полиномов 8-ого порядка, и корни для полиномов 4-ого порядка.

Таблица корней полинома 8-ого порядка
11B: 02 04 10 1B 5E E4 4D FA
11D: 02 04 10 1D 4C 9D 5F 85
12B: 02 04 10 2B E9 EE FB C1
12D: 02 04 10 2D E5 5D F6 75
139: 02 04 10 39 9C 4E 8F 72
13F: 02 04 10 3F 96 91 84 AA
14D: 02 04 10 4D F8 E3 EB AB
15F: 02 04 10 5F 86 9A 95 C0
163: 02 04 10 63 F3 F4 E1 93
165: 02 04 10 65 8B 8C 99 ED
169: 02 04 10 69 03 05 11 68
171: 02 04 10 71 F3 2F E0 5B
177: 02 04 10 77 8B 3A 98 48
17B: 02 04 10 7B 03 05 11 7A
187: 02 04 10 87 6F 1D D6 34
18B: 02 04 10 8B AA 1A CF E3
18D: 02 04 10 8D 3D 7F 60 B8
19F: 02 04 10 9F 7D 59 94 38
1A3: 02 04 10 A3 70 CD 4A 43
1A9: 02 04 10 A9 18 E9 CD 82
1B1: 02 04 10 B1 66 5F B8 27
1BD: 02 04 10 BD 95 E6 A1 78
1C3: 02 04 10 C3 1F 96 A0 FD
1CF: 02 04 10 CF 76 A0 58 56
1D7: 02 04 10 D7 EB 9E CC 79
1DD: 02 04 10 DD 61 4D D3 35
1E7: 02 04 10 E7 7D 4B EA 2C
1F3: 02 04 10 F3 C1 1C A3 9A
1F5: 02 04 10 F5 28 7E 67 D3
1F9: 02 04 10 F9 6F 1B BC 26

Таблица корней полинома 4-ого порядка
13: 2 4 3 5
19: 2 4 9 E
1F: 2 4 F 8