Short polynomial representations for square roots modulo \(p\)
type: Item
instance of: scholarly article
title: Short polynomial representations for square roots modulo \(p\)
zbMATH Open document ID: 1023.12002
DOI: 10.1023/A:1021819602497
author: Simon Joseph Agou
author: Marc Deléglise
author: Jean-Louis Nicolas
published in: Designs, Codes and Cryptography
publication date: 2003-04-03T00:00:00Z
review text: Let \(p\) be an odd prime, then a polynomial \(P(X) \in \mathbb F_p[X]\) is said to represent the square root in \(\mathbb F_p^*\) if \(P(X)\) satisfies \((P(a))^2 = a\) for all quadratic residues \(a \in \mathbb F_p^*\), or equivalently \(P(i^2) = \sigma_ii, \sigma_i \in\{-1,+1\}\), for \(1 \leq i \leq (p-1)/2\). It is shown that if we fix the signs \(\sigma_i\) for all \(1 \leq i \leq (p-1)/2\), i.e. we fix \(\sigma = (\sigma_1,\ldots, \sigma_{(p-1)/2})\), then there exists a unique polynomial \(P_\sigma \in \mathbb F_q[X]\) with degree at most \((p-3)/2\) and \(P(i^2) = \sigma_ii\). An explicit formula for the polynomials \(P_\sigma\) is presented and all polynomials representing the square root in \(\mathbb F_p^*\) are described in terms of the polynomials \(P_\sigma\). Furthermore the length, i.e. the number of nonzero coefficients, of polynomials that have degree at most \((p-3)/2\) and represent the square root in \(\mathbb F_p^*\) is investigated. It is shown that for \(p-1 = 2^ns\), \(s\) odd, there exist at least \(2^{2^{n-1}}\) polynomials \(P(X) \in \mathbb F_p[X]\) of degree at most \((p-3)/2\), length at most \(2^{n-1}\) and representing the square root in \(\mathbb F_p^*\). (This coincides with the well known fact that for \(n = 1\), i.e. \(p \equiv 3 \pmod 4\), the monomial \(X^{(p+1)/4}\) represents the square root.) Conversely the authors show that for fixed \(n\) and all but finitely many primes \(p\) of the form \(p = 2^ns+1\), \(s\) odd, the length of a polynomial with degree at most \((p-3)/2\) and representing the square root in \(\mathbb F_p^*\) is at least \(2^{n-1}\). Finally the authors show that there are binomials respectively trinomials of degree at most \((p-3)/2\) representing the square root if and only if \(p \equiv 5 \pmod 8\) respectively \(p = 12m+7\), \(m \geq 1\).
reviewed by: Wilfried Meidl
Mathematics Subject Classification ID: 12E20
Mathematics Subject Classification ID: 11T06
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 1892216
zbMATH Keywords: square root modulo \(p\)
zbMATH Keywords: Shanks algorithm
zbMATH Keywords: finite fields
MaRDI profile type: Publication
full work available at URL: a:1021819602497
OpenAlex ID: W2143225046
Recommended article: Square Roots mod p
Recommended article: Q3044344
Recommended article: POLYNOMIAL REPRESENTATIONS FOR n-TH ROOTS IN FINITE FIELDS
Recommended article: Roots of polynomials modulo prime powers
Recommended article: Polynomial Representations of Sums of Two Squares
Recommended article: Polynomials modulo \(p\) whose values are squares (elementary improvements on some consequences of Weil's bounds).
Recommended article: Taking \(p\)th roots modulo polynomials over finite fields
Recommended article: On the least square-free primitive root modulo \(p\)
Recommended article: Polynomials with roots mod \(p\) for all primes \(p\)
Recommended article: Root sets of polynomials modulo prime powers
description: scientific article; zbMATH DE number 1892216