An efficient algorithm for deciding quadratic residuosity in finite fields \(GF(p^ m)\) (Q1822956)

This paper presents an efficient algorithm for deciding quadratic residuacity in finite fields \(GF(p^ m)\) (p: odd prime, m: positive integer). The underlying idea of the proposed algorithm is to represent finite fields \(GF(p^ m)\) by matrices over GF(p) with respect to the defining irreducible polynomial f(x) over GF(p). The algorithm computes quadratic residuacity of any non-zero element \(a\in GF(p^ m)\) with the matrix operations over GF(p) and the evaluation of Legendre's and Jacobi's symbol in GF(p), if the constant term \(f_ 0\) of the defining irreducible polynomial f(x) of degree m satisfies that \(((-1)^ m/p)=- 1\), where (\(\cdot /\cdot)\) denotes the Legendre symbol. Input: f(x)\(=x^ m+f_{m-1}x^{m-1}+...+f_ 1x+f_ 0\) (defining irreducible \(polynomial),\) a\(=a_{00}+a_{10}x+...+a_{m-1,0}x^{m-1}\) (non-zero element in \(GF(p^ m)),\) where \(f_ i\), \(a_{i0}\in GF(p)\) (0\(\leq i\leq m-1);\) Step 1: \(a=[a_{00},a_{10},...,a_{m-1,0}]^ T;\) Step 2: Compute \(a_ i=Fa_{i-1}=[a_{0i},a_{i1},...,a_{m-1,i}]^ T\) (1\(\leq i\leq m-1)\), wher F is a companion matrix of the defining irreducible polynomial f(x); Step 3: Set \(S=[a_ 0,a_ 1,...,a_{m-1}];\) Step 4: Compute (\(| S| /p)\), where (\(\cdot /\cdot)\) denotes the Legendre symbol. The algorithm efficiently runs especially for finite fields \(GF(p^ m)\) of large characteristic p and dimension m.