c++ - C ++中有限域元素的平方根

Question

是否有任何方法可以从有限域中获得元素的平方根。用 C++ 编程我使用的是 NTL，但没有提供这样做的方法。提前致谢

Answer 1

所以实际上 NTL 库提供了一个名为 ZZ::SqrRootMod(...) 的方法，它有几个重载。该方法实际上实现了我描述的功能。我也想给你们举个例子，例如：

   ZZ response;

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

只要可以将值转换为 ZZ 例如（ZZ_p,int），值就可以是多种数字类型

在收到 Prf 的电子邮件后，这引起了我的注意。我要感谢谁。

Answer 2

如果 GF(2^m) 小到可以使用 log 和 exponentiate 表，那么 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，和 (a • b)^2 = a^2 • b^2 = d^2。GF(2^m) 的元素可以使用具有 1 位元素的 m × m 矩阵映射到它们的平方根，其中列中的值表示 2 的平方根的幂，即 2^((2^m )/2)，可以通过平方使用幂来快速计算：

https://en.wikipedia.org/wiki/Exponentiation_by_squaring

设 σ = sqrt(2)，则 0 的平方根和 2 的幂为：

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

对于映射矩阵，列以 2 的幂为索引，列中的值是 2 的幂的平方根。例如，GF(2^8) 与约简多项式 x^8 + x^4 + x^3 + x^2 + 1 (hex 11D)，把GF(2^8)的一个元素当作矩阵E[8][1]，下面的映射矩阵当作M[8][8]，则平方根 S[8][1] = M[8][8] • E[8][1]（无进位乘法，因为这些是 GF(2) 的 1 位元素）。

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

Answer 3

也许 John Kerl 的“有限域中的计算”（可悲的是一份陈旧的未完成手稿）给出了一些提示。据我所知，没有有效的算法，但我很可能完全错了。您应该在http://math.stackexchange.com或http://cs.stackexchange.com询问。