square root of a finite field element in C++

Question

Is there any implementation of a method to obtain the square root of an element from a finite field. Programmed in C++ I was using NTL but the do not provide a method to do that. Thanks in advance

Answer 1

So in fact NTL libraries provide a method called ZZ::SqrRootMod(...) with several overloads. The method actually fulfill the functionality I described. I would like to give you guys an example as well so for instance:

   ZZ response;

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

Were value could be of several numeric types as long as it can be cast to ZZ e.g.(ZZ_p,int)

This came to my attention after I receive an email from Prf. Shoup to whom am I thank for.

Answer 2

If GF(2^m) is small enough to use log and exponentiate tables, then square root of x can be implemented using tables, log[] and exp[]

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

If GF(2^m) is too large to use log and exponentiation tables, there is an alternative method. GF(2^m) is isomorphic to its field of square roots, since if a + b = c and a • b = d, then (a + b)^2 = a^2 + b^2 = c^2, and (a • b)^2 = a^2 • b^2 = d^2. The elements of GF(2^m) can be mapped to their square roots using an m by m matrix with 1 bit elements, where the values in the columns represent powers of the square root of 2 which is 2^z (field math), where z =(2^m)/2 (integer math), which can be quickly calculated using exponentiation by squaring:

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

Let σ = sqrt(2), then the square roots of 0 and powers of 2 are:

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

For the mapping matrix, the columns are indexed by powers of 2, and the values in the columns are the square roots of those powers of 2. For example, GF(2^8) with reducing polynomial x^8 + x^4 + x^3 + x^2 + 1 (hex 11D), treat an element of GF(2^8) as a matrix E[8][1], and the mapping matrix below as M[8][8], then the square root S[8][1] = M[8][8] • E[8][1] (carryless multiply since these are 1 bit elements of 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

Answer 3

Perhaps John Kerl's "Computation in finite fields" (sadly an oldish unfinished manuscript) gives some hints. As far as I know, there are no efficient algorithms, but I could very well be completely wrong. You should ask at http://math.stackexchange.com or http://cs.stackexchange.com.