An efficient algorithm for deciding quadratic residuosity in finite fields \(GF(p^ m)\)
type: Item
instance of: scholarly article
title: An efficient algorithm for deciding quadratic residuosity in finite fields \(GF(p^ m)\)
zbMATH Open document ID: 0679.68059
DOI: 10.1016/0020-0190(89)90127-0
author: Toshiya Itoh
author: Shigeo Tsujii
published in: Information Processing Letters
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 11R09
Mathematics Subject Classification ID: 11T55
zbMATH DE Number: 4113983
zbMATH Keywords: Euler's criterion
zbMATH Keywords: quadratic residuacity in finite fields
zbMATH Keywords: Legendre symbol
MaRDI profile type: Publication
full work available at URL: 0020-0190(89)90127-0
OpenAlex ID: W1983731997
cites work: Q5690468
cites work: Q4146667
cites work: Number theory in science and communication. With applications in cryptography, physics, digital information, computing, and self- similarity.
cites work: Gaussian elimination is not optimal
description: scientific article; zbMATH DE number 4113983