Short polynomial representations for square roots modulo \(p\) (Q1866025)

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\).