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

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

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

При умножении вы должны выбрать генератор 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 sum _{i + j = k} a _i b _j X ^{i + j}

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

В итоге, в редком случае, когда p ⁿ = 2 ^{2 n} , вы получаете поле Конвеев Конвея (смотрите в "Конвейских путях", или в томе 4А Кнута, раздел 7.1.3), для которого существуют очень эффективные алгоритмы.

Answer 3

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

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

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

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

Answer 4

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

LinBox (C ++)

MPFQ (C ++)

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