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

http://en.cppreference.com/w/cpp/numeric/math/sqrt is this what you mean? — IllusiveBrian, Mar 18 '14 at 16:39
@Namfuak: The OP wants to find sqrt in Galois field (a.k.a finite field). The standard sqrt wont work. — yasouser, Mar 18 '14 at 16:41
@user3245438: see this related question: http://stackoverflow.com/questions/10718629/finite-field-galois-field-linear-algebra-library-for-c-not-c — yasouser, Mar 18 '14 at 16:41
Do you need a very fast implementation? Otherwise you could just take the logarithm, divide by 2 and invert the logarithm. — Peter G., Mar 18 '14 at 16:42

DaWNFoRCe · Accepted Answer · 2014-03-20T14:42:29.420

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.

rcgldr · Answer 2 · 2022-03-08T14:08:56.053

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

score 0 · Answer 3 · answered Mar 18 '14 at 16:53

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.

square root of a finite field element in C++

3 Answers3