Как можно реализовать умножение в конечных полях?

Question

Если F:= GF(p^n) - конечное поле с p ^ n элементами, где p - простое число, а не натуральное число, существует ли эффективный алгоритм для вычисления произведения двух элементов в F?

Вот мои мысли до сих пор:

Я знаю, что стандартная конструкция F состоит в том, чтобы взять неприводимый многочлен f степени n в GF(p), а затем рассматривать элементы F как многочлены в частном GF(p)[X]/(f), и у меня есть Я чувствую, что это, вероятно, уже правильный подход, поскольку полиномиальное умножение и сложение должно быть легко осуществимо, но я почему-то не понимаю, как это можно сделать на самом деле. Например, как выбрать подходящий f и как получить класс эквивалентности произвольного полинома?

Answer 1

Сначала выберите неприводимый многочлен степени n над GF[p]. Просто порождайте случайные, случайный многочлен неприводим с вероятностью ~ 1 / n.

Чтобы проверить ваши случайные полиномы, вам понадобится некоторый код для разложения полиномов по GF[p], см. Страницу википедии с некоторыми алгоритмами.

Тогда ваши элементы в GF[p^n] являются просто полиномами n-степени над GF[p]. Просто сделайте обычную полиномиальную арифметику и убедитесь, что вычислите остаток по модулю вашего неприводимого полинома.

Кодировать простые версии этой схемы довольно просто. Вы можете сколь угодно усложнить реализацию, скажем, операции по модулю. Смотрите модульное возведение в степень, умножение Монтгомери и умножение с использованием БПФ.

Answer 2

Существует ли эффективный алгоритм умножения элементов в GF(p^n), зависит от того, как вы представляете элементы GF(p^n).

Как вы говорите, один способ действительно работает в GF(p)(X)/(f). Сложение и умножение здесь относительно просты. Однако определить подходящий неприводимый многочлен f непросто - насколько я знаю, не существует эффективного алгоритма для вычисления подходящего f.

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

Вычисление с математическими структурами часто довольно сложно. Вы, конечно, не пропустите ничего очевидного здесь.

Answer 3

Это зависит от ваших потребностей и от вашей области.

Когда вы умножаете, вы должны выбрать генератор F^x. Когда вы добавляете, вы должны использовать тот факт, что F является векторным пространством для некоторого меньшего F_p^m. На практике то, что вы делаете много времени, - это смешанный подход. Например, если вы работаете над F₂₅₆, возьмите генератор X из F₂₅₆^x, и пусть G будет минимальным полиномом над F₁₆. Теперь у вас есть

(сумма_{i меньше 16} a_i Xⁱ) (сумма_{j меньше 16} b_j X^j) = сумма sum_k_{i + j = k} a_i b_j X^{i + j}

Все, что вам нужно сделать, чтобы сделать умножение эффективным, это сохранить таблицу умножения F₁₆ и (используя G) построить X^m в терминах меньших степеней X и элементов в F₁₆

В итоге, в редком случае, когда pⁿ = 2²ⁿ, вы получаете поле nimbers Конвея (см. "Пути победы" Конвея или раздел 7.1.3 тома 4А Кнута), для которого существуют очень эффективные алгоритмы.

Answer 4

Полевая арифметическая библиотека Галуа (C++, мод 2, не похоже, что она поддерживает другие простые элементы)

LinBox (C++)

MPFQ (C++)

Однако у меня нет личного опыта (я сделал свои собственные примитивные классы C++ для полей Галуа степени 31 или меньше, ничего слишком экзотического или заслуживающего копирования). Как и один из упомянутых комментаторов, вы можете проверить https://mathoverflow.net/ - просто спросите и убедитесь, что вы сделали свою домашнюю работу в первую очередь. Кто-то должен знать, какие виды математического программного обеспечения подходят для манипулирования конечными полями, и это достаточно близко к области интересов Mathoverflow, поэтому хорошо поставленный вопрос не должен закрываться.

Answer 5

Предположим, что это вопрос для алгоритма, выполняющего умножение в конечных полях, когда идентифицирован монический неприводимый многочлен f(X) (иначе рассмотрите тест Рабина на неприводимость )

У вас есть два многочлена степени n-1

      A(X) = a_0 + a_1*X + a_2*X^2 + ... + a_(n-1)*X^(n-1) and
B(X) = b_0 + b_1*X + b_2*X^2 + ... + b_(n-1)*X^(n-1)

Коэффициенты a_k, b_k находятся вне представителей {0,1,..., р-1} из Z / пз .

Продукт определяется как

      C(X) = A(X)*B(X) % f(X),

где оператор по модулю «%» - это остаток от полиномиального деления A (X) * B (X) / f(X) .

Ниже приводится подход со сложностью O (n ^ 2).

1.) По закону распределения продукт можно разложить на

        B(X) * X_(n-1) * a_(n-1)
+ B(X) * X_(n-2) * a_(n-2)
+ ...
+ B(X) * a_0

знак равно

        (...(a_(n-1) * B(X)  * X 
   +  a_(n-2)  * B(X)) * X
   +  a_(n-3)  * B(X)) * X
   ...
   +  a_1      * B(X)) * X
   +  a_0      * B(X)

2.) Поскольку% -оператор является гомоморфизмом колец из Z / pZ [X] на GF (p ^ n), он может применяться на каждом шаге итерации выше.

       A(X)*B(X) % f(X) =

  (...(a_(n-1) * B(X)  * X % f(X)
   +  a_(n-2)  * B(X)) * X % f(X)
   +  a_(n-3)  * B(X)) * X % f(X)
   ...
   +  a_1      * B(X)) * X % f(X)
   +  a_0      * B(X)

3.) После каждого умножения на X , то есть сдвига в пространстве коэффициентов, у вас есть многочлен T_k (X) степени n с элементом t_kn * X ^ n . Приведение по модулю f(X) осуществляется с помощью

      T_k(X) % f(X) = T_k(X) - t_kn*f(X),

который является многочленом степени n-1.

Наконец, с редукционным полиномом

      r(x) := f(x) - X^n  and

T_k(X) =: t_kn * X^n + U_(n-1)(X)

T_k(X) % f(X) = t_kn * X^n + U_(n-1)(X) - t_kn*( r(x) + X^n)
              = U_(n-1)(X) - t_kn*r(x)

т.е. все шаги могут быть выполнены с многочленами максимальной степени n-1.