Конечные поля. Выбор порождающего полинома

Как мне выбирать примитивный порождающий (ака "редуцирующий"?) полином для генерации конечного поля?
Я знаю, что для GF(p^n) он должен иметь степень n и быть неразложимым в Z/pZ, но как его выбрать?

Например, для GF(2^8) существует такой примитивный полином: x^8 + x^4 + x^3 + x^2 + 1.
А меня, честно говоря, интересует только полином для GF(2^16), хотя принцип выбора для более общего случая тоже был бы интересен.

P.S. Я не математик (duh), так что был бы признателен за возможно более простое объяснение.

 

Можно выбирать рандомно, а затем проверять - вычислять x^{2^n-1} по модулю этого многочлена.

 

Имхо любой примитивный сгодится, примитивность это необходимое и достаточное условие, разве не так?

Стандартный полином для таких целей - это 0x1100B,
хотя у меня в коллекции есть все такие пятибитовые полиномы.

Вот кусок кода из моей проги - построение поля и таблиц дискретных логарифмов. Логарифмы нужны чтобы заменить умножение на сложение логарифмов.

Код (Text):

1. const
2.  
3.    _RSPrimPoly:Cardinal=$1100B;
4.    _GFSize:Cardinal=65535;      
5.  
6. var  _GFLog,          
7.       _GFExp:Pointer;
8.  
9.  
10. procedure GFInit;
11. var b,log:Cardinal;
12. begin
13.  GetMem(_GFLog,(_GFSize+1)*SizeOf(Cardinal));
14.  GetMem(_GFExp,(_GFSize+1)*SizeOf(Cardinal));
15.  
16.  log:=0;
17.  b:=1;
18.  while log<_GFSize do begin
19.  
20.   _GFLog[b]:=log;
21.   _GFExp[log]:=b;
22.   b:=b shl 1;
23.   if (b>_GFSize) then b:=b xor _RSPrimPoly;
24.  
25.   inc(log);
26.  end;
27.  
28.  _GFLog[0]:=_GFSize; // просто заглушки, не использовать!!!
29.  _GFExp[_GFSize]:=0; // присоединение бесконечно-удаленной
30.                               // точки происходит иначе!
31. end;

 

Предвижу вопрос, а для чего нужна минус-бесконечная присоединенная точка к полю Галуа (которая лежит в ячейке Log[0]) ? Можно и без нее, но ее включают чтобы избавиться от проверок на ноль.

Так, умножение полиномов a и b проводят по формуле:
c=Exp[(Log[a] + Log) mod 65535 ]

Тут есть три проблемы:
1) Фомула не работает для a или/и b равных нулю.
Поэтому нужно проверять входные элементы на равенство нулю, что требует времени, сравнимого с вычислением основной функции.
2) Формула требует приведения mod 65535, что тоже требует времени.
3) Первые два обстоятельства создают особо много гимора для SIMD, который подразумевает вход однородных данных.

В расширенном поле умножение происходит по формуле:
c=Exp[ Log[a] + Log ]

Все! Не нужна проверка нуля и приведение суммы по модулю, ха-ха!
Вот к чему нужно стремиться в программной реализации.
Но тип данных должен быть длиннее чем word 16бит. поэтому у меня в примере uint32=Cardinal

 

Оо, благодарю. Всё принесло пользу. Тему можно считать закрытой.

Кроме того, было обнаружено: Fast Galois Field Arithmetic Library in C/C++, таблица примитивных полиномов включена.

 

посмотрел описание, 16-битное умножение там реализовано как раз через логарифмы.

Код (Text):

1. int galois_logtable_multiply(int x, int y, int w)
2. {
3.   int sum_j;
4.  
5.   if (x == 0 || y == 0) return 0;
6.  
7.   sum_j = galois_log_tables[w][x] + galois_log_tables[w][y];
8.   /* if (sum_j >= nwm1[w]) sum_j -= nwm1[w];    Don't need to do this,
9.                                    because we replicate the ilog table twice.  */
10.   return galois_ilog_tables[w][sum_j];
11. }

Ага, от приведения по модулю они избавились удвоением таблицы, это хорошо. А вот Log[0]="бесконечность" не используется, это плохо. Нулей их код боится и поспешно выходит из тела. Постоянные проверки на ноль и двойные массивы будут жрать заметное время... Мой те совет- забей на эту либру - единственное нужное тебе поле, а не на все случаи жизни, проще и надежнее реализовать самому.

 

Угу, но хорошая либа (вкупе с хорошими советами) будет использована как доля ссылочного материала при реализации.

 

Согласен, очень полезная и интересная ссылка!
А вот 16-бит полином там такой же, только записан в восьмиричном виде.