Квадратный корень из конечного элемента поля в C++

Есть ли реализация метода для получения квадратного корня элемента из конечного поля. Запрограммированный на C++, я использовал NTL, но у меня нет способа сделать это. заранее спасибо

Источник

3 ответа

Решение

Таким образом, библиотеки NTL предоставляют метод с именем ZZ::SqrRootMod(...) с несколькими перегрузками. Метод фактически выполняет функциональность, которую я описал. Я хотел бы привести вам пример, например, так:

   ZZ response;

   response= SqrRootMod(conv<ZZ>(value), conv<ZZ>(prime));

Если бы значение могло иметь несколько числовых типов, при условии, что оно может быть приведено к ZZ, например (ZZ_p, int)

Это привлекло мое внимание после того, как я получил письмо от Прф. Покажите мне, за кого я благодарен.

Источник

Если GF(2 ^ m) достаточно мал, чтобы использовать таблицы журнала и возведения в степень, то квадратный корень из x может быть реализован с использованием таблиц, log [] и exp []

      L = log(x)
if (L is odd) L = L + 2^m - 1
E = L / 2
square root = exp(E)

Если GF(2^m) слишком велико для использования логарифмических таблиц и таблиц возведения в степень, существует альтернативный метод. GF(2^m) изоморфна своему полю квадратных корней, так как если a + b = c и a • b = d, то (a + b)^2 = a^2 + b^2 = c^2, и (а • б) ^ 2 = а ^ 2 • б ^ 2 = d ^ 2. Элементы GF(2 ^ m) могут быть сопоставлены с их квадратными корнями с использованием матрицы m на m с 1-битными элементами, где значения в столбцах представляют степени квадратного корня из 2, который равен 2 ^ ((2 ^ m)/2), который можно быстро вычислить с помощью возведения в степень в квадрате:

https://en.wikipedia.org/wiki/Экспоненциация_by_squaring

Пусть σ = sqrt(2), тогда квадратные корни из 0 и степени двойки равны:

      S[0] = 0
S[1] = 1
S[2] = σ
S[4] = S[2] • σ
S[8] = S[4] • σ
...

Для матрицы отображения столбцы индексируются степенями двойки, а значения в столбцах являются квадратными корнями этих степеней двойки. Например, GF(2^8) с уменьшающим полиномом x^8 + x^4 + x ^ 3 + x ^ 2 + 1 (шестнадцатеричный 11D), рассматривать элемент GF(2 ^ 8) как матрицу E [8] [1], а матрицу отображения ниже как M [8] [8], затем квадратный корень S[8][1] = M[8][8] • E[8][1] (умножение без переноса, так как это 1-битные элементы GF(2)).

      80 40 20 10 08 04 02 01    value of E

 0  0  0  0  0  0  1  0
 1  0  0  0  0  0  0  0
 0  0  1  0  0  0  0  0
 1  0  0  0  1  0  0  0    mapping
 1  1  1  0  0  0  0  0    matrix
 1  0  1  1  1  0  1  0
 0  0  1  0  1  1  0  0
 0  0  0  0  1  0  1  1

5c 08 2e 04 17 02 85 01    value of S
Источник

Возможно, "Вычисление в конечных полях" Джона Керла (к сожалению, старая незаконченная рукопись) дает некоторые подсказки. Насколько я знаю, эффективных алгоритмов не существует, но я вполне могу ошибаться. Вы должны спросить на http://math.stackexchange.com/ или http://cs.stackexchange.com/.

Источник
Другие вопросы по тегам