Представление конечного поля в ЭВМ

[AndreyXYZ]

Каким образом можно организовать на ЭВМ умножение и сложение в $GF(q),\,q=p^n,$ где $p$ --- простое?
Если $n=1,$ то самый удобный способ, на мой взгляд, работать с полем $\mathbb{Z}_p.$
В общем случае можно некоторым образом построить поле, поставить ему в соответствие таблицу сложения и умножения и работать с ними. Но хотелось бы увидеть более простой способ работы с элементами поля.

[Xaositect]

Можно воспользоваться тем, что $GF(p^n) = GF(p)[x]/(f(x))$, $f(x)$ - неприводимый многочлен $n$-й степени. Тогда элементы $GF(p^n)$ можно хранить как набор коэффициентов многочлена. И как глобальную переменную или константу хранить многочлен f.
C $GF(2^n)$ достаточно просто - элемент поля представляется в виде $n$ битов - коэффициентов многочлена и операции можно реализовать через побитовые операции над целыми числами.

[mkot]

А для умножения можно ещё заметить следующее. Так как мультипликативная группа конечного поля является циклической, то все ненулевые элементы являются степенями некоторого первообразного элемента, Следовательно, умножение, можно свести к сложению показателей. Достаточно для этого раз и навсегда построить соответствующую таблицу.
Например рассмотрим поле $\mathbb{F}_{2^2}$. Рассмотрим многочлен $f(x) = x^2 + x + 1$.
Он неприводим, пусть $\alpha$ -- его корень. То есть $\alpha^2 = \alpha + 1$.
Таким образом, элементами поля будут

$$0, 1, \alpha, \alpha + 1$$

.
Можно также заметить, что $\xi = \alpha$ -- первообразный элемент.
Тогда можно построить таблицу

$$\begin{array}{c|c} 0 & 0 \\ \alpha^3 & 1 \\ \alpha^1 & \alpha \\ \alpha^2 & \alpha + 1\\ \ldots \end{array}$$

Тогда, например, $\alpha \cdot (\alpha + 1) = \alpha^1 \cdot \alpha^3 = \alpha^3 = 1$.

Также элементы конечного поля представимы в виде матриц. Как это делается можно найти в замечательной книжке Лидла и Нидеррайтера Конечные поля на стр. 89-91.

[AndreyXYZ]

Xaositect писал(а):

Можно воспользоваться тем, что $GF(p^n) = GF(p)[x]/(f(x))$, $f(x)$ - неприводимый многочлен $n$-й степени. Тогда элементы $GF(p^n)$ можно хранить как набор коэффициентов многочлена. И как глобальную переменную или константу хранить многочлен f.
C $GF(2^n)$ достаточно просто - элемент поля представляется в виде $n$ битов - коэффициентов многочлена и операции можно реализовать через побитовые операции над целыми числами.

Где найти алгоритм построения неприводимого многочлена размерности $n$ над полем $GF(p)$?

Если действовать методом, который я предложил изначально:

AndreyXYZ в сообщении #207892 писал(а):

В общем случае можно некоторым образом построить поле, поставить ему в соответствие таблицу сложения и умножения и работать с ними. Но хотелось бы увидеть более простой способ работы с элементами поля.

то какой самый простой алгоритм построения конечного поля (построения 2-х таблиц)?

[sermp]

Есть хорошая библиотека NTL от Victora Shoup'а http://shoup.net/ntl на с++, кросс-платформенная, поддерживает работу с полиномами и матрицами.

[VAL]

AndreyXYZ в сообщении #207919 писал(а):

Xaositect писал(а):

Можно воспользоваться тем, что $GF(p^n) = GF(p)[x]/(f(x))$, $f(x)$ - неприводимый многочлен $n$-й степени. Тогда элементы $GF(p^n)$ можно хранить как набор коэффициентов многочлена. И как глобальную переменную или константу хранить многочлен f.
C $GF(2^n)$ достаточно просто - элемент поля представляется в виде $n$ битов - коэффициентов многочлена и операции можно реализовать через побитовые операции над целыми числами.

Где найти алгоритм построения неприводимого многочлена размерности $n$ над полем $GF(p)$?

В классической монографии Р.Лидл, Г.Нидеррайтер. Конечные поля.

Другой вариант - подобрать неприводимый многочлен методом научного тыка.
С учетом того, что неприводимых полиномов много довольно много, а алгоритм Берлекэмпа (проверки на неприводимость) работает очень быстро, этот способ вполне эффективен.
Кстати, у Лидла с Нидеррайтером в приложениях есть таблицы неприводимых полиномов.

Наконец, в некоторых системах компьютерной алгебры, например, в Maple есть готовые библитеки для работы сконечными полями. Задавая конечное поле можно заранее указать, наряду с $p$ и $n$, неприводимый полином. А можно этого и не делать. Тогда Maple предложит свой вариант.

-- 19 май 2009, 02:33 --

AndreyXYZ в сообщении #207919 писал(а):

Если действовать методом, который я предложил изначально:

AndreyXYZ в сообщении #207892 писал(а):

В общем случае можно некоторым образом построить поле, поставить ему в соответствие таблицу сложения и умножения и работать с ними. Но хотелось бы увидеть более простой способ работы с элементами поля.

то какой самый простой алгоритм построения конечного поля (построения 2-х таблиц)?

Учитывая простоту выполнения сложения в любом конечном поле, хранить таблицу сложения - странное решение.
Умножение в представлении с помощью полиномиального базиса (представление с помощью первообразного корня прекрасно годится для умножения, но неудобно для выполнения сложения) тоже выполняется не слишком долго. Но если критично быстродействие, а не память, то, разумеется можно и таблицу построить. Опять таки с помощью уже упомянутых представлений. Или других. Например, матричного.

[maxal]

Могу посоветовать библиотеку PARI - там такие операции как проверка многочлена на неприводимость и разложение на неприводимые множители осуществляются одной командой:
http://pari.math.u-bordeaux.fr/

[sermp]

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

[VAL]

sermp в сообщении #215145 писал(а):

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

Вашего способа не понял.
Но я бы проверял по определению, последовательно деля многочлены $x^k-1$ на наш многочлен. Здесь $k$ - максимальные (по делимости) делители $q^m-1$, отличные от самого $q^m-1$, $m$ - степень данного многочлена, а $q$ - число элементов поля.

[sermp]

Да, я не совсем точно выразился и забыл исключить делители $q-1, q^2-1$ и т.д.
Имел ввиду я следующее, чтобы проверить является ли многочлен $F(x)$ степени $m$ над полем $GF(q)$ примитивным надо:
1) Найти все $t$, такие что $t\ |\ q^m - 1,\ t \not |\ q^k - 1,\ k=\overline{1,m-1}$ и $t<q^m - 1$
2) Для каждого такого $t$ проверить, что $x^t \not \equiv 1 (modd\ F(x))$. Если же $\exists t: x^t \equiv 1 (modd\ F(x))$, значит $F(x) $
не является примитивным.
Т.е. мы с Вами говорим об одном алгоритме.